Calculating paths in a graph

Question

Hi! I have to make a method for making a list with all the paths in a graph.My graph has only one start node and one finish node. Each node has a list whith its children and other list whith its parents. I have to make another list containing all the paths (each of them in another list)

Any suggestion??

Answer 1

You could generate every possible combination of vertices (using combinatorics) and filter out the paths that don't exist (where the vertices aren't joined by an edge or the edge has the wrong direction on it).

You can improve on this basic idea by having the code that generates the combinations check what remaining vertices are available from the current vertex.

This is all assuming you have acyclic graphs and wish to visit each vertex exactly once.

Answer 2

It depends on whether it is acyclic or not. Clearly a cycle will result in infinity paths (once round the loop, twice round, 3 times round... etc etc). If the graph is acyclic then you should be able to do a depth-first seach (DFS) (http://en.wikipedia.org/wiki/Depth-first%5Fsearch) and simply count the number of times you encounter the destination node.

Answer 3

First familiarize yourself with basic graph algorithms (try a textbook, or google). Figure out which one best suits the problem you are solving, and implement it. You may need to adapt the algorithm a little, but in general there are widely known algorithms for all basic graph problems.

Answer 4

If you have a GraphNode class that looks something like this:

public class GraphNode
{
 public IEnumerable<GraphNode> Children { get; set; }
 // ...
}

Then this sould do the work:

public static class GraphPathFinder
{
 public static IEnumerable<IEnumerable<GraphNode>> FindAllPathsTo(this GraphNode startNode, GraphNode endNode)
 {
  List<IEnumerable<GraphNode>> results = new List<IEnumerable<GraphNode>>();
  Stack<GraphNode> currentPath = new Stack<GraphNode>();
  currentPath.Push(startNode);

  FindAllPathsRecursive(endNode, currentPath, results);

  return results;
 }

 private static void FindAllPathsRecursive(GraphNode endNode, Stack<GraphNode> currentPath, List<IEnumerable<GraphNode>> results)
 {
  if (currentPath.Peek() == endNode) results.Add(currentPath.ToList());
  else
  {
   foreach (GraphNode node in currentPath.Peek().Children.Where(p => !currentPath.Contains(p)))
   {
    currentPath.Push(node);
    FindAllPathsRecursive(endNode, currentPath, new List<IEnumerable<GraphNode>>());
    currentPath.Pop();
   }
  }
 }
}

It's a simple implementation of the DFS algorithm. No error checking, optimizations, thread-safety etc...

Also if you are sure that your graph does not cycles, you may remove the where clause in the foreach statement in the last method.

Hope this helped.