QuickGraph - is there algorithm for find all paren

问题:

In QuickGraph - is there algorithm for find all parents (up to root vertex's) of a set of vertex's. In other words all vertex's which have somewhere under them (on the way to the leaf nodes) one or more of the vertexs input. So if the vertexs were Nodes, and the edges were a depends on relationship, find all nodes that would be impacted by a given set of nodes.

If not how hard is it to write one's own algorithms?

回答1:

Here's what I've used to accomplish a predecessor search on a given vertex:

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

Note that if you know your root beforehand, you can specify it in the dfs.Compute() method (i.e. dfs.Compute(0)).

-Doug

回答2:

I used Doug's answer and found out that if there are more than one parent for a vertex, his solution only provides one of the parents. I am not sure why.

So, I created my own version which is as follows:

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

回答3:

You either need to maintain a reversed graph, or create a wrapper over the graph that reverses every edge. QuickGraph has the ReversedBidirectionalGraph class that is a wrapper intended just for that, but it does not seem to work with the algorithm classes because of generic type incompatibility. I had to create my own wrapper class:

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
}

Then run DFS or BFS on this wrapper:

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

Doug's answer is not correct, because DFS will only visit the downstream subgraph. The predecessor observer does not help.