1

我有一个有向多图，其中两个节点之间可以存在多个边。对于此图，我想知道两个节点之间的所有可能路径。因此，对于下面的示例，节点 0 和 2 之间的生成路径将是：

  • 0 -> 2
  • 0 - 边 A-> 1 -> 2
  • 0 - 边 B-> 1 -> 2

在此处输入图像描述

我正在尝试使用以下 QuickGraph 实现来完成此操作：

var startNode = "0";
var endNode = "2";

var graph = new AdjacencyGraph<string, TaggedEdge<string, string>>(allowParallelEdges: true);

var edges = new List<TaggedEdge<string, string>>{
    new TaggedEdge<string, string>("0", "1", "edge A"),
    new TaggedEdge<string, string>("0", "1", "edge B"),
    new TaggedEdge<string, string>("1", "2", string.Empty),
    new TaggedEdge<string, string>("0", "2", string.Empty),
    new TaggedEdge<string, string>("0", "3", string.Empty),
    new TaggedEdge<string, string>("1", "3", string.Empty), };
edges.ForEach(x => graph.AddVerticesAndEdge(x));

var algo = new EdgeDepthFirstSearchAlgorithm<string, TaggedEdge<string, string>>(graph);
var observer = new EdgePredecessorRecorderObserver<string, TaggedEdge<string, string>>();

using (observer.Attach(algo))
{
    algo.Compute(startNode);
}

var allPaths = observer.AllPaths().Where(x => x.Last().Target == endNode);

但是，此实现仅返回 2 条路径：

  • 0 -> 2
  • 0 -> 1 -> 2

因此，似乎平行边缘不会产生单独的路径。QuickGraph 中是否有任何方法可以实现这一点。而且，有谁知道 Graph 构造函数中的“allowParallelEdges”参数的作用？

4

0 回答 0