В своей работе мне было необходимо визуализировать графы (directed graphs), в частности, для построения графа взаимосвязей между сайтами. Не могу сказать, что это было легко. Было использовано несколько подходов и инструментов, и добиться 100% сатисфакции не удалось, но все же задача была более менее решена. Хочу сделать анализ инструментов и подходов, которые доступны в данный момент для работы с графами в вебе.

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

Graphviz - Graph Visualization Software

Graphviz — разработанный специалистами лаборатории AT&T пакет утилит по автоматической визуализации графов, заданных в виде описания на языке «dot». Пакет распространяется с открытыми исходными файлами по лицензии CPL (Common Public License) и работает на многих операционных системах, включая GNU/Linux, Mac OS, Unix-подобные, Microsoft Windows.

Википедия

Если говорить о графах, начинать необходимо, конечно с Graphviz, возле которого удобно разместились и другие инструменты. В пакет утилит входит программа «dot», автоматический визуализатор ориентированных графов, который принимает на вход текстовый файл с представлением графа в виде смежных списков, а на выходе формирует граф в виде графического, векторного или текстового файла.

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

digraph G{ 
 Рождение->Юность->Зрелость->Старость->Смерть;
 Юность->Смерть;
 Зрелость->Смерть;
}

Программа «dot» сама распознаёт все связи графа и упорядочивает его таким образом, чтобы было наименьшее количество пересечений.

Программа DOT поддерживает следующие форматы выходного файла:

Недостатки для моего случая:

• программа является Windows-приложением, поэтому в вебе использовать не получится
• генерация в виде изображения, что само по себе ограничения для создания интерактивных приложений

На сайте есть множество дополнительных программ и инструментов, использующие Graphviz в качестве основного компонента.

Например, проект WebDot позволяет конвертировать dot файлы в изображения, которые можно публиковать в вебе, но необходим Apache сервер.

Примеры изображений (примеры взяты с галереи сайта проекта):

Библиотека Wingraphviz.dll

Есть возможность строить такие же графы полностью программно через технологию COM. Для этого используется программа Wingraphviz, содержащая в себе движок DOT. Эта программа оформлена в виде DLL и позволяет вызывать себя из других программ, в том числе из C# программ.

Для использования библиотеки Wingraphviz.dll ее необходимо зарегистрировать в реестре c помощью команды (что уже является недостатком):

В программном коде Wingraphviz вызывается следующим образом:

WINGRAPHVIZLib.DOTClass d = new WINGRAPHVIZLib.DOTClass();
Bitmap и = d.ToPNG("fileName.dot");
b.Save("fileName.png");

Потом файл вставляется как графический объект на веб-страницу. В принципе, работает, но такое решение не по фэн-шую.

Поддерживаемые форматы:

• TextImage

	SVG	: Scalable Vector Graphics.
	Plain	: Simple, line-based ASCII format.
	PlainExt	: Simple, line-based ASCII format.
	Dot	: Attributed DOT.
	Canon	: Prettyprint input; no layout is done.
	PS	: PostScript (EPSF) .

• BinaryImage

	GIF	: GIF89a.
	PNG	: Portable Network Graphics.
	SVGZ	: Compressed SVG.
	WBMP	: Wireless BitMap .
	JPEG
	EMF	: Enhanced-Format Metafiles .

• ImageMap

	CMAP	: Client-side image map..
	ISMAP	: Server-side image map.
	IMAP	: Apache map file for httpd servers.

QuickGraph, Graph Data Structures And Algorithms for .Net

QuickGraph provides generic directed/undirected graph datastructures and algorithms for .Net 2.0 and up. QuickGraph comes with algorithms such as depth first seach, breath first search, A* search, shortest path, k-shortest path, maximum flow, minimum spanning tree, least common ancestors, etc... QuickGraph supports MSAGL, GLEE, and Graphviz to render the graphs, serialization to GraphML, etc...

Если говорить о .NET, то нельзя не сказать о QuickGraph - наборе инструментов и алгоритмов для работы с графами. По ссылке вы найдете для себя много чего интересного, но в данный момент мы занимаемся визуализацией. Итак, QuickGraph поддерживает три вида визуализации:

• Visualization Using MsAgl
• Visualization Using Glee
• Visualization Using Graphviz

С первыми двумя не сильно разбирался - необходимо иметь сборки MsAgl и Glee, а вот с третьим пунктом пришлось разобраться.

Вот такой код:

IVertexAndEdgeListGraph<TVertex,TEdge> g = ...;
var graphviz = new GraphvizAlgorithm<TVertex,TEdge>(g);

// render
string output = graphviz.Generate(new FileDotEngine(), "graph");

сохранит ваш граф в dot формате. Что делать с этим файлом дальше - либо Wingraphviz, либо ваш вариант.

JavaScript InfoVis Toolkit

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

Вот что получилось для запроса "Paris Hilton":

Canviz

JavaScript library for drawing Graphviz graphs to a web browser canvas.

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

Таким образом мой файл вида:

digraph G {
0 ; 1 ; 2 ; 3 ; 4 ; 5 ; 6 ; 7 ; 8 ; 9 ; 10 ;
11 ; 12 ; 13 ; 14 ; 15 ; 16 ; 17 ; 18 ; 19 ; 20 ;
21 ; 22 ; 23 ; 24 ; 25 ; 26 ; 27 ;  28 ; 29 ; 30 ;
31 ; 32 ; 33 ; 34 ; 35 ; 36 ; 37 ; 38 ; 39 ; 40 ;
41 ; 42 ; 43 ; 44 ;  45 ; 46 ; 47 ; 48 ; 49 ; 50 ;
51 ; 52 ; 53 ; 54 ; 55 ; 56 ;
0 -> 24 [];
0 -> 1 [];
1 -> 0 [];
1 -> 17 [];
1 -> 41 [];
2 -> 0 [];
2 -> 9 [];
2 -> 27 [];
3 -> 0 [];
3 -> 24 [];
4 -> 0 [];
4 -> 17 [];
4 -> 27 [];
5 -> 0 [];
6 -> 0 [];
7 -> 0 [];
8 -> 0 [];
10 -> 9 [];
10 -> 26 [];
11 -> 9 [];
12 -> 9 [];
13 -> 9 [];
14 -> 9 [];
15 -> 9 [];
16 -> 9 [];
17 -> 24 [];
18 -> 17 [];
19 -> 17 [];
20 -> 17 [];
21 -> 17 [];
22 -> 17 [];
23 -> 17 [];
25 -> 24 [];
26 -> 24 [];
27 -> 24 [];
28 -> 24 [];
29 -> 24 [];
30 -> 26 [];
31 -> 26 [];
32 -> 26 [];
33 -> 26 [];
34 -> 26 [];
35 -> 26 [];
36 -> 26 [];
37 -> 1 [];
38 -> 1 [];
39 -> 1 [];
40 -> 1 [];
41 -> 1 [];
42 -> 1 [];
43 -> 1 [];
44 -> 27 [];
45 -> 27 [];
46 -> 27 [];
47 -> 27 [];
48 -> 27 [];
49 -> 27 [];
50 -> 41 [];
51 -> 41 [];
52 -> 41 [];
53 -> 41 [];
54 -> 41 [];
55 -> 41 [];
56 -> 41 [];
}

не был визуализирован. Я даже задал вопрос по этому поводу, пока ответов нет.

А пока ответов нет...

... я остановился на варианте GraphLight. Simple graph layout engine for silverlight.

Итак, имея вот такой вот исходный файл:

digraph Task <br />{<br />	nodes:<br />		s1 [label="microsoft.com"];<br />		s2 [label="msn.com"];<br />		s3 [label="download.cnet.com"];<br />		s4 [label="apple.com"];<br />		s5 [label="symantec.com"];<br />		s6 [label="ibm.com"];<br />		s7 [label="hp.com"];<br />		s8 [label="adobe.com"];<br />		s9 [label="dell.com"];<br />		s10 [label="microsoft.com"];<br />		s11 [label="openoffice.org"];<br />		s12 [label="freedownloadscenter.com"];<br />		s13 [label="freedownloadscenter.com"];<br />		s14 [label="en.kioskea.net"];<br />		s15 [label="kutchka.com"];<br />		s16 [label="download.openoffice.org"];<br />		s17 [label="brothersoft.com"];<br />		s18 [label="support.microsoft.com"];<br />		s19 [label="support.dell.com"];<br />		s20 [label="adobe.com"];<br />		s21 [label="techguy.org"];<br />		s22 [label="kellys-korner-xp.com"];<br />		s23 [label="support.xbox.com"];<br />		s24 [label="aumha.org"];<br />		s25 [label="en.wikipedia.org"];<br />		s26 [label="microsoft.com"];<br />		s27 [label="office.microsoft.com"];<br />		s28 [label="windowsupdate.microsoft.com"];<br />		s29 [label="research.microsoft.com"];<br />		s30 [label="wiki.answers.com"];<br />		s31 [label="xbox.com"];<br />		s32 [label="microsoft.com"];<br />		s33 [label="teamxbox.com"];<br />		s34 [label="xbox360.ign.com"];<br />		s35 [label="en.wikipedia.org"];<br />		s36 [label="en.wikipedia.org"];<br />		s37 [label="us.playstation.com"];<br />		s38 [label="bungie.net"];<br />		s39 [label="xboxscene.com"];<br />		s40 [label="en.wikipedia.org"];<br />		s41 [label="en.wikipedia.org"];<br />		s42 [label="officelive.com"];<br />		s43 [label="us20.trymicrosoftoffice.com"];<br />		s44 [label="workspace.officelive.com"];<br />		s45 [label="thinkfree.com"];<br />		s46 [label="docs.google.com"];<br />		s47 [label="free.avg.com"];<br />		s48 [label="mozilla.com"];<br />		s49 [label="softwarepatch.com"];<br />		s50 [label="en.wikipedia.org"];<br />		s51 [label="mozilla.org"];<br />		s52 [label="lavasoft.com"];<br />		s53 [label="home.live.com"];<br />		s54 [label="hotmail.com"];<br />		s55 [label="download.live.com"];<br />		s56 [label="yahoo.com"];<br />		s57 [label="bing.com"];<br />		s58 [label="mail.google.com"];<br />		s59 [label="cnn.com"];<br />	edges:<br />		s1 -> s25;<br />		s1 -> s2;<br />		s2 -> s1;<br />		s2 -> s18;<br />		s3 -> s1;<br />		s3 -> s10;<br />		s3 -> s28;<br />		s4 -> s1;<br />		s4 -> s25;<br />		s5 -> s1;<br />		s5 -> s18;<br />		s5 -> s28;<br />		s6 -> s1;<br />		s7 -> s1;<br />		s8 -> s1;<br />		s9 -> s1;<br />		s11 -> s10;<br />		s11 -> s27;<br />		s12 -> s10;<br />		s13 -> s10;<br />		s14 -> s10;<br />		s15 -> s10;<br />		s16 -> s10;<br />		s17 -> s10;<br />		s18 -> s25;<br />		s19 -> s18;<br />		s20 -> s18;<br />		s21 -> s18;<br />		s22 -> s18;<br />		s23 -> s18;<br />		s24 -> s18;<br />		s26 -> s25;<br />		s27 -> s25;<br />		s28 -> s25;<br />		s29 -> s25;<br />		s30 -> s25;<br />		s32 -> s31;<br />		s33 -> s31;<br />		s34 -> s31;<br />		s35 -> s31;<br />		s36 -> s31;<br />		s37 -> s31;<br />		s38 -> s31;<br />		s39 -> s31;<br />		s40 -> s27;<br />		s41 -> s27;<br />		s42 -> s27;<br />		s43 -> s27;<br />		s44 -> s27;<br />		s45 -> s27;<br />		s46 -> s27;<br />		s47 -> s28;<br />		s48 -> s28;<br />		s49 -> s28;<br />		s50 -> s28;<br />		s51 -> s28;<br />		s52 -> s28;<br />		s53 -> s2;<br />		s54 -> s2;<br />		s55 -> s2;<br />		s56 -> s2;<br />		s57 -> s2;<br />		s58 -> s2;<br />		s59 -> s2;<br />}

можно получить такую вот картинку:

Несколько моментов реализации: так как в проекте используются заранее подготовленные *.graph файлы, а мне необходимо было генерировать их на основе пользовательских данных (запроса и количества обрабатываемых страниц), кроме того Silverlight-приложения не позволяют читать файлы вне сборки и делать кросс-доменные запросы, то было решено получать текстовый файл из другого проекта (предварительно создав для него файл clientaccesspolicy.xml, который позволяет нашему Silverlight приложению получать данные от этого приложения). Таким образом первый проект на выходе выдает текст со структурой графа, а Silverlight приложение на основе этих данных рисует граф.

Думаю позже опубликовать сервис генерации graph файлов в интернете, как и Silverlight приложение.

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

P.S. О других инструментах можно почитать на stackoverflow:

• Directed graph layout engines on .NET / Silverlight / JavaScript / Flash
• What options are available for the layout of directed or undirected graphs in .NET?
• graph viewer/drawer for c#?

P.S.S.

• Graph#
• Netron Reloaded
• MSAGL (Microsoft Research Automatic Graph Layout - paid)
• Flare (идеальный вариант, но на Flex, которым я не владею)

Если у вас есть свои идеи (инструменты, реализации) - делитесь в комментариях.