QuickGraph - 是否有找到一組頂點的所有父項（根到頂點的）的算法

Question

在QuickGraph中 - 是否有算法用於查找一組頂點的所有父項（至頂點的頂點）。換句話說，所有在它們下面（在葉節點的途中）的頂點都有一個或多個頂點輸入。因此，如果頂點是節點，並且邊是一個取決於關係的關係，則查找將受到給定節點集影響的所有節點。

如果不是編寫自己的算法有多難？

Answer 1

下面就是我用來完成在給定的頂點前身搜索：

IBidirectionalGraph<int, IEdge<int>> CreateGraph(int vertexCount) 
{ 
    BidirectionalGraph<int, IEdge<int>> graph = new BidirectionalGraph<int, IEdge<int>>(true); 
    for (int i = 0; i < vertexCount; i++) 
     graph.AddVertex(i); 

    for (int i = 1; i < vertexCount; i++) 
     graph.AddEdge(new Edge<int>(i - 1, i)); 

    return graph; 
} 

static public void Main() 
{ 
    IBidirectionalGraph<int, IEdge<int>> graph = CreateGraph(5); 

    var dfs = new DepthFirstSearchAlgorithm<int, IEdge<int>>(graph);    
    var observer = new VertexPredecessorRecorderObserver<int, IEdge<int>>(); 

    using (observer.Attach(dfs)) // attach, detach to dfs events 
     dfs.Compute(); 

    int vertexToFind = 3; 
    IEnumerable<IEdge<int>> edges; 
    if (observer.TryGetPath(vertexToFind, out edges)) 
    { 
     Console.WriteLine("To get to vertex '" + vertexToFind + "', take the following edges:"); 
     foreach (IEdge<int> edge in edges) 
      Console.WriteLine(edge.Source + " -> " + edge.Target); 
    } 
} 

需要注意的是，如果你知道你的根事先，你可以在dfs.Compute()方法（即dfs.Compute(0)）指定。

-Doug

Answer 2

我用道格的答案，結果發現，如果有一個頂點不止一個家長，他的解決方案只提供父母一方。我不知道爲什麼。

所以，我創建了自己的版本，這是如下：

public IEnumerable<T> GetParents(T vertexToFind) 
    { 
     IEnumerable<T> parents = null; 

     if (this.graph.Edges != null) 
     { 
      parents = this.graph 
       .Edges 
       .Where(x => x.Target.Equals(vertexToFind)) 
       .Select(x => x.Source); 
     } 

     return parents; 
    } 

Answer 3

您也需要保持一個逆轉圖形，或覆蓋反轉每條邊的圖形創建一個包裝。 QuickGraph具有ReversedBidirectionalGraph類，它是一個專門用於此目的的包裝器，但由於泛型類型不兼容，它似乎不適用於算法類。 我必須創建自己的包裝類：

class ReversedBidirectionalGraphWrapper<TVertex, TEdge> : IVertexListGraph<TVertex, TEdge> where TEdge : IEdge<TVertex> 
{ 
    private BidirectionalGraph<TVertex, TEdge> _originalGraph; 
    public IEnumerable<TEdge> OutEdges(TVertex v) 
    { 
     foreach (var e in _graph.InEdges(v)) 
     { 
      yield return (TEdge)Convert.ChangeType(new Edge<TVertex>(e.Target, e.Source), typeof(TEdge)); 
     } 
    } //...implement the rest of the interface members using the same trick 
} 

然後在此包裝上運行DFS或BFS：

var w = new ReversedBidirectionalGraphWrapper<int, Edge<int>>(graph);  
var result = new List<int>();  
var alg = new DepthFirstSearchAlgorithm<int, Edge<int>>(w); 
alg.TreeEdge += e => result.Add(e.Target);  
alg.Compute(node); 

道格的答案是不正確的，因爲DFS將只能訪問下游的子圖。前任觀察員沒有幫助。