Graphviz и Dot и графики с сотнями узлов.

У меня есть несколько графиков, которые я хотел бы визуализировать с 150-750 узлами и примерно в 3 раза большим количеством ребер.

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

dot очень хорошо отображает эти более мелкие графики. Тем не менее, кажется, есть момент, когда все становится очень, очень медленно, или точка просто сбрасывает ядро ​​и говорит «двигайтесь дальше».

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

Любой совет? Как я могу получить их точечный рендеринг или найти другой инструмент, который может создавать ориентированный график? Меня здесь убивает тот же ранг?

Вот пример вывода моего текущего прогона, который длится 20 минут и не показывает никаких признаков завершения.

network simplex:  188 nodes 487 edges maxiter=2147483647 balance=1
network simplex: 188 nodes 487 edges 0 iter 0.00 sec
Maxrank = 561, minrank = 0
mincross: pass 0 iter 0 trying 0 cur_cross 0 best_cross 0
mincross: pass 0 iter 0 trying 0 cur_cross 4084 best_cross 4084
mincross: pass 0 iter 1 trying 0 cur_cross 3308 best_cross 3308
mincross: pass 0 iter 2 trying 0 cur_cross 1552 best_cross 1552
mincross: pass 0 iter 3 trying 0 cur_cross 1409 best_cross 1409
mincross: pass 1 iter 0 trying 0 cur_cross 5183 best_cross 840
mincross: pass 1 iter 1 trying 1 cur_cross 4156 best_cross 840
mincross: pass 1 iter 2 trying 2 cur_cross 2003 best_cross 840
mincross: pass 1 iter 3 trying 3 cur_cross 1780 best_cross 840
mincross: pass 2 iter 0 trying 0 cur_cross 840 best_cross 840
mincross: pass 2 iter 1 trying 1 cur_cross 946 best_cross 840
mincross: pass 2 iter 2 trying 2 cur_cross 922 best_cross 840
mincross: pass 2 iter 3 trying 0 cur_cross 774 best_cross 774
mincross: pass 2 iter 4 trying 0 cur_cross 629 best_cross 629
mincross: pass 2 iter 5 trying 1 cur_cross 759 best_cross 629

...

mincross: pass 2 iter 19 trying 3 cur_cross 567 best_cross 438
mincross: pass 2 iter 20 trying 4 cur_cross 507 best_cross 438
network simplex:  135708 nodes 203040 edges maxiter=2147483647 balance=2  
network simplex: 100 200 300 400 500 600 700 800 900 1000   
network simplex: 1100 1200 1300 1400 1500 1600 1700 1800 1900 2000   
network simplex: 2100 2200 2300 2400 2500 2600 2700 2800 2900 3000   
network simplex: 3100 3200 3300 3400 3500 3600 3700 3800 3900 4000   
network simplex: 4100 4200 4300 4400 4500 4600 4700 4800 4900 5000   
network simplex: 5100 5200 5300 5400 5500 5600 5700 5800 5900 6000

... в настоящее время на уровне 321 200


dot graphviz
person Peter V    schedule 03.11.2015    source источник
comment
Я согласен с тем, что rank = same добавляет ограничения, которые могут помешать dot найти решение. Отображает ли dot тот же график, если rank = same не указан в файле графика? В противном случае вам, возможно, придется отредактировать свой вопрос, включив в него самый маленький файл, который dot не может отобразить, чтобы мы могли изучить его построчно на предмет потенциальных проблем. Конечно, может случиться так, что график слишком сложен для dot или dot не воспринимает общую структуру в графике, которая позволила бы ему произвести хороший рендеринг.   -  person Simon    schedule 04.11.2015
comment
Я экспериментировал с уменьшением количества операторов rank = same, и это, похоже, сильно ускорило процесс. Кажется, что время растет как минимум на n ^ 2 с количеством rank = same операторов. В итоге файл отрисовался; на xeon v3 потребовалось около 20 минут, вылетевший образ cairo: 32k x 25k или около того. Рендерер SVG работал, давая график с некоторыми проблемами. Я буду продолжать экспериментировать и пока оставлю это открытым и сообщу о результатах.   -  person Peter V    schedule 04.11.2015

Ответы (1)


arrow_upward
0
arrow_downward

Чтобы закончить здесь, я бы теперь посоветовал не использовать rank = same даже с графами «от малого до среднего», назовите это более 100 узлами.

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

Как ни странно, похоже, что, вероятно, предстоит провести довольно много оригинальных исследований в области алгоритмов их размещения и распределения, поэтому, если вы аспирант, ищущий диссертацию, это область, которая не получила тонны внимание, по крайней мере, за последние 10 лет.

person Peter V    schedule 21.03.2016