Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 56, средняя оценка - 4.98
Avazart
Эксперт С++
7247 / 5419 / 297
Регистрация: 10.12.2010
Сообщений: 24,044
Записей в блоге: 17
#1

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

10.02.2013, 19:55. Просмотров 8537. Ответов 38
Метки нет (Все метки)

В общем есть такой пакет http://ru.wikipedia.org/wiki/Graphviz

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

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

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

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

Возможно кто-то имел дело с этой библиотекой и знает как её использовать?
2
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.02.2013, 19:55
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Визуализация графов (C++):

Теорие графов. Композиция двух неор. графов. - C++
Здравствуйте. Прошу помощи уже здесь :| (old topic)... Прошу помочь с составлением алгоритма "Композиции двух неориентированных графов". ...

Реализация графов - C++
Помогите пожалуйста!!!!! как написать программу на Си ++ на эту тему :реализация различных типов графов и операций над ними. спасибо...

Программирование графов - C++
Неподскажите сайт где очень понятно объясняют графы, как запрограммировать, и т.д. Просто гуглил но чо то мне не понравилось то, что он...

Представление графов С++ - C++
#include <iostream> #include <vector> using namespace std; int n; int m; vector<int> *adj; vector<bool>...

Теория графов - C++
Есть задание. найти максимальное и среднее расстояние между центральными вершинами неориентированного графа. 1 Что такое центральные...

Представление графов С++ - C++
Считывания графу из входного файла. На вход подается текстовый файл следующего вида: n m v1 u1 v2 u2 .... vm um

38
iama
1250 / 975 / 49
Регистрация: 30.07.2010
Сообщений: 5,297
12.02.2013, 23:48 #2
Цитата Сообщение от Avazart Посмотреть сообщение
вершины графа располагаются оптимальным образом
Странное и сомнительное утверждение.

Мне кажется, что проще было бы нужный функционал реализовать самостоятельно, тем более, ничего красивого или сверхъестественного я там не заметил.
0
Avazart
Эксперт С++
7247 / 5419 / 297
Регистрация: 10.12.2010
Сообщений: 24,044
Записей в блоге: 17
12.02.2013, 23:56  [ТС] #3
Цитата Сообщение от iama Посмотреть сообщение
Мне кажется, что проще было бы нужный функционал реализовать самостоятельно
Оптимальным для отображения, с минимум пересечений... хотя да когда узлов много не справляется...

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

Если есть идее готов выслушать...
0
iama
1250 / 975 / 49
Регистрация: 30.07.2010
Сообщений: 5,297
12.02.2013, 23:57 #4
Avazart, для начала определите понятие "оптимальное отображение графа", его можно трактовать по-разному.
0
Avazart
Эксперт С++
7247 / 5419 / 297
Регистрация: 10.12.2010
Сообщений: 24,044
Записей в блоге: 17
13.02.2013, 00:14  [ТС] #5
Ну...
Цитата Сообщение от Avazart Посмотреть сообщение
минимум пересечений
Добавлено через 1 минуту
Программа «dot» сама распознаёт все связи графа и упорядочивает его таким образом, чтобы было наименьшее количество пересечений.
http://ru.wikipedia.org/wiki/Graphviz

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

Более того редактор читает данные из дот файла который может содержать избыточную информацию т.е почти сыром виде что удобно
A -> B
A -> C
итд
0
iama
1250 / 975 / 49
Регистрация: 30.07.2010
Сообщений: 5,297
13.02.2013, 00:18 #6
Avazart, вы сами понимаете, это не определение. Просто чтобы смотрелось нормально?
0
Avazart
Эксперт С++
7247 / 5419 / 297
Регистрация: 10.12.2010
Сообщений: 24,044
Записей в блоге: 17
13.02.2013, 00:50  [ТС] #7
Цитата Сообщение от iama Посмотреть сообщение
Avazart, вы сами понимаете, это не определение. Просто чтобы смотрелось нормально?
По моему минимально пересечение ребер это достаточно конкретно как для задания...

Как это реализовать это другой вопрос... как организовать раздачу координат
Цитата Сообщение от iama Посмотреть сообщение
чтобы смотрелось нормально?
0
iama
1250 / 975 / 49
Регистрация: 30.07.2010
Сообщений: 5,297
13.02.2013, 01:01 #8
Avazart, простая жадная реализация будет совсем не плоха. Жадность по степени вершины, сначала берете вершины с наибольшей степенью, располагаете их вокруг (0; 0) как вершины правильного многоугольника, для каждой вершины будем поддерживать подмножество [0; 2pi) как угол, в котором можно располагать вершины, инцидентые данной, потом запускаем рекурсивно (или с помощью очереди) алгоритм для всех смежных, уже расположеных.
0
Avazart
Эксперт С++
7247 / 5419 / 297
Регистрация: 10.12.2010
Сообщений: 24,044
Записей в блоге: 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
0
iama
1250 / 975 / 49
Регистрация: 30.07.2010
Сообщений: 5,297
13.02.2013, 09:42 #10
Цитата Сообщение от Avazart Посмотреть сообщение
Но такой вопрос как я понял возле центра мы распологаем по кругу вершины "первым слоем" , но чем определяется их количество ?
Я бы просто сделал какую-то эвристическую функцию от остаточного графа. Идея такая — если граф плотный, будем брать просто какую-то фиксированную часть от оставшихся вершин (хоть в процентах, для жадной реализации это результат сильно не ухудшит), и будем разбрасывать их; для разреженных — берем кучками, которые сильно отличаются друг от друга по весу (вес множества вершин определим как сумму их степеней), и располагаем каждый раз по кучке.

Понятно, что это только эвристика, и есть графы, изображение на которых будет не слишком красивым, но написав такое вы много для себя поймете, и следущая эвристика будет намного лучше.
0
Avazart
Эксперт С++
7247 / 5419 / 297
Регистрация: 10.12.2010
Сообщений: 24,044
Записей в блоге: 17
13.02.2013, 14:00  [ТС] #11
Вопрос не в обучение чему-то а в использовании то что уже работает и нормально работает.
Писание велосипеда подобным образом займет куча времени ибо дофига придется "пробовать"
0
iama
1250 / 975 / 49
Регистрация: 30.07.2010
Сообщений: 5,297
13.02.2013, 23:42 #12
Avazart, ну уж извините, я таких способов работы не использую, не понимаю и не приемлю.
0
Avazart
Эксперт С++
7247 / 5419 / 297
Регистрация: 10.12.2010
Сообщений: 24,044
Записей в блоге: 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.с из доки легко скомпилировался и работал..
0
alex_x_x
бжни
2450 / 1655 / 84
Регистрация: 14.05.2009
Сообщений: 7,162
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 -
2
Avazart
Эксперт С++
7247 / 5419 / 297
Регистрация: 10.12.2010
Сообщений: 24,044
Записей в блоге: 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
0
17.02.2013, 03:30
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.02.2013, 03:30
Привет! Вот еще темы с ответами:

Визуализация - C++
Добрый день, подскажите пожалуйста, чем лучше отображать 2d графику - хочу поиграться с алгоритмами генерирования карт и хочется видеть...

Визуализация - C++
Здравствуйте, уважаемые форумчане. Хотелось бы узнать, возможно ли визуализировать(создать несколько членов, которые будут отвечать за...

Методы обхода графов - C++
Всем привет! Есть задание : Обойти граф, используя заданный алгоритм ( Обход в глубину по матрице инцидентности ). Все что касается...

Генерирование особых графов - C++
кто может привести какой-либо тест(пример в текстовом файле) или алгоритм генерирования тестов для создания произвольного графа с...


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

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru