Оптимизация макета графа в C#

Question

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

Я читал Graphviz, QuickGraph и Graph#, но часть визуализации мне не нужна — у меня уже есть приложение, которое будет отображать узлы с учетом координат x/y.Мне сказали, что и алгоритм Сугиямы, и семейство алгоритмов, основанных на силе, имеют тенденцию выводить приятные графики, но я не могу найти библиотеку .NET, которая будет выводить координаты вместо изображения без какого-либо довольно серьезного исходного кода. взлом.

Может ли кто-нибудь порекомендовать библиотеки, алгоритмы и т.п.?

Answer 1

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

Раньше было сложно найти решение с открытым исходным кодом, но однажды получившая коммерческую лицензию МСАГЛ сейчас вроде с открытым исходным кодом.

Различие между График# и QuickGraph заключается в том, что последний предоставляет примитивы обхода графа и манипулирования, но не предоставляет никаких алгоритмов компоновки.В Graph# есть весь доступный исходный код, и, судя по тому, что я (кратко) рассмотрел, он имеет четкое разделение между механизмом компоновки и реализацией рисования.

Графвиз написан на чистом C/C++ и является довольно монолитным, принимает в качестве входных данных текстовый файл, описывающий график, и выдает различные типы выходных данных, как векторных, так и растровых.Он не очень хорошо подходит в качестве подключаемого механизма компоновки, но его можно использовать, выделив и предоставив необходимый входной файл и проанализировав выходные данные.Хотя это не очень чистое решение.

Еще есть что-то под названием ОГДФ.Хотя он полностью написан на C++, он был разработан для использования в качестве библиотеки механизма компоновки и имеет для этого хорошо структурированный интерфейс.Он поддерживает различные алгоритмы макета, включая оптимизированный Сугияма, если вас это интересует.

Если вы заинтересованы во внедрении оптимизированного варианта Сугиямы, вы всегда можете создать свой собственный, используя подробное описание алгоритма :)

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

Answer 2

Microsoft Research имеет автоматизированный механизм построения графиков, который может помочь вам в этом.

Подробнее об этом можно прочитать здесь:

http://research.microsoft.com/en-us/downloads/f1303e46-965f-401a-87c3-34e1331d32c5/

Answer 3

yFiles имеет очень сложные реализации алгоритмов компоновки как принудительного (так называемого «органического»), так и основанного на Сугияме («иерархического»).Они предлагают реализации без просмотра для Java, .net, Silverlight, Flex и Javascript.API для получения координат доступен онлайн. здесь.

Алгоритмы и их качество можно протестировать в бесплатном режиме. редактор графиков yEd Однако библиотеки доступны только коммерчески.

Answer 4

На всякий случай кто-то столкнется с подобной проблемой.Существует проект GraphX ​​для .NET с открытым исходным кодом, который включает в себя множество алгоритмов компоновки, отделенных от механизма визуализации.Таким образом, вы можете просто взять библиотеку логики, выполнить вычисления и получить пакет координат для использования в вашем собственном инструменте визуализации.

https://github.com/panthernet/GraphX

Answer 5

существует реализация макета Сугияма на Java как часть системы modsl, лицензия Apache.источник здесь.

мне удалось достаточно легко преобразовать его в смешанный Реализация Objective-C/Objective-C++ на основе диграфа.

Answer 6

Я получил координаты узлов таким образом

namespace GleeTest
{
    class GleeTest
    {

        static void Main() {
            Microsoft.Glee.GleeGraph oGleeGraph = new Microsoft.Glee.GleeGraph();

            Microsoft.Glee.Splines.ICurve oCurve =
               Microsoft.Glee.Splines.CurveFactory.CreateEllipse(
                   1, 1,
                   new Microsoft.Glee.Splines.Point(0, 0)
                   );
            Microsoft.Glee.Node strNode1 = new Microsoft.Glee.Node("Circle", oCurve);

            Microsoft.Glee.Node strNode3 = new Microsoft.Glee.Node("Diamond", oCurve);
            Microsoft.Glee.Node strNode4 = new Microsoft.Glee.Node("Standard", oCurve);
            Microsoft.Glee.Node strNode2 = new Microsoft.Glee.Node("Home", oCurve);

            oGleeGraph.AddNode(strNode1);
            oGleeGraph.AddNode(strNode2);
            oGleeGraph.AddNode(strNode3);
            oGleeGraph.AddNode(strNode4);

            Microsoft.Glee.Edge oGleeEdge1 =
               new Microsoft.Glee.Edge(strNode1, strNode2);
            Microsoft.Glee.Edge oGleeEdge2 =
            new Microsoft.Glee.Edge(strNode2, strNode1);
            Microsoft.Glee.Edge oGleeEdge3 =
            new Microsoft.Glee.Edge(strNode2, strNode2);
            Microsoft.Glee.Edge oGleeEdge4 =
            new Microsoft.Glee.Edge(strNode1, strNode3);
            Microsoft.Glee.Edge oGleeEdge5 =
            new Microsoft.Glee.Edge(strNode1, strNode4);
            Microsoft.Glee.Edge oGleeEdge6 =
          new Microsoft.Glee.Edge(strNode4, strNode1);


            oGleeGraph.AddEdge(oGleeEdge1);
            oGleeGraph.AddEdge(oGleeEdge2);
            oGleeGraph.AddEdge(oGleeEdge3);
            oGleeGraph.AddEdge(oGleeEdge4);
            oGleeGraph.AddEdge(oGleeEdge5);
            oGleeGraph.AddEdge(oGleeEdge6);

            oGleeGraph.CalculateLayout();


            System.Console.WriteLine("Circle position  " + oGleeGraph.FindNode("Circle").Center.X + "," + oGleeGraph.FindNode("Circle").Center.Y);
            System.Console.WriteLine("Home position = " + oGleeGraph.FindNode("Home").Center.X + "," + oGleeGraph.FindNode("Home").Center.Y);
            System.Console.WriteLine("Diamond position = " + oGleeGraph.FindNode("Diamond").Center.X + "," + oGleeGraph.FindNode("Diamond").Center.Y);
            System.Console.WriteLine("Standard position = " + oGleeGraph.FindNode("Standard").Center.X + "," + oGleeGraph.FindNode("Standard").Center.Y);




        }

    }
}