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

Визуализация графов - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 56, средняя оценка - 4.98
Avazart
 Аватар для Avazart
6897 / 5137 / 252
Регистрация: 10.12.2010
Сообщений: 22,570
Записей в блоге: 17
10.02.2013, 19:55     Визуализация графов #1
В общем есть такой пакет http://ru.wikipedia.org/wiki/Graphviz

С помощью него можно вводить граф ввиде dot файла и получать её визуализацию
( вершины графа располагаются оптимальным образом )

Описание утилит на русском тут http://rus-linux.net/nlib.php?name=/...-ru-10-16.html

Оф. сайт http://www.graphviz.org/ Тут же можно скачать и установить, причем как пакет с утилитами и dll -ками, инклюдами так и сами соры.

Сама библиотека написана на Си. Никак не могу понять как использовать эту либу в своих программах.
Пытаюсь скомпилить примеры из доки но без успешно то ли программа завершается крахом то ли требует несуществующие dll.

Возможно кто-то имел дело с этой библиотекой и знает как её использовать?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.02.2013, 19:55     Визуализация графов
Посмотрите здесь:

Реализация графов C++
генерирование особых графов C++
Теорие графов. Композиция двух неор. графов. C++
C++ Визуализация
Программирование графов C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
iama
 Аватар для iama
1249 / 974 / 48
Регистрация: 30.07.2010
Сообщений: 5,297
12.02.2013, 23:48     Визуализация графов #2
Цитата Сообщение от Avazart Посмотреть сообщение
вершины графа располагаются оптимальным образом
Странное и сомнительное утверждение.

Мне кажется, что проще было бы нужный функционал реализовать самостоятельно, тем более, ничего красивого или сверхъестественного я там не заметил.
Avazart
 Аватар для Avazart
6897 / 5137 / 252
Регистрация: 10.12.2010
Сообщений: 22,570
Записей в блоге: 17
12.02.2013, 23:56  [ТС]     Визуализация графов #3
Цитата Сообщение от iama Посмотреть сообщение
Мне кажется, что проще было бы нужный функционал реализовать самостоятельно
Оптимальным для отображения, с минимум пересечений... хотя да когда узлов много не справляется...

Честно говоря я понятия не имею как реализовать отображение графов так как это делает это пакет...
подобных алгоритмов я раньше не встречал, что бы их реализовать самому...

Если есть идее готов выслушать...
iama
 Аватар для iama
1249 / 974 / 48
Регистрация: 30.07.2010
Сообщений: 5,297
12.02.2013, 23:57     Визуализация графов #4
Avazart, для начала определите понятие "оптимальное отображение графа", его можно трактовать по-разному.
Avazart
 Аватар для Avazart
6897 / 5137 / 252
Регистрация: 10.12.2010
Сообщений: 22,570
Записей в блоге: 17
13.02.2013, 00:14  [ТС]     Визуализация графов #5
Ну...
Цитата Сообщение от Avazart Посмотреть сообщение
минимум пересечений
Добавлено через 1 минуту
Программа «dot» сама распознаёт все связи графа и упорядочивает его таким образом, чтобы было наименьшее количество пересечений.
http://ru.wikipedia.org/wiki/Graphviz

Добавлено через 1 минуту
Связи - ребра могут изгибаться если надо ...

Более того редактор читает данные из дот файла который может содержать избыточную информацию т.е почти сыром виде что удобно
A -> B
A -> C
итд
iama
 Аватар для iama
1249 / 974 / 48
Регистрация: 30.07.2010
Сообщений: 5,297
13.02.2013, 00:18     Визуализация графов #6
Avazart, вы сами понимаете, это не определение. Просто чтобы смотрелось нормально?
Avazart
 Аватар для Avazart
6897 / 5137 / 252
Регистрация: 10.12.2010
Сообщений: 22,570
Записей в блоге: 17
13.02.2013, 00:50  [ТС]     Визуализация графов #7
Цитата Сообщение от iama Посмотреть сообщение
Avazart, вы сами понимаете, это не определение. Просто чтобы смотрелось нормально?
По моему минимально пересечение ребер это достаточно конкретно как для задания...

Как это реализовать это другой вопрос... как организовать раздачу координат
Цитата Сообщение от iama Посмотреть сообщение
чтобы смотрелось нормально?
iama
 Аватар для iama
1249 / 974 / 48
Регистрация: 30.07.2010
Сообщений: 5,297
13.02.2013, 01:01     Визуализация графов #8
Avazart, простая жадная реализация будет совсем не плоха. Жадность по степени вершины, сначала берете вершины с наибольшей степенью, располагаете их вокруг (0; 0) как вершины правильного многоугольника, для каждой вершины будем поддерживать подмножество [0; 2pi) как угол, в котором можно располагать вершины, инцидентые данной, потом запускаем рекурсивно (или с помощью очереди) алгоритм для всех смежных, уже расположеных.
Avazart
 Аватар для Avazart
6897 / 5137 / 252
Регистрация: 10.12.2010
Сообщений: 22,570
Записей в блоге: 17
13.02.2013, 02:13  [ТС]     Визуализация графов #9
Хорошо мне такое приходило на ум что от этого стоит плясать.

Но такой вопрос как я понял возле центра мы распологаем по кругу вершины "первым слоем" , но чем определяется их количество ?

Добавлено через 53 минуты
Ну вот к примеру http://alenacpp.blogspot.com/2006/03/blog-post_23.html что говорит что не все так просто... опять же сводит к готовым решениям.

Добавлено через 10 минут
Да и действительно критериев оказывается довольно много http://ru.wikipedia.org/wiki/%D0%92%...84%D0%BE%D0%B2
iama
 Аватар для iama
1249 / 974 / 48
Регистрация: 30.07.2010
Сообщений: 5,297
13.02.2013, 09:42     Визуализация графов #10
Цитата Сообщение от Avazart Посмотреть сообщение
Но такой вопрос как я понял возле центра мы распологаем по кругу вершины "первым слоем" , но чем определяется их количество ?
Я бы просто сделал какую-то эвристическую функцию от остаточного графа. Идея такая — если граф плотный, будем брать просто какую-то фиксированную часть от оставшихся вершин (хоть в процентах, для жадной реализации это результат сильно не ухудшит), и будем разбрасывать их; для разреженных — берем кучками, которые сильно отличаются друг от друга по весу (вес множества вершин определим как сумму их степеней), и располагаем каждый раз по кучке.

Понятно, что это только эвристика, и есть графы, изображение на которых будет не слишком красивым, но написав такое вы много для себя поймете, и следущая эвристика будет намного лучше.
Avazart
 Аватар для Avazart
6897 / 5137 / 252
Регистрация: 10.12.2010
Сообщений: 22,570
Записей в блоге: 17
13.02.2013, 14:00  [ТС]     Визуализация графов #11
Вопрос не в обучение чему-то а в использовании то что уже работает и нормально работает.
Писание велосипеда подобным образом займет куча времени ибо дофига придется "пробовать"
iama
 Аватар для iama
1249 / 974 / 48
Регистрация: 30.07.2010
Сообщений: 5,297
13.02.2013, 23:42     Визуализация графов #12
Avazart, ну уж извините, я таких способов работы не использую, не понимаю и не приемлю.
Avazart
 Аватар для Avazart
6897 / 5137 / 252
Регистрация: 10.12.2010
Сообщений: 22,570
Записей в блоге: 17
17.02.2013, 03:19  [ТС]     Визуализация графов #13
Цитата Сообщение от iama Посмотреть сообщение
Avazart, ну уж извините, я таких способов работы не использую, не понимаю и не приемлю.
Как вы думаете сколько человеко-часов потрачено на написание данной библиотеки ?
А на тестирование и обкатку?
Я уже не говорю о теоретических знаниях.

Проблема в том что библиотеку неудается прикрутить и/или я не могу понять как её правильно использовать.

Добавлено через 14 минут
Сдесь находится документация http://graphviz.org/doc/libguide/libguide.pdf

В ней описана общая схема работы с библиотекой
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
Agraph_t* G;
GVC_t* gvc;
gvc = gvContext();
 
 /*  G = createGraph (); операции по созданию графа */
 
gvLayout (gvc, G, "dot");
 
/* drawGraph (G);   операции по рисованию графа */
 
gvFreeLayout(gvc, g);
agclose (G);
gvFreeContext(gvc);
Согласно описанию создать граф можно
C++
1
Agraph_t* G = agopen("network", AGDIGRAPH);
И это удается сделать, но при добавлении вершин
C++
1
Agnode_t *agnode(Agraph_t*, char*);
Эта ф-ция возвращает NULL в место нода и тут приехали ...

Попытки загрузить граф другими ф-циями agread(), agmemread() приводили к ошибкам памяти.

Добавлено через 10 минут
Пытался вызвать aginit() так как думал что проблема в ней ( но вроде как её не нужно вызывать если используешь
gvContext(); ), но у меня не удалось это сделать...

Установил библиотеку на Ubuntu пример simple.с из доки легко скомпилировался и работал..
alex_x_x
бжни
 Аватар для alex_x_x
2441 / 1646 / 84
Регистрация: 14.05.2009
Сообщений: 7,163
17.02.2013, 03:27     Визуализация графов #14
Цитата Сообщение от iama Посмотреть сообщение
Странное и сомнительное утверждение.
Мне кажется, что проще было бы нужный функционал реализовать самостоятельно, тем более, ничего красивого или сверхъестественного я там не заметил.
не мог не оставить это тут
Bash
1
lsmod | perl -e 'print "digraph \"lsmod\" {";<>;while(<>){@_=split/\s+/; print "\"$_[0]\" -> \"$_\"\n" for split/,/,$_[3]}print "}"' | dot -Tpng | display -
Avazart
 Аватар для Avazart
6897 / 5137 / 252
Регистрация: 10.12.2010
Сообщений: 22,570
Записей в блоге: 17
17.02.2013, 03:30  [ТС]     Визуализация графов #15
alex_x_x, Че за скрипт ?

Пример simple.с

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <graphviz/gvc.h>
 
int main(int argc, char **argv)
{
  GVC_t *gvc;
  graph_t *g;
  FILE *fp;
  gvc = gvContext();
  if (argc > 1)
      fp = fopen(argv[1], "r");
  else
      fp = stdin;
 
  g = agread(fp);
  gvLayout(gvc, g, "dot"); 
  gvRender(gvc, g, "plain", stdout);
  gvFreeLayout(gvc, g);
  agclose(g);
 
return (gvFreeContext(gvc));
}
Bash
1
gcc simple.c -o prog -lgvc -lgraph -lcdt
alex_x_x
17.02.2013, 03:40
  #16

Не по теме:

Avazart, показывает граф с зависимостями между модулями ядра линукс
я использовал непосредственно dot, для отображения зависимостей между модулями в проекте, но в нативном коде честно говоря никогда не использовал

Avazart
 Аватар для Avazart
6897 / 5137 / 252
Регистрация: 10.12.2010
Сообщений: 22,570
Записей в блоге: 17
17.02.2013, 05:21  [ТС]     Визуализация графов #17
Цитата Сообщение от alex_x_x Посмотреть сообщение
я использовал непосредственно dot
Ну да можно так, но как к примеру сделать свой редактор, что бы пользователь мог "двигать" узлы, а не имел просто статическую картинку?

Добавлено через 1 час 25 минут
Смотрю пример demo.c
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
#include <graphviz/gvc.h>
int main(int argc, char **argv)
{
  Agraph_t *g;
  Agnode_t *n, *m;
  Agedge_t *e;
  Agsym_t *a;
  GVC_t *gvc;
  /* set up a graphviz context */
  gvc = gvContext();
  /* parse command line args - minimally argv[0] sets layout engine */
  gvParseArgs(gvc, argc, argv);
  /* Create a simple digraph */
  g = agopen("g", AGDIGRAPH);
  n = agnode(g, "n");
  m = agnode(g, "m");
  e = agedge(g, n, m);
   /* Set an attribute - in this case one that affects the visible     rendering */
  agsafeset(n, "color", "red", "");
  /* Compute a layout using layout engine from command line args */
  gvLayoutJobs(gvc, g);
  /* Write the graph according to -T and -o options */
  gvRenderJobs(gvc, g);
  /* Free layout data */
  gvFreeLayout(gvc, g);
 
  /* Free graph structures */
  agclose(g);
  /* close output file, free context, and return number of errors */
return (gvFreeContext(gvc));
}
И никак не могу вьехать какие параметры надо передавать в командную строку

Пытаю так:
Bash
1
./prog dot Tpng -otest.png
Получаю
There is no layout engine support for "prog"
Use one of: circo dot fdp neato nop nop1 nop2 osage patchwork sfdp twopi
В место передачи консольных параметров подставляю пример из доки
C++
1
2
3
4
5
6
7
8
char* args[] = {
"dot",
"-Tgif",
/* gif output */
"-oabc.gif"
/* output to file abc.gif */
};
gvParseArgs (gvc, sizeof(args)/sizeof(char*), args);
Получаю дамп памяти...

Добавлено через 9 минут
И походу связано это с количеством аргументов... если написать
C++
1
gvParseArgs (gvc,2, args);
То в терминале вижу кракозябы - вывело в двоичном файл изображения . Т.е. есть без дампа, но третий параметр не передался и файла изображения в папке не появилось.
alex_x_x
бжни
 Аватар для alex_x_x
2441 / 1646 / 84
Регистрация: 14.05.2009
Сообщений: 7,163
17.02.2013, 05:43     Визуализация графов #18
Avazart, я знаю енто только на уровне dot
те например так

Bash
1
printf 'digraph "name" { \n "A" -> "B" \n "B" -> "C" \n "C" -> "A" \n }' | dot -Tpng | display -
видимо она это и ест
Цитата Сообщение от Avazart Посмотреть сообщение
Ну да можно так, но как к примеру сделать свой редактор, что бы пользователь мог "двигать" узлы, а не имел просто статическую картинку?
не знаю, не уверен, что это возможно
Avazart
 Аватар для Avazart
6897 / 5137 / 252
Регистрация: 10.12.2010
Сообщений: 22,570
Записей в блоге: 17
17.02.2013, 17:51  [ТС]     Визуализация графов #19
Вроде ошибка из-за ф-ций:
C++
1
2
3
4
/* Compute a layout using layout engine from command line args */
  gvLayoutJobs(gvc, g);
  /* Write the graph according to -T and -o options */
  gvRenderJobs(gvc, g);
http://en.usenet.digipedia.org/thread/16985/352/

А если нужно сохранять в файл то так работает :
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
#include <graphviz/gvc.h>
 
int main(int argc, char **argv)
{
    GVC_t *gvc;
    graph_t *g; 
    FILE *fp;
    gvc = gvContext();
 
    /* Загрузка графа с файла */ 
    //if (argc > 1)
    //    fp = fopen(argv[1], "r");
    //else
    //    fp = stdin;
    //g = agread(fp); 
 
    /* Создание графа вручную */
    Agnode_t *n, *m;
    Agedge_t *e;
     
    g = agopen("g", AGDIGRAPH);
    n = agnode(g, "n");
    m = agnode(g, "m");
    e = agedge(g, n, m);
      
     /* *** */
   
    gvLayout(gvc, g, "dot");
    gvRenderFilename(gvc, g, "png", "test.png");
    gvFreeLayout(gvc, g); 
    agclose(g);
 
return (gvFreeContext(gvc));
}
Добавлено через 1 минуту
Остается понять какого в Винде работать не хочет....

Добавлено через 11 часов 30 минут
В общем код приведенный выше пытаюсь скомпилить под Windows в VC++:

1. В доке написано что нужно линковать с gvc, graph, cdt но дело в том что если линковать с graph.lib
то начинает требовать graph.dll а её в папках пакета GraphViz нет...
- Пробую линковать с cgraph.lib

C++
1
2
3
#pragma comment(lib,"gvc.lib")
#pragma comment(lib,"cdt.lib")
#pragma comment(lib,"cgraph.lib")
2. Приложение запускается и в консоли вижу:
Error: Layout type: "dot" not recognized. Use one of:
Error: renderer for png is unavailable
Оказывается рядом exe-ником должен лежать файл config6

3. Все запустилось, работает и файл изображения png появился, но вот только он пустой - маленький белый квадратик, графа на нем нет.

Добавлено через 7 минут
4. Проверяю :
C++
1
2
    g = agopen("g", AGDIGRAPH);
    n = agnode(g, "n"); // почему  n=NULL ???
Оказывается после второй строчки n == NULL, а значит вершина графа не добавилась - вот почему граф пустой.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.02.2013, 21:10     Визуализация графов
Еще ссылки по теме:

Теория графов C++
Визуализация C++
C++ Для любителей графов

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

Или воспользуйтесь поиском по форуму:
Avazart
 Аватар для Avazart
6897 / 5137 / 252
Регистрация: 10.12.2010
Сообщений: 22,570
Записей в блоге: 17
18.02.2013, 21:10  [ТС]     Визуализация графов #20
5. Это так в дебаге выдает NULL, а в релизе - ошибка памяти
Необработанное исключение в "0x100053f6" в "test.exe": 0xC0000005: Нарушение прав доступа при чтении "0x2808a487".
с указанием на строчку
C++
1
 g = agopen("g", AGDIGRAPH);
6. Думал проблема lib файлах, решил попробовать грузить dll явно, но та же ошибка...
Посмотрел что импортирует dot.exe - gvc.dll и cgraph.dll идр импортирует ф-ции с теми же именами что и я в том числе agopen()

Задается вопрос как он это делает ?
Yandex
Объявления
18.02.2013, 21:10     Визуализация графов
Ответ Создать тему
Опции темы

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