Создание неориентированного графа и его обход с помощью BFS в QuickGraph

Question

Я пытаюсь выяснить, как создать новый экземпляр неориентированного взвешенного графа, используя QuickGraph для C#. Моя цель - создать неориентированный взвешенный граф, заполненный случайным числом узлов и случайно сгенерированными начальными и конечными узлами, кратчайший путь которых можно найти с помощью алгоритма поиска в ширину. В документации немногое, так что если кто-то может оказать любую помощь, которая будет признательна.

Answer 1

Ричард, QuickGraph не делает ничего для вас, он только делает доступными события, на которые вы можете подписаться. Подписавшись на эти события, вы можете ответить соответствующим образом. Из общепризнанного отсутствия документации QuickGraph по поиску в глубину (да, я понимаю, что вы делаете BFS, а не DFS, но концепция подписки на события одинакова):

1. InitializeVertex, вызывается в каждой вершине перед началом вычисления,
2. DiscoverVertex, вызывается при первом обнаружении вершины,
3. ExamineEdge, который вызывается на каждом ребре каждой вершины после ее обнаружения,
4. TreeEdge, который вызывается для каждого ребра, когда он становится членом ребер, образующих дерево поиска.
5. FinishVertex, вызываемый в вершине после того, как все ее внешние ребра были добавлены в дерево поиска и были обнаружены все смежные вершины (но до того, как их внешние ребра были исследованы).

Кстати, откройте Reflector и взгляните на QuickGraph.Algorithms.Observers. И ваше требование кратчайшего пути будет проще с другим методом, чем BFS.

Answer 2

На Github была короткая ветка, в которой был полезный базовый пример того, как настроить BFS и получить от него некоторые результаты.

Другие детали, специфичные для вашего приложения (создание случайного графа и т. Д.), Очевидно, не являются частью этого примера.

Источник:https://github.com/YaccConstructor/QuickGraph/issues/189

Вот полный пример:

UndirectedGraph<string, Edge<string>> g = new UndirectedGraph<string, Edge<string>>();

g.AddVerticesAndEdge(new Edge<string>("0", "1"));
g.AddVerticesAndEdge(new Edge<string>("0", "2"));
g.AddVerticesAndEdge(new Edge<string>("2", "3"));

var algo = new UndirectedBreadthFirstSearchAlgorithm<string, Edge<string>>(g);

var observer = new UndirectedVertexPredecessorRecorderObserver<string, Edge<string>>();

var rootVertex = "0";
using (observer.Attach(algo))
{
    algo.Compute(rootVertex);
}

var targetVertex = "3";
bool foundPath = observer.TryGetPath(targetVertex, out IEnumerable<Edge<string>> path);

path будет содержать два ребра:

[0]: "0"->"2"
[1]: "2"->"3"

Answer 3

Для этого алгоритма еще нет документации; но есть следующая лучшая вещь (или, возможно, даже лучшая вещь): юнит тест!

Если вы загрузите источники QuickGraph и найдете BreadthFirstAlgorithmSearchTest.BreadthFirstSearchAll(), вы увидите пример использования алгоритма, который запускает BFS на всех ориентированных графах в тестовом проекте.