January 9th, 2010

glider

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

Иногда возникает необходимость поработать с графами. Однажды в нежелании писать руками алгоритмы на графах я наткнулся на библиотеку QuickGraph. Все прекрасно и замечательно - несмотря на убогую документацию либа действительно очень полезная и содержит пачку реализованных и протестированных алгоритмов (половину названий которых я вообще никогда не слышал =)).

Есть только одно но. Дебагать что-либо, связанное с графами, прямо в IDE весьма неудобно - открывать в watch список вертексов, находить нужные, снова открывать список ребер, сопоставлять их как-то с вертексами, через минуту забывать картинку графа, и так далее. К счастью, я натолкнулся на возможность Quickgraph по сериализации графов в разные форматы. По рандому выбрал Graphviz и не пожалел.

Линковкой маленькой дополнительной библиотечки QuickGraph.Graphviz программист получает функционал GraphvizAlgorithm, который умеет персистить графы QuickGraph в dot-файлы. Последние представляют собой plain text, описывающий вершины и ребра графа, а также их форматирование. Для просмотра этих файлов нужно скачать тулкит с сайта Graphviz и воспользоваться программкой dot.exe, которая умеет рендерить dot-файлы в несколько графических форматов, включая png. Причем, никакую layout-информацию типо координат вершин указывать не надо - dot.exe все сгенерит сама, пользуясь своими эвристиками (не знаю, как для общего случая, но для моих задач они отработали неплохо).
Copy Source | Copy HTML
var algo = new GraphvizAlgorithm<IBlock, TaggedEdge<IBlock, List<PredicateType?>>>(Blocks);
var name = UnitTest.PersistentId != null ? ("anonymous body, " + UnitTest.PersistentId) : "anynomous body";
algo.FormatVertex += (o, e) => e.VertexFormatter.Label = e.Vertex.ToString();
algo.FormatEdge += (o, e) => e.EdgeFormatter.Label = new GraphvizEdgeLabel{Value =
    e.Edge.Tag.Where(p => p != null).Select(p => p.Value.ToSymbol()).StringJoin()};
 
var dotPath = @"d:\hirgraph\" + name + ".dot";
algo.Generate(new FileDotEngine(), dotPath);
 
var dotExePath = @"c:\Program Files\Graphviz2.26\bin\dot.exe";
if (File.Exists(dotExePath))
{
    var psi = new ProcessStartInfo(dotExePath);
    psi.Arguments = String.Format(
        "-Tpng -o \"{0}\" \"{1}\"",
        Path.ChangeExtension(dotPath, "png"),
        dotPath);
    psi.UseShellExecute = false;
    psi.RedirectStandardOutput = true;
    psi.CreateNoWindow = true;
 
    var p = Process.Start(psi);
    var stdout = p.StandardOutput.ReadToEnd();
    p.WaitForExit();
 
    if (stdout.IsNeitherNullNorEmpty())
    {
        Log.TraceLine(stdout);
    }
}
Все получилось в шоколаде - пару взглядов на картинки графов мне помогли устранить стремные баги, которые отладить не получалось.

Осталось только упомянуть один косяк: QuickGraph.Graphviz не умеет работать с многострочными лейблами для вертексов - сгенеренный dot-файл оказывается невалидным. Пришлось чекаутнуть исходники (ура опен-сорсу) и сделать приватный билд с хаком. Это заняло 15 минут на разбирательства с форматом и еще 15 минут на реализацию заплатки. В паблик я патч не сабмиттил, ибо надо бы написать юнит-тесты. Кому интересно - спрашивайте, расскажу что делать.