c# - QuickGraph-一連の頂点のすべての親（ルート頂点まで）を検索するためのアルゴリズムはありますか

Question

QuickGraphには、一連の頂点のすべての親（ルート頂点まで）を検索するためのアルゴリズムがあります。言い換えると、その下のどこかに（リーフノードに向かう途中で）1つ以上の頂点が入力されているすべての頂点。したがって、頂点がノードであり、エッジが依存関係である場合、特定のノードのセットによって影響を受けるすべてのノードを見つけます。

そうでなければ、自分のアルゴリズムを書くのはどれほど難しいですか？

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

-ダグ

Answer 2

Doug の回答を使用したところ、頂点に複数の親がある場合、彼の解決策は親の 1 つしか提供しないことがわかりました。理由はわかりません。

そこで、次のような独自のバージョンを作成しました。

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