QuickGraph查找顶点的不度

本文关键字：顶点 查找 QuickGraph | 更新日期: 2023-09-27 18:19:56

我正在使用QuickGraph创建一个有向无环图。我需要找到所有不度数为零的顶点。我在图的Vertices集合上看不到这种支持，也看不到使用LINQ进行过滤的方法。

这是我正在编写的一个示例数据结构：

var componentGraph = new AdjacencyGraph<Component, Edge<Component>>();
var serverOnMachineA = new TalismaServerComponent("CLTDEPAPI10");
var serverOnMachineB = new TalismaServerComponent("CLTDEPAPI11");
var appServerOnMachineB = new TalismaAppServerComponent("CLTDEPAPI11");
var webComponentsOnMachineC = new TalismaWebComponentsComponent("CLTDEPFE1");
componentGraph.AddVertex(serverOnMachineA);
componentGraph.AddVertex(serverOnMachineB);
componentGraph.AddVertex(appServerOnMachineB);
componentGraph.AddVertex(webComponentsOnMachineC);
componentGraph.AddEdge(new Edge<Component>(appServerOnMachineB, serverOnMachineA));
componentGraph.AddEdge(new Edge<Component>(webComponentsOnMachineC, appServerOnMachineB));
componentGraph.AddEdge(new Edge<Component>(webComponentsOnMachineC, serverOnMachineB));

我只需要这个图中没有"in"边（indegree=0）的顶点的列表。

QuickGraph查找顶点的不度

您可能需要不同的图形类型。深入论坛和QuickGraph的来源，我发现了双向图形类，它是

一种对稀疏有效的可变有向图数据结构需要枚举出边和入边的图形表示。需要是邻接图的两倍内存。

正如本讨论所暗示的，检索入度的方法似乎在IBidirectionalIncidenceGraph上找到。

您使用的数据结构不会对传入的边进行记账，因此您必须通过迭代所有边并查看它们的目标来检索顶点的阶数，这对于大型图来说可能是一项昂贵的操作。

BidirectionalGraph速度更快，但用于记账的内存空间是前者的两倍。使用它，你可以做一些类似的事情：

var orphans = graph.Vertices.Where(v => graph.InDegree(v) == 0)
相关文章：