Find all paths from start vertex to the end vertex.

Topics: algorithm
Jul 3, 2008 at 12:08 PM
Hi all.

I'm using quick graph in my project and I need to know the number of paths from the start vertex to the end vertex, it doesn't matter the size of the path, just the number of paths. I searched in this API but it hasn't a way to do this. does it have?

Does anyone know how can I implement this? I'm studying the possibility of implement a kind of DFS algorithm, but with some changes to do this? Is it the best solution or is there a better one?

Thanks a lot.



Jan 10, 2010 at 2:29 PM

Although I have another task to do, I need the same problem solved.

I have a DAG and have to get to know all possible subgraphs between a vertex source and a vertex sink, no matter how long the route is. The edges are also not weighted.

Apr 6, 2010 at 1:06 PM

the following code will give you th enumber and routes of all paths found in a Bidirectional graph using the  HoffmanPavley algorith.

            BidirectionalGraph<string, TaggedEdge<string, string>> mvGraph2 = new BidirectionalGraph<string, TaggedEdge<string, string>>();
            // UndirectedGraph<string, TaggedEdge<string, string>> mvGraph2 = new UndirectedGraph<string, TaggedEdge<string, string>>();

            mvGraph2.AddVerticesAndEdge(new TaggedEdge<string, string>("P1a", "I1", "P1a-I1"));
            mvGraph2.AddVerticesAndEdge(new TaggedEdge<string, string>("I1", "P1a", "I1-P1a"));

            mvGraph2.AddVerticesAndEdge(new TaggedEdge<string, string>("P1a", "I3", "P1a-I3"));
            mvGraph2.AddVerticesAndEdge(new TaggedEdge<string, string>("I3", "P1a", "I3-P1a"));

            mvGraph2.AddVerticesAndEdge(new TaggedEdge<string, string>("I1", "I2", "I1-I2"));
            mvGraph2.AddVerticesAndEdge(new TaggedEdge<string, string>("I2", "I1", "I2-I1"));

            mvGraph2.AddVerticesAndEdge(new TaggedEdge<string, string>("I1", "I3", "I1-I3"));
            mvGraph2.AddVerticesAndEdge(new TaggedEdge<string, string>("I3", "I1", "I3-I1"));

            mvGraph2.AddVerticesAndEdge(new TaggedEdge<string, string>("I3", "I2", "I3-I2"));
            mvGraph2.AddVerticesAndEdge(new TaggedEdge<string, string>("I2", "I3", "I2-I3"));

            mvGraph2.AddVerticesAndEdge(new TaggedEdge<string, string>("I3", "Leach", "I3-Leach"));
            mvGraph2.AddVerticesAndEdge(new TaggedEdge<string, string>("Leach", "I3", "Leach-I3"));

            mvGraph2.AddVerticesAndEdge(new TaggedEdge<string, string>("I2", "Leach", "I2-Leach"));
            mvGraph2.AddVerticesAndEdge(new TaggedEdge<string, string>("Leach", "I2", "Leach-I2"));
           
            HoffmanPavleyRankedShortestPathAlgorithm<string, TaggedEdge<string, string>> test1 = new HoffmanPavleyRankedShortestPathAlgorithm<string, TaggedEdge<string, string>>(mvGraph2, E => 1.0);

            test1.ShortestPathCount = 10;

            //int.MaxValue;

            test1.SetRootVertex("P1a");
            test1.SetRootVertex("Leach");

            // test1.Compute();

            test1.Compute("P1a", "Leach");
           
            System.Diagnostics.Trace.WriteLine("Paths Found = " + test1.ComputedShortestPathCount.ToString() );

            foreach (IEnumerable<TaggedEdge<string, string>> path in test1.ComputedShortestPaths)
            {
                System.Diagnostics.Trace.WriteLine("Path Found.....");
                foreach (var edge in path)
                {
                    System.Diagnostics.Trace.WriteLine(edge);
                }
            }

Apr 7, 2010 at 10:40 AM

Thanx a lot!