Альтернатива Graphviz с лучшим автоматическим размещением узлов для больших графиков?

Извините за разочарование. Graphviz мог бы быть лучше во многих отношениях, но на данный момент перспективы для этого не велики, потому что AT&T не поддерживает работу так сильно, как это было в прошлом, и некоторые авторы (такие как я) ушли в поисках других. Работа. Мы ищем людей, которые хотят взять его на себя, так что дайте нам знать.

Мы также впечатлены yFiles .

Также попробуйте Tom Sawyer Software ; у них много инженерных талантов, и они много работали над передовыми методами компоновки и интерактивными инструментами. (Возможно, вам придется потратить $$$, так как бесплатная пробная версия, похоже, прекращена.)

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

Если «большой» означает, возможно, сотни узлов, попробуйте neato -Goverlap=false(чтобы избежать перекрытия текстовых меток узлов) и, возможно -Gmodel=subset, попытайтесь улучшить кластеризацию. (Эти параметры не установлены по умолчанию, потому что при анализе данных, например, в биоинформатике, прямое встраивание MDS дает более точное представление расстояний в базовой сети.)

Если «большой» означает тысячи узлов, возможно, многие тысячи, используйте sfdpвместо neatoснова с -Goverlap=false. (Модель расстояния подмножества недоступна в sfdp, потому что неясно, как обрабатывать ребра переменной длины при объединении ребер в иерархическом решателе.) Хороший пример графа с 1054 узлами можно увидеть здесь .

Для «проблем нехватки места» в случае отключенных компонентов см. также атрибуты pack и packmode. Решения таких проблем не очевидны (по сути, вы пытаетесь оптимально упаковать неправильные формы с дополнительными ограничениями, а иногда и в масштабе того, что люди считают «большим», поэтому необходимы субквадратичные алгоритмы). Для связных графов поэкспериментируйте с -Параметры управления.

Это предложения. Что касается отговорок и объяснений...

То, что кто-то называет «лавинным эффектом», также называют нестабильностью макета по отношению к (незначительным) изменениям во входном графе. Это свойство почти всех программ компоновки пакетных графов и решателей ограничений. Таким образом, вам следует искать интерактивные инструменты, такие как компоновка весеннего встраивания D3, и Тим Двайер проделал большую работу над этим, когда работал в Microsoft, так что, возможно, когда-нибудь их инструментарий Graph Layout (AGL) примет его методы интерактивных ограничений. Просто наблюдение: большинство исследователей и программистов не пытались атаковать масштаб, интерактивность и эстетику одновременно (выберите любые 2 из вышеперечисленных...)

Проблема со стилем также хороша, у нас просто не было времени/энергии, чтобы решить ее, поскольку большинство графиков генерируются автоматически, поэтому вы можете применять стили в каком-либо инструменте предварительной обработки или скрипте. Также необходимо учитывать, что граф представляет собой не просто статическое дерево разбора, но после чтения графа его таблица стилей или атрибуты объектов, к которым были применены стили, могут быть изменены, после чего граф должен быть записан правильно таким образом, чтобы максимально сохранить первоначальную структуру. Не непреодолимые, но это детали, которые необходимо тщательно продумать.

Об ошибках можно сообщать на сайте www.graphviz.org в разделе «Отслеживание ошибок и проблем».

Глобальная трассировка кромок с плавными изгибами — сложная задача. Обратите внимание, что во многих классно выглядящих макетах некоторых других инструментов используются изогнутые края, но они просто рисуют поверх всего, что мешает. Думаю, мы добавили эту функцию и в graphviz. Также я думаю, что был документ CHI или INFOVIS, показывающий, что такие изогнутые края на самом деле немного сложнее правильно читать, чем прямые линии.

Пересечения - возможна некоторая локальная оптимизация. Не уверен, какой инструмент используется. Легко указать на конкретные примеры, где макеты могли бы быть лучше, но сложнее придумать эффективное решение, при котором «минимальное количество пересечений» на самом деле не ухудшило бы ситуацию в целом.

Обратите внимание, что я напрямую связан с Graphviz.

Я рекомендую программное обеспечение " yEd " - бесплатное приложение для рисования графиков общего назначения, которое очень старается решить проблемы, с которыми вы сталкиваетесь. Насколько мне известно, это программное обеспечение использует лучшие свободно доступные реализации алгоритмов компоновки.

Теперь к более подробному ответу, который больше подходит для StackOverflow, чем для «Рекомендации по программному обеспечению»:

Проблема, которую вы пытаетесь решить, является действительно сложной задачей (особенно в смысле вычислительной сложности ), поэтому маловероятно, что вы найдете инструмент, который одинаково хорошо решит все ваши проблемы. Существует ряд бесплатных решений (GraphViz, вероятно, является одним из лучших) и довольно много коммерческих конкурентов. Для коммерческой библиотеки рисования графиков yFiles доступно бесплатное (как в пиве) кроссплатформенное приложение, которое вы можете попробовать. Он может импортировать данные из нескольких различных форматов, применять сопоставления стилей к вашим данным и предлагает огромную коллекцию различных алгоритмов компоновки. Он называется yEd и может быть запущен без установки в веб-версии отсюда .. Настольную версию можно было запустить как java-приложение «webstart» непосредственно из браузера или после установки одной из автономных программ для Windows, Linux и Mac.

Некоторые из алгоритмов компоновки, вероятно, не следует использовать с очень большими графами (десятки тысяч элементов), потому что они будут выполняться очень долго или потребуют слишком много памяти, но в большинстве случаев существует по крайней мере один стиль компоновки, который должны хорошо соответствовать вашим данным. Если вам нужно запрограммировать API, вам нужно будет лицензировать базовую библиотеку (доступную для Java, .net, Javascript), что противоречит вашему «бесплатному» требованию, но это даст вам еще больше контроля над макетом.

Отказ от ответственности : я работаю в компании, которая создает этот (бесплатный) продукт, однако на Stack Exchange я не представляю своего работодателя. Я тратил большую часть своего академического и профессионального времени на программное обеспечение для построения графиков с конца 1990-х годов, и я считаю, что у меня очень глубокие знания о рынке и доступном программном обеспечении (как бесплатном, так и коммерческом). Могут быть доступны и другие инструменты, и я надеюсь, что этот сайт может найти отличные альтернативы — я, конечно, не буду их отрицать.

Чтобы очень конкретно ответить на запрос вопроса, поскольку два других ответа отлично поработали над расширением:

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

Однако определение числа пересечений графа является NP-сложной задачей (Гэри и Джонсон показали , что она NP-полна в 1983 году).

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

Это, безусловно, будет считаться «решением на основе GraphViz», но если вы работаете с GraphViz, вы можете проверить Gephi . Это гораздо более способно, когда дело доходит до обработки больших графиков.

PlantUML — это инструмент с открытым исходным кодом, позволяющий пользователям создавать диаграммы UML из обычного текстового языка. Язык PlantUML является примером специального языка приложений. Он использует программное обеспечение Graphviz для построения диаграмм. Он использовался, чтобы слепые студенты могли работать с UML. PlantUML также помогает слепым инженерам-программистам проектировать и читать диаграммы UML.