c# - QuickGraph 查找有向多图的所有路径
问题描述
我有一个有向多图,其中两个节点之间可以存在多个边。对于此图,我想知道两个节点之间的所有可能路径。因此,对于下面的示例,节点 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”参数的作用?
解决方案
推荐阅读
- r - R Shiny - 我真的需要所有这些 REACTIVE 功能吗?
- django - 尽管将 required attr 设置为 false,但仍需要表单字段
- javascript - JavaScript Regex 在 SQL 插入中的单引号内获取多个单引号
- java - Apache Spark to_json options parameter
- python - 如何使用循环将输出放入列表中?
- mysql - MYSQL 创建表语句给我“非唯一”错误?
- c# - 用数据表中的 ID 替换名称的快速方法?
- python - 将特定列的值与不同文件进行比较
- python - 无法解压不可迭代的 int 对象
- python - 如何将辅助 python 文件上传到谷歌云平台?