Greg - 1 year ago 88
C# Question

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

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?

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

for (int i = 1; i < vertexCount; 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

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download