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



Coordinator
Nov 9, 2008 at 2:44 PM

Do you mean all shortest path between 2 vertices? This would be FloydWarshall which is not implemented.




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.




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);
}




Hi,
is it difficult to implement FloydWarshall 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)




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 FloydWarshall algorithm, see FloydWarshallAllShortestPathAlgorithm in the V3 branch.
To use it, create the algorithm, compute, then use TryGetPath, TryGetCost to extract the paths.




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.




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




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




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].




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




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




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 kshortest path  there exist algorithm but QuickGraph does not implement any.




If you need help to implement kshortest path algorithm I'm here.
Bye.




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/kshortestpaths/) 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 kshortest paths problem.
Using this thread we can start implementing Yen's algorithm to solve the problem.
Thanks for you attention.
Bye.




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




It's hard to implement it!
I'm not understanding this algorithm.
Bye.




Someone can explain this algorithm step by step?
Thanks!




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 kth 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 HoffmanPavlet 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




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?




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 biconnected graph and bidirectional graph. Your example will work perfectly fine, you simply need to use a datastructure that implement IBidirectional<TVertex,TEdge>.




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.




I've created a new Issue Tracker with attached my serialized adjacency graph.
Bye.



Coordinator
Jan 6, 2009 at 5:30 PM

Fixed.

