QuickGraph - is there algorithm for find all parents (up to root vertex’s) of a set of vertex’s

Topics: graph
Apr 27, 2010 at 6:59 AM

Hi,

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?  

May 11, 2010 at 3:01 PM

What is structure of the graph, is it DAG?

If so I would solve it in following way (lets say that your set of verices is V):

1) change all edges direction so edge (v,w) -> (w,v) we get graph G'

2) perform BFS search with all nodes from V in algorithm queue

Explenation: all vertices reachable from set V in graph G' are on some path w1..w2..wn..v so they can be defined as parent of set V.
You can use some quickgraph algorithms to help you. For instance instead of one BFS ( don't know if you can manipulate nodes queue
in different way then way by reflection) you can do one BFS for each v e V and add all vertices with BlackColor to set. After all iterations
your set will contain parent nodes.

I hope it would be helpfull.

Witek

 

May 12, 2010 at 12:48 PM

Its a Directed Graph Witek - this thread he gives an indicate in the sample code.  So I'm not sure if it really would be a DAG in the sense that the following quote might not be true for my usage "such that there is no way to start at some vertex v and follow a sequence of edges that eventually loops back to v again".   Would this impact the suggested solution here?

re your step 1) would this be done in code manually then, or is there a quickgraph method for this?

re 2) which algorithm is the BFS search - I don't see a Breadth First Search mentioned in the online doco here, oh but I see there is one in the code base

I'll need to let you explanation sink in a bit longer  :)   thanks for responding