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

Question

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

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

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

Answer 1

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

Раньше было сложно найти решение с открытым исходным кодом, но когда-то коммерчески лицензированный MSAGL сейчас кажется открытым исходным кодом .

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

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

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

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

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

Answer 2

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

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

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

Answer 3

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

https://github.com/panthernet/GraphX

Answer 4

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

Алгоритмы и их качество можно проверить в бесплатном приложении yEd Graph Editor , однако библиотеки доступны только для коммерческого использования.

Answer 5

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

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);




        }

    }
}

Answer 6

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

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