
Hi all,
I'm working on a small project to learn .NET 3.5 after transitioning from Java. I'm using the QuickGraph API to write a simple traveling management program.
I'm using an AdjacencyGraph and a Dictionary for weighted edges for my graphs and distances. I can easily find the shortest path from x to y with the DijkstraShortestPathAlgorithm.
I also want to give users the ability to pick a path even if its not the most efficient. I'm attempting to do this with the DepthFirstSearch and specifying the starting node. However, I'm having trouble with the callbacks and correctly determining
all possible paths. I've taken a look at the DepthFirstSearchAlgorithmTest.cs file for some guidance, but its not helping. Is there an existing algorithm to do this? If not, any help would be greatly appreciated.
Thanks,
Todd



Coordinator
Dec 6, 2008 at 6:03 AM

What you want to do is to create a VertexPredecessorRecorderObserver, attach it to the DFS algorithm and 'Compute'. The recorder will store the map of precessor and provides API to extract paths.
var predecessors =
new
VertexPredecessorRecorderObserver<TVertex, TEdge>();
using (ObserverScope.Create(dfs, predecessors))
dfs.Compute();
IEnumerable<TEdge> edges;
if(predecessors.TryGetPath(v, out edges))
...
You can also use the CyclePoppingRandomTree to efficiently cover a graph with a tree.




Hi Boys,
please help me. How can I have all possible paths between two vertices using DFS algorithm?
How can I find them using CyclePoppingRandomTree.
Thanks.



Dec 10, 2008 at 8:08 PM
Edited Dec 10, 2008 at 8:24 PM

Hi,
I need to find all shortest paths between two vertices, now to find them I iterate Dijkstra ntimes
deleting the prevoius path founded.
It' s too slow, can you say me if there'is something faster.
Thanks.
P.S.
Searching I found this Algo: K Shortest Paths
Do you know?




I used recursion and lists to build my paths. If my current vertex equals my starting vertex, I push the list of verticies into my results, the remove the last vertex from my current path and return. Eventually this covers all verticies from Vertex A to
B, and it avoids duplicates.
On Thu, Dec 11, 2008 at 9:09 AM, giomuti <notifications@codeplex.com> wrote:
From: giomuti
Hi,
I need to find all shortest paths between two vertices, now to find them I iterate Dijkstra ntimes
deleting the prevoius path founded.
It' s too slow, can you say me if there'is something faster.
Thanks.



Dec 11, 2008 at 6:55 AM
Edited Dec 11, 2008 at 7:34 AM

Can you post the code?Thanks..




Sorry, its code for work. Do some searching of the forums. You'll find an an algorithm that helped me, you'll just need to modify it to use the results from the Graph search.




Is this the algorithm:
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);
}
I' ve posted that. It's too slow for my
adjacency graph.
Someone knows k Shortest paths algo?



Coordinator
Dec 11, 2008 at 8:38 AM

Kshortest path are not implemented in QuickGraph. There are numerous papers describing various algorithms. All of them are nontrivial to implement.




Correct.
On Thu, Dec 11, 2008 at 9:27 PM, giomuti <notifications@codeplex.com> wrote:
From: giomuti
Is this the algorithm:
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);
}
I' ve posted that. It's too slow for my
adjacency graph.
Someone knows k Shortest paths algo?




Hi,
something new about kth shortest paths?
Thanks you for your patience.
Bye.



Coordinator
Dec 14, 2008 at 1:06 AM

kth shortest path is a hard problem. It's not clear when I will have the time to implement something for it.




ok, thanks.



Coordinator
Jan 5, 2009 at 9:52 PM

kshortest path have been implemented in quickgraph. See HoffmanPavley algorithm.

