QuickGraph查找顶点的indegree

我正在使用QuickGraph创建一个有向无环图。我需要找到indegree为零的所有顶点。我在图表的Vertices集合中看不到这种支持，或者使用LINQ进行过滤的方式。QuickGraph查找顶点的indegree

下面是一个示例数据结构我构成：

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));

我只需要在这个图中的顶点的列表不具有“中的”边缘（入度= 0）。

来源

2014-08-29 Mark Richman

谁投票结束？这个问题有什么不清楚的地方？我投票弃权。 – chiccodoro 2014-08-29 13:59:32

@chiccodoro谢谢！我不明白为什么这个也不清楚。 – 2014-08-29 14:13:43

'Vertex'是否具有类似IncomingEdges属性或至少类似AdjacentEdges属性的东西？然后，当然，你可以通过使用'componentGraph.Vertices.Where（V型滤池=>！v.IncomingEdges.Any（）'或相似的。不过，我想你需要一定的算法的实现，使这个更好的性能... – chiccodoro 2014-09-01 06:42:13

您可能需要不同的图形类型。潜水比特到QuickGraph的论坛和源我发现BidirectionalGraph类，这是

一个可变的有向图数据结构高效地为其中出边和入边需要被枚举稀疏图表示。需要两倍的内存作为邻接图。

检索入度的方法似乎可以在IBidirectionalIncidenceGraph上找到，因为this discussion意味着。

您使用的数据结构不会保留传入的边缘，因此您必须通过遍历所有边缘并查看其目标来检索顶点的入度，这对于大型图表。

BidirectionalGraph更快，但需要两倍的记忆空间来保存书籍。使用它你可以这样做：

var orphans = graph.Vertices.Where(v => graph.InDegree(v) == 0)

来源

2014-09-01 14:46:54 chiccodoro

我认为这会工作为了我！我将只有少数（<50）顶点，所以效率不是太大的问题。我会试试这个，并将其标记为有效时的答案。谢谢！ – 2014-09-02 00:14:13

@Mark，比我感到高兴的是，我可以为一个我只能通过评论发现的问题提供帮助:-) – chiccodoro 2014-09-02 15:20:41

是告诉我RTFM的一个好方法吗？ – 2014-09-02 15:21:18

QuickGraph查找顶点的indegree

回答

相关问题