Лекция: QuickGraph

Существует прекрасная бесплатная библиотека для работы с графами – QuickGraph. Работа с графами в этой библиотека реализована очень просто.

Импортируем пространство имен:
Imports QuickGraph

Объявляем граф:
Dim graph As New BidirectionalGraph(Of Object, IEdge(Of Object))

Как ранее было сказано, компьютеры – это узлы нашего графа. Добавляем узел:
graph.AddVertex(«ИмяКомпьютера»)

Список компьютеров мы возьмем из Active Directory:
Dim de As New DirectoryServices.DirectoryEntry
Dim search As New DirectorySearcher(de)
search.Filter = "(objectCategory=computer)"
Dim results As SearchResultCollection = search.FindAll()
For i As Integer = 0 To results.Count — 1
Dim de2 As DirectoryEntry = results(i).GetDirectoryEntry
Dim ComputerName As String = CType(de2.InvokeGet(«cn»), String)
graph.AddVertex(ComputerName)
Next

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

Как известно все компьютеры имеют общие точки, с которыми они связаны – маршрутизаторы (роутеры). Возможен вариант, когда локальная сеть не имеет маршрутизатора, но в этом случае ее визуализация достаточно проста.

Каждый компьютер сети напрямую связан с маршрутизатором, адрес которого прописан как шлюз в свойствах сетевой платы компьютера.

Пройдясь по компьютерам при помощи WMI…
Private Function GetGateway(ByVal ComputerName As String) As String
Dim s As String = String.Empty
Dim query As ManagementObjectSearcher
Dim queryCollection As ManagementObjectCollection
Dim msc As ManagementScope = New ManagementScope("\\" + ComputerName + "\root\cimv2")
query = New ManagementObjectSearcher(msc, New SelectQuery(«SELECT * FROM Win32_NetworkAdapterConfiguration»))
queryCollection = query.Get()
For Each mObject As ManagementObject In queryCollection
Try
If mObject(«DefaultIPGateway»).ToString <> "" Then
s = mObject(«DefaultIPGateway»)(0).ToString
End If
Catch
End Try
Next
Return s
End Function

… получим список всех шлюзов. Добавим их в граф, так же как и компьютеры:
graph.AddVertex(«ИмяШлюза»)

Одновременно с добавлением узлов, добавим связь между компьютером и шлюзом:
graph.AddEdge(New Edge(Of Object)(«ИмяКомпьютера», «ИмяШлюза»))

Вот теперь мы получили граф, но только не визуальный.

Graph#

QuickGraph поддерживает MSAGL, GLEE и Graphviz для визуализации графов, но мы воспользуемся Graph#. Данный фреймворк содержит различные алгоритмы для визуализации графов в WPF приложениях.

Размещаем на форме GraphLayuot контрол из данного фреймворка и пишем простую строку для отображения созданного нами ранее графа:
GraphLayout.Graph = graph
И это все, что нам нужно. Все остальное возьмет на себя Graph#.

Литература

• Dijkstra E. W. A note on two problems in connexion with graphs. // Numerische Mathematik. V. 1 (1959), P. 269—271
• Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1.
• Ананий В. Левитин. Глава 9. Жадные методы: Алгоритм Дейкстры // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. — М.: «Вильямс», 2006. — С. 189—195. — ISBN 0-201-74395-7.