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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 24, средняя оценка - 4.83
Avazart
 Аватар для Avazart
6904 / 5144 / 253
Регистрация: 10.12.2010
Сообщений: 22,621
Записей в блоге: 17
24.02.2013, 18:09     Визуализация графа (реализация алгоритма) #1
Начало темы Визуализация графов

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

В общем о иерархическом подходе
Наиболее же известную идею размещения ациклических графов можно
рассматривать как обобщение случая размещения деревьев. Для подчерки-
вания иерархичности структуры используются, как и в древесном случае,
поуровневые представления, в которых все дуги следуют одному и тому же
направлению [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
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.02.2013, 18:09     Визуализация графа (реализация алгоритма)
Посмотрите здесь:

C++ Реализация алгоритма Мандельброта
Реализация алгоритма C++
C++ реализация алгоритма кодирования
Реализация алгоритма Йена на С++ C++
C++ Визуализация Алгоритма А*
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Avazart
 Аватар для Avazart
6904 / 5144 / 253
Регистрация: 10.12.2010
Сообщений: 22,621
Записей в блоге: 17
24.02.2013, 18:24  [ТС]     Визуализация графа (реализация алгоритма) #2
Вот попытка реализовать часть шага 1
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <iostream>
#include <iomanip>
 
#include <string>
#include <vector>
//------------------------------
using namespace std;
//---------------------------------------------------------------------------
struct vertex
{
    string name;
    int level;
    vertex(string _name):name(_name),level(0){}
};
//---------------------------------------------------------------------------
void dfs( vector<vertex>& v, vector<vector<int> >& g, int index,int start_level=1)
{
    if( v[index].level< start_level )
        {
            v[index].level= start_level++;
            for(size_t i=0; i<g[index].size(); ++i)
                dfs(v,g,g[index][i],start_level);
        }
}
//---------------------------------------------------------------------------
void print( vector<vertex>& v)
{
    for(size_t level=0; level<v.size(); ++level)
        {
            cout<<"level#"<<level<<"\t";
            for(size_t i=0; i<v.size(); ++i)
                if(v[i].level== level) cout<<v[i].name<<"\t";
            cout<<endl;
        }
}
//---------------------------------------------------------------------------
int main(int argc, char* argv[])
{
vector<vertex> v;
 
v.push_back(vertex("0."));
v.push_back(vertex("1."));
v.push_back(vertex("2."));
v.push_back(vertex("3."));
v.push_back(vertex("4."));
v.push_back(vertex("5."));
v.push_back(vertex("6."));
v.push_back(vertex("7."));
v.push_back(vertex("8."));
v.push_back(vertex("9."));
v.push_back(vertex("10."));
 
vector< vector<int> > g( v.size() );
 
g[0].push_back(2);
 
g[1].push_back(2);
g[1].push_back(5);
 
g[2].push_back(3);
g[2].push_back(4);
 
g[5].push_back(6);
 
g[7].push_back(8);
g[7].push_back(9);
 
g[8].push_back(5);
 
g[10].push_back(5);
 
for(size_t i=0; i<v.size(); ++i) dfs(v,g,i);
 
print(v);
 
getchar();
return 0;
}
//---------------------------------------------------------------------------
Вывод:
level#1 0. 1. 7. 10.
level#2 2. 8. 9.
level#3 3. 4. 5.
level#4 6.
Добавлено через 9 минут
Просьба к администрации подправить изображения в в посте N1
Миниатюры
Визуализация графа (реализация алгоритма)  
Jupiter
Каратель
Эксперт C++
6543 / 3963 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
24.02.2013, 22:00     Визуализация графа (реализация алгоритма) #3
Avazart, и? поиск в ширину отлично разбивает на уровни
Avazart
 Аватар для Avazart
6904 / 5144 / 253
Регистрация: 10.12.2010
Сообщений: 22,621
Записей в блоге: 17
24.02.2013, 23:12  [ТС]     Визуализация графа (реализация алгоритма) #4
Чет не догоняю что изменит смена на поиск в ширину ?

Я не могу как согласовать деревья поиска.

В моем примере level#1 занимают 0, 1, 7, 10 хотя graphViz поставил вершины 0,1,10 на уровень ниже и так лучше по тому как нет "растяжения" и не нужны доп. фиктивные вершины.
Jupiter
Каратель
Эксперт C++
6543 / 3963 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
24.02.2013, 23:56     Визуализация графа (реализация алгоритма) #5
Цитата Сообщение от Avazart Посмотреть сообщение
Чет не догоняю что изменит смена на поиск в ширину ?
за один обход по графу назначим каждой вершине уровень
Avazart
 Аватар для Avazart
6904 / 5144 / 253
Регистрация: 10.12.2010
Сообщений: 22,621
Записей в блоге: 17
24.02.2013, 23:59  [ТС]     Визуализация графа (реализация алгоритма) #6
Цитата Сообщение от Jupiter Посмотреть сообщение
за один обход по графу назначим каждой вершине уровень
Как за один обход можно посетить все вершины если у меня несколько "входных" вершин 0,1,7 и 10 которые не связаны с друг другом.
Jupiter
Каратель
Эксперт C++
6543 / 3963 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
25.02.2013, 00:05     Визуализация графа (реализация алгоритма) #7
Цитата Сообщение от Avazart Посмотреть сообщение
Как за один обход можно посетить все вершины если у меня несколько "входных" вершин 0,1,7 и 10 которые не связаны с друг другом.
тогда чему удивлятся что твоя программы выдала эти же вершины на 1-м уровне?
значит graphViz учитывает ратояние между 2-мя вершинами, чтобы оно не привышало 1 уровень, вот он и переместил их на 2-й уровень
Avazart
 Аватар для Avazart
6904 / 5144 / 253
Регистрация: 10.12.2010
Сообщений: 22,621
Записей в блоге: 17
25.02.2013, 00:40  [ТС]     Визуализация графа (реализация алгоритма) #8
Цитата Сообщение от Jupiter Посмотреть сообщение
тогда чему удивлятся что твоя программы выдала эти же вершины на 1-м уровне?
Да это ожидаемо ... вопрос как реализовать так как в graphViz... тут либо этот алгоритм(мой пример) как-то переделывать либо корректировать следующим шагом ...

Добавлено через 29 минут
К стати вот еще источник http://rain.ifmo.ru/cat/view.php/the...arization-2007
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.02.2013, 01:20     Визуализация графа (реализация алгоритма)
Еще ссылки по теме:

C++ Реализация LCS алгоритма на с++
Реализация алгоритма RLE C++
C++ Реализация алгоритма

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Avazart
 Аватар для Avazart
6904 / 5144 / 253
Регистрация: 10.12.2010
Сообщений: 22,621
Записей в блоге: 17
27.02.2013, 01:20  [ТС]     Визуализация графа (реализация алгоритма) #9
Пришел к тому что нужно формировать еще и контейнер со входящими ребрами
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
//---------------------------------------------------------------------------
using namespace std;
//---------------------------------------------------------------------------
struct vertex
{
    string name;
    int level;
    bool used;
    vertex(string _name):name(_name),level(0),used(false){}
};
//---------------------------------------------------------------------------
struct edge
{
     vector<int> out;   //  Исходящие ребра
     vector<int> in;    //  Входящие ребра
};
//---------------------------------------------------------------------------
void add_adge(int from,int to, vector<edge>& edges)
{
    edges[from].out.push_back(to);
    edges[to].in.push_back(from);
}
//---------------------------------------------------------------------------
void dfs( vector<vertex>& v, vector<edge>& e, int index ,int start_level=1)
{
    if(! v[index].used)
     {
         v[index].used= true;
         v[index].level= start_level;
 
         for(size_t d=0; d< e[index].out.size(); d++) //  движемся вниз по графу
                dfs(v,e,e[index].out[d],start_level+1) ;
 
         for(size_t u=0; u< e[index].in.size(); u++)  //  движемся вверх по графу
                dfs(v,e,e[index].in[u], start_level-1) ;
     }
}
//---------------------------------------------------------------------------
void print( vector<vertex>& v)
{
    for(int level= -5; level< 10; ++level)//Уровни могут быть отрицательными
        {
            cout<<"level#"<<level<<"\t";
            for(size_t i=0; i<v.size(); ++i)
                if(v[i].level== level) cout<<v[i].name<<"\t";
            cout<<endl;
        }
}
//---------------------------------------------------------------------------
int main(int argc, char* argv[])
{
vector<vertex> vertexes;
 
vertexes.push_back(vertex("0."));
vertexes.push_back(vertex("1."));
vertexes.push_back(vertex("2."));
vertexes.push_back(vertex("3."));
vertexes.push_back(vertex("4."));
vertexes.push_back(vertex("5."));
vertexes.push_back(vertex("6."));
vertexes.push_back(vertex("7."));
vertexes.push_back(vertex("8."));
vertexes.push_back(vertex("9."));
vertexes.push_back(vertex("10."));
 
vector<edge> edges(vertexes.size() );
 
add_adge(0,2,edges);
 
add_adge(1,2,edges);
add_adge(1,5,edges);
 
add_adge(2,3,edges);
add_adge(2,4,edges);
 
//add_adge(2,5,edges);   //  Test
 
add_adge(5,6,edges);
 
add_adge(7,8,edges);
add_adge(7,9,edges);
 
add_adge(8,5,edges);
 
add_adge(10,5,edges);
 
 
dfs(vertexes,edges,1);
 
print(vertexes);
 
getchar();
return 0;
}
//---------------------------------------------------------------------------
Вывод:
level#-5
level#-4
level#-3
level#-2
level#-1
level#0 7.
level#1 0. 1. 8. 9. 10.
level#2 2. 5.
level#3 3. 4. 6.
level#4
level#5
level#6
level#7
level#8
level#9
Yandex
Объявления
27.02.2013, 01:20     Визуализация графа (реализация алгоритма)
Ответ Создать тему
Опции темы

Текущее время: 08:56. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru