0

有向非巡回グラフを作成するために 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));

このグラフで、「イン」エッジを持たない (インディグリー = 0) 頂点のリストが必要なだけです。

4

1 に答える 1

2

別のグラフ タイプが必要になる場合があります。フォーラムとQuickGraphのソースに少し飛び込んで、BidirectionalGraphクラスを見つけました

アウトエッジとインエッジを列挙する必要があるスパース グラフ表現に効率的な可変有向グラフ データ構造。隣接グラフの 2 倍のメモリが必要です。

この議論が示唆するIBidirectionalIncidenceGraphように、インディグリーを取得する方法は にあるようです。

使用するデータ構造は、着信エッジでブックキーピングを行わないため、すべてのエッジを反復処理してターゲットを調べることにより、頂点のイン次数を取得する必要があります。これは、大きなグラフの場合、コストのかかる操作になる可能性があります。

のBidirectionalGraph方が高速ですが、ブックキーピングには 2 倍のメモリ領域が必要です。それを使用すると、次のようなことができます。

var orphans = graph.Vertices.Where(v => graph.InDegree(v) == 0)
于 2014-09-01T14:46:54.300 に答える