Форум программистов, компьютерный форум CyberForum.ru

Визуализация графа (реализация алгоритма) - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Вычислить по координатам http://www.cyberforum.ru/cpp-beginners/thread793853.html
Привет всем!Помогите,пожалуйста,нужно проверить,лежит ли точка в этом ромбе или нет,вообщем-логические операции.Спасибо большое.
C++ Пытался изменить чужую программу, не смог понять смысл оператора стрелочка #include <iostream> #include "CalcEval.h" using namespace std; int main (int argc, char *const argv) { FILE *WorkOut = fopen("C:\\WORK\\CalcEval.Out", "w"); CalcEval *eval = new CalcEval(); eval->getMultAB(2f, 2f); // не понимаю смысла этой стрелочки fputs(eval, WorkOut); // хотел сбросить полученную строку в файл - не фортануло http://www.cyberforum.ru/cpp-beginners/thread793850.html
Вычислить значения синусов C++
Помогите пожалуйста решить задачу на си++ Вычислите значения а) sin x + sin2x + ... + sinnx; б) sin x + sin2x2 + ... + sinnxn; в) sin x + sin x2 + ... + sin xn ; г) sin x + sin sin x+ .. + sin sin...sin x (n раз).
C++ Для заданного вектора X(2N ) вычислить выражение
Помогите пожалуйста решить задачу на си++ Для заданного вектора X(2N ) вычислите Y = x1 - x2 + x3 - ... - x2N . Создавайте тему в соответствующем разделе. Один вопрос - одна тема
C++ Определить, имеется ли среди заданных целых чисел A, B, C хотя бы одно чётное http://www.cyberforum.ru/cpp-beginners/thread793834.html
Помогите пожалуйста решить задачу на си++ Определите, имеется ли среди заданных целых чисел A, B, C хотя бы одно чётное.
C++ Решить линейное уравнение ax = b Помогите пожалуйста решить задачу на си++ Решите линейное уравнение ax = b. подробнее

Показать сообщение отдельно
Avazart
Эксперт С++
7115 / 5292 / 273
Регистрация: 10.12.2010
Сообщений: 23,382
Записей в блоге: 17

Визуализация графа (реализация алгоритма) - C++

24.02.2013, 18:09. Просмотров 3352. Ответов 8
Метки (Все метки)

Начало темы Визуализация графов

Нашел описание алгоритма визуализации графа.
Но как реализовывать не совсем ясно.

В общем о иерархическом подходе
Наиболее же известную идею размещения ациклических графов можно
рассматривать как обобщение случая размещения деревьев. Для подчерки-
вания иерархичности структуры используются, как и в древесном случае,
поуровневые представления, в которых все дуги следуют одному и тому же
направлению [66]. Такие представления называются монотонными поуров-
невыми представлениями.
Настоящая работа посвящена обзору такой методологии (иерархиче-
ский подход), применяемой для размещения ациклических графов. Данный
подход является крайне интуитивным и позволяет для произвольного ацик-
лического графа построить монотонное поуровневое представление с реб-
рами в виде ломанных или сплайнов. Первоначально идея была сформули-
рована еще в 1981 году [74], а также в некоторых других очень близких по
тематике работах [77, 20]. Дальнейшее развитие (см. аннотированную биб-
лиографию [9]) сохранило основную концепцию, в которой иерархический
подход содержит три части:

1) распределение вершин по уровням так, чтобы все дуги следовали
одному направлению;
2) выбор порядка вершин на уровне с целью минимизации пересече-
ний ребер;
3) определение координат вершин на уровне с целью минимизации
общей длины ребер и количества изломов.

Следует отметить, что данный подход оперирует различными эстетиче-
скими критериями на каждом из своих шагов.

Для успешного применения иерархического подхода система изображе-
ния графов (исходные данные, визуализирующая компонента, область при-
менения) должна удовлетворять следующим ограничениям:

1) исходный граф должен быть ациклическим мультиграфом или
мультиграфом, «близким» к ациклическому. Близость здесь следует
понимать в том смысле, что смена ориентации малого количества дуг
должна превратить граф в ациклический;

2) семантика графовой информации должна предполагать возмож-
ность построения монотонного изображения, подчеркивающего на-
правленность или наличие некоторого порядка на множестве вершин;

3) система визуализации не должна предполагать проведение только
прямолинейных ребер между вершинами графа. Ребра должны быть
изображены в виде ломанных или сплайнов


ЭТАПЫ ИЕРАРХИЧЕСКОГО ПОДХОДА

1. Распределение вершин по уровням. Каждой вершине u присваива-
ется число L(u), указывающее уровень этой вершины так, чтобы
все дуги, соединяющие вершины, следовали от меньшего номера к
большему, при этом вершины одного уровня не должны быть свя-
заны между собой. Подразумевается, что все вершины одного
уровня будут расположены на одной прямой — вертикальной или
горизонтальной — в зависимости от того, какое мы предпочитаем
общее направление размещения: сверху вниз или слева направо.

После проведения распределения вершин по уровням просматри-
ваются все дуги: если дуга e = (u,v) проходит через несколько уров-
ней, т.е. L(u) – L(v) > 1, то она удаляется из графа и заменяется на
цепочку фиктивных вершин v1,…,vN такую, что v1 = u, vN = u, каж-
дая вершина vi соединена дугой с vi+1 и L(vi+1) = L(vi) + 1, а v1 = v и
vN = u.

2. Определение порядка вершин на уровне. Задача данного шага со-
стоит в сортировке вершин на каждом из уровней. Порядок вер-
шин определяет топологию конечного изображения и должен быть
выбран с целью минимизации пересечений ребер графа.

3. Определение координат вершин на уровне. На данном шаге каж-
дой вершине присваивается вертикальная координата (при разме-
щении в горизонтальном направлении) так, чтобы сохранить поря-
док вершин на уровне, который был вычислен на предыдущем ша-
ге. Координата выбирается с целью минимизации общей длины
ребер и количества изломов. Наконец, конечное изображение по-
лучается представлением каждого ребра в виде прямолинейного
отрезка и удаления фиктивных вершин. В этом случае длинные
ребра оказываются изображенными в виде ломанных.
Визуализация графа (реализация алгоритма)

Взято от сюда http://www.iis.nsk.su/files/articles...09_baburin.pdf
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru