5

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?

skaffman
  • 398,947
  • 96
  • 818
  • 769
Greg
  • 34,042
  • 79
  • 253
  • 454

3 Answers3

3

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

Doug
  • 5,208
  • 3
  • 29
  • 33
  • thanks Doug - by the way can I ask you if have any comments on two key questions I had with QuickGraph for which I didn't get any responses: http://stackoverflow.com/questions/2718241/can-quickgraph-support-these-requirements-includes-database-persistence-support, and http://stackoverflow.com/questions/2718522/quickgraph-how-can-i-associate-an-edge-with-a-class-i-e-like-you-can-with-a thanks – Greg May 03 '10 at 23:56
2

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.

bbzippo
  • 21
  • 1
  • I thought as much as well but not the algorithms work well with the ReversedBidirectionalGraph. Normally you would use but with the reversed one it should be >. That will work out of the box. – Thulani Chivandikwa Feb 16 '17 at 17:14
  • Could you provide your whole implementation? It is hard to make use of your answer without it. – Olivér Raisz Mar 30 '23 at 11:29
1

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;
    }
prabug
  • 161
  • 8