Find all path

Topics: algorithm
Nov 8, 2008 at 7:39 AM
Hi guys,

I need to find all path between two vertex. Can you help me? Which is the algorithm to use?

Thanks.

Bye bye.


Coordinator
Nov 9, 2008 at 2:44 PM
Do you mean all shortest path between 2 vertices? This would be Floyd-Warshall which is not implemented.
Nov 9, 2008 at 3:59 PM
Hi,

I mean "All Simple Paths": http://www.nist.gov/dads/HTML/allSimplePaths.html

Maybe I solved the problem using this:

public void FindPath(int S, int E, ArrayList Path){if (S == E){Path.Add(S);AllPath.Add(new ArrayList(Path));Path.RemoveAt(Path.Count - 1);return;}if (Path.Contains(S))return;Path.Add(S);var K = g.OutEdges(S).GetEnumerator();while (K.MoveNext()){FindPath(K.Current.Target, E, Path);}Path.RemoveAt(Path.Count - 1);}

Where S is Start Vertex, E is End Vertex, and g is the Adjacency Graph.

What do you think about? It's good!! It returns really all paths!

bye.


Nov 9, 2008 at 4:04 PM
Sorry!! This is the function:

public void FindPath(int S, int E, ArrayList Path)
{
if (S == E)
{
Path.Add(S);
AllPath.Add(new ArrayList(Path));
Path.RemoveAt(Path.Count - 1);
return;
}
if (Path.Contains(S))
return;

Path.Add(S);

var K = g.OutEdges(S).GetEnumerator();

while (K.MoveNext())
{
FindPath(K.Current.Target, E, Path);
}
Path.RemoveAt(Path.Count - 1);
}

Nov 19, 2008 at 6:38 PM
Hi,

is it difficult to implement Floyd-Warshall algorithm?

Thanks.
Coordinator
Nov 20, 2008 at 4:48 AM
I've started but I need time to finish it. It's a well known and documented algorithm so it should be fairly easy to write (always easier said than done)
Nov 30, 2008 at 1:21 PM
Hi,

I'm also very interested in this topic. I'm trying to integrate QuickGraph in my train control program (http://users.telenet.be/loccommander)  to determine all routes between 2 vertices.

Great work QuickGraph!

Best regards,
Frank
Coordinator
Dec 1, 2008 at 4:48 PM
I've implemented and checkin the Floyd-Warshall algorithm, see FloydWarshallAllShortestPathAlgorithm in the V3 branch.

To use it, create the algorithm, compute, then use TryGetPath, TryGetCost to extract the paths.
Dec 7, 2008 at 5:36 PM
Hi,

Ok, many thanks.

Is it also possible to make it available for the V2 branch?
I have trouble shooting with building V3 version, I'm missing the reference having the

System.Diagnostics.Contracts

Thanks,
Frank

Coordinator
Dec 7, 2008 at 9:05 PM
The v3 branch should build for .NET2.0, without contracts installed. To do this, use the 'Release20' configuration in the QuickGraph solution.
Dec 13, 2008 at 1:05 PM
Hi Jonathan,

Sorry, but still complaining about Contracts... So, I have selected Release20 and target framework is .NET Framework 2.0. Rebuilt the project but still seeks for the Microsoft.contracts reference...
Any idea what I'm still doing wrong.

Thank you.

Best regards,
Frank
Dec 13, 2008 at 3:43 PM
Hi Jonathan,

Good news, with the latest sources I can build it.

Thanks,
Frank
Coordinator
Dec 13, 2008 at 4:15 PM
Yes, I've 'inlined' the contracts API in the QuickGraph library (work in progress for other assemblies).
Dec 13, 2008 at 4:30 PM
Hi Jonathan,

Thanks for the effort!

BTW. how can I define my weights func to use the algo?

Best regards,
Frank
Coordinator
Dec 13, 2008 at 8:59 PM
Are you using C#? Then, you can simply use lambads. If you have a dictionary, pass e => dic[e].
Dec 16, 2008 at 8:13 PM
Hi Jonathan,

Yes I'm using C#, but I don't understand what argument can be specified for the constructor.

What I have...

 

 

 

Dictionary

 

<TaggedEdge<int, MRBaseObject>, double> edgeCost = new Dictionary<TaggedEdge<int, MRBaseObject>, double>(mvGraph.EdgeCount);

 

 

ArrayList staticTrackItems = activeLayout.mfGetStaticObjects().mfGetCollection();

 

 

foreach(MRStaticObject staticObject in staticTrackItems)

 

{

 

foreach(TaggedEdge<int, MRBaseObject> edge in staticObject.mfGetEdges())

 

{

mvGraph.AddVerticesAndEdge(edge);

edgeCost.Add(edge, 20.0F);

}

}

 

ArrayList ctrlTrackItems = activeLayout.mfGetSwitchObjects().mfGetCollection();

 

 

foreach(MRSwitchObject ctrlObject in ctrlTrackItems)

 

{

 

foreach(TaggedEdge<int, MRBaseObject> edge in ctrlObject.mfGetEdges())

 

{

mvGraph.AddVerticesAndEdge(edge);

edgeCost.Add(edge, 20.0F);

}

}

 

if (mvGraph.IsEdgesEmpty)

 

 

return;

 

 

Func<TaggedEdge<int, MRBaseObject>, double> weights = null;

 

 

// We want to use Dijkstra on this graph

 

 

 

 

 

//DijkstraShortestPathAlgorithm<int, TaggedEdge<int, MRBaseObject>> dijkstra = new DijkstraShortestPathAlgorithm<int, TaggedEdge<int, MRBaseObject>>(mvGraph, edgeCost);

 

 

 

 

 

FloydWarshallAllShortestPathAlgorithm<int, TaggedEdge<int, MRBaseObject>> allPaths = new FloydWarshallAllShortestPathAlgorithm<int, TaggedEdge<int, MRBaseObject>>(mvGraph, weights);

 

 

 

This edgeCost used to work in the Dijkstra algo but no longer with this version. And it is not accepted as an argument in the constructor for FloydWarshallAllShortestPathAlgorithm

 

I could use the dictionary edgeCost in the Dijkstra with previous version but not with this version and it can also not be used in the constructor for  FloydWarshallAllShortestPathAlgorithm.


Any help is much appreciated,
Thanks.
Frank



Coordinator
Dec 17, 2008 at 12:26 AM

Dijkstra now takes a delegate that maps a TEdge to a double (i.e. map from edges to their cost). Implicitely, this was done by calling the indexer of the dictionary. Simply pass the following in your case:

    e => edgeCost[e]

If all your edges have constant weight, you do not need a dictionary. Simply use

    e => 1.0

Dec 20, 2008 at 9:57 AM
Hi Jonathan,
I don't know why but this is the way I define object by use of a constructor.
FloydWarshallAllShortestPathAlgorithm<int, TaggedEdge<int, MRBaseObject>> allPaths = new FloydWarshallAllShortestPathAlgorithm<int, TaggedEdge<int, MRBaseObject>>(mvGraph, edgeCost[0]);

But, I get compilation problems as the second arguments is not of type Func... but a double. I reallly don' know how to make a FloydWarshallAllShortestPathAlgorithm object, sorry.

Error 1 The best overloaded method match for 'QuickGraph.Algorithms.ShortestPath.FloydWarshallAllShortestPathAlgorithm<int,QuickGraph.TaggedEdge<int,MRBaseObjects.MRBaseObject>>.FloydWarshallAllShortestPathAlgorithm(QuickGraph.IVertexAndEdgeListGraph<int,QuickGraph.TaggedEdge<int,MRBaseObjects.MRBaseObject>>, QuickGraph.Func<QuickGraph.TaggedEdge<int,MRBaseObjects.MRBaseObject>,double>)' has some invalid arguments E:\Frank\LocCommander\ModelRoadController\MRGraph\MRGraphMgr.cs 78 98 MRGraph
Any help is very welcome.
Thanks.
Frank

----- Original Message -----
From: [email removed]
To: [email removed]
Sent: Wednesday, December 17, 2008 2:26 AM
Subject: Re: Find all path [quickgraph:39479]

From: pelikhan

Dijkstra now takes a delegate that maps a TEdge to a double (i.e. map from edges to their cost). Implicitely, this was done by calling the indexer of the dictionary. Simply pass the following in your case:

e => edgeCost[e]

If all your edges have constant weight, you do not need a dictionary. Simply use

e => 1.0

Dec 20, 2008 at 3:03 PM
Hi Jonathan,

I think I have found a solution to my problem.

Nevertheless, I'm wondering when more than 1 path exists between a source and destination this implementation of the algo will only return one path(the shortest?).
Is there some other algo already implemented to find all paths between a source and a target.

Thanks,
Frank
Coordinator
Dec 20, 2008 at 9:37 PM
There's currently no algorithm in QuickGraph that implements this. This problem is called the k-shortest path - there exist algorithm but QuickGraph does not implement any.
Dec 21, 2008 at 8:05 AM
If you need help to implement k-shortest path algorithm I'm here.

Bye.
Dec 21, 2008 at 10:20 AM
I need to implement this algorithm to use it in a project.

We can share here all informations about this algorithm.

Searching over internet I found many information about it.
Here (http://code.google.com/p/k-shortest-paths/)  there' is an implementation using java language.
It's impossibile to use it because it's copyrighted, so we have to implement it starting from the algorithm.

Here (http://www.mat.uc.pt/~eqvm/cientificos/investigacao/Artigos/new_yen.ps.gz) is possible to download a simple "New implementation of Yen's ranking Loopless paths algorithm".
It solves the k-shortest paths problem.

Using this thread we can start implementing Yen's algorithm to solve the problem.

Thanks for you attention.

Bye.
Dec 24, 2008 at 11:10 AM
Hi giomuti,

Sorry for the late reply but very hard times in professional life...
Yes it would be great if we could implement this algo.
Currently I have not a lot of time to dick into it... and also the Graph code is pretty new to me. But I would like to use it in my control software for model railroad.
I will keep in touch!

Thanks,
Frank
Dec 26, 2008 at 7:57 AM
It's hard to implement it!

I'm not understanding this algorithm.

Bye.
Dec 26, 2008 at 8:55 AM
Someone can explain this algorithm step by step?

Thanks!
Dec 27, 2008 at 7:51 AM
Hi guys,

I'm trying to solve the problem implementing this algorithm.

Once found the shortest path and removed all vertices and arcs except the terminal mode, I need to find  the shortest tree rooted at target vertex.

Someone knows how to do this?

Thanks!
Jan 2, 2009 at 1:04 PM
Edited Jan 2, 2009 at 1:10 PM
If someone needs to find k-th shrortest paths can use this simple and not fast algorithm.
To test it do:

IterateGraph(Graph, Weight, StartVertex, EndVertex, NumIterations);


private List<List<int>> ListShortPaths = new List<List<int>>();
int FullCount = 0;
VertexPredecessorRecorderObserver<int, Edge<int>> Observer;
List<int> PopulatePath(int Vertex, int FirstVertex, List<int> ShortPath)
{
ShortPath.Add(Vertex);
if (Observer.VertexPredecessors.ContainsKey(Vertex) && Vertex != FirstVertex)
PopulatePath(Observer.VertexPredecessors[Vertex].Source, FirstVertex, ShortPath);

return ShortPath;
}
private void IterateGraph(AdjacencyGraph<int, Edge<int>> graph, MyDictionary<Edge<int>, double> Weight, int IDStazA, int IDStazB, int NumeroMaxIterazioni)
{
int ShortPathCount = 0;

DijkstraShortestPathAlgorithm<int, Edge<int>> Algo;
Observer = new VertexPredecessorRecorderObserver<int, Edge<int>>();
Algo = new DijkstraShortestPathAlgorithm<int, Edge<int>>(graph, e => Weight.GetWeight(e));
using (ObserverScope.Create(Algo, Observer))
Algo.Compute(IDStazA);

List<int> ShortPath = PopulatePath(IDStazB, IDStazA, new List<int>());
ShortPath.Reverse();

ShortPathCount = ShortPath.Count;

int j = 0;

int A = 0;
int B = 0;

if (ShortPathCount > 1)
{
ListShortPaths.Add(ShortPath);

for (int i = ShortPathCount - 2; i >= 0; i--)
{
j = i + 1;
A = ShortPath[j];
B = ShortPath[i];

var Edges = graph.Edges.Where(Ed => Ed.Source == B && Ed.Target == A).ToList();

foreach (var Edge in Edges)
{
graph.RemoveEdge(Edge);
}
}
FullCount++;
if (FullCount < NumeroMaxIterazioni)
IterateGraph(graph, Weight, IDStazA, IDStazB, NumeroMaxIterazioni);
}
}

Coordinator
Jan 4, 2009 at 10:10 PM
I've implemented the Hoffman-Pavlet algorithm - http://portal.acm.org/citation.cfm?doid=320998.321004 -. See http://www.codeplex.com/quickgraph/Wiki/View.aspx?title=Ranked%20Shortest%20Path&referringTitle=User%20Manual
Jan 5, 2009 at 8:09 AM
Hi, thanks for you work.

I've a question: Can I use it with a non bidirectional graph? I've seen that the extension method is active only for this type of graph.

bye.
Coordinator
Jan 5, 2009 at 10:32 AM
BidirectionalGraph is needed to compute the first minimum tree on the reversed graph. What other kind of graph are you looking to use?
Jan 5, 2009 at 11:11 AM
Hi, I have a graph that not necessarily is bidirectional.

Take vertices A and B, A is connected to B but not necessarily B is connected to A.

Thanks.
Coordinator
Jan 5, 2009 at 3:28 PM

You are confuising bi-connected graph and bi-directional graph. Your example will work perfectly fine, you simply need to use a datastructure that implement IBidirectional<TVertex,TEdge>.

 

Jan 5, 2009 at 5:17 PM
Ok, sorry.

I've seen the extension method (To bidirectional) with the new changeset.Thanks!

I've a problem. Executing the code below, it returns always (KeyNotFoundException) Error: key not found in the dictionary:

            IBidirectionalGraph<int, Edge<int>> g1 = g.ToBidirectionalGraph();

            int Source = 1;
            int Target = 33;

            int pathCount = 5;

            foreach (IEnumerable<Edge<int>> path in g1.RankedShortestPathHoffmanPavley(E=> 5, Source, Target, pathCount))
            {
            }

Bye.
Coordinator
Jan 5, 2009 at 8:15 PM
Can you please post the stacktrace of this exception? Where does it throw exactly the exception.
Jan 6, 2009 at 6:20 AM
I've created a new Issue Tracker with attached my serialized adjacency graph.

Bye.
Coordinator
Jan 6, 2009 at 5:30 PM
Fixed.