Click here to Skip to main content
15,126,209 members
Please Sign up or sign in to vote.
4.00/5 (2 votes)
See more:
Hello,

I'm trying to retrieve all simple paths between two given nodes in an undirected graph, using depth first search.
My real problem is it is unusable in production due to a too long computation time, even in small graphs (100 vertices but with tons of edges in every ways), it quickly take more an hour.

My algo is the following:
C#
public ICollection<MyObject[]> FindPaths(MyObject sourceObject, MyObject targetObject)
{
    ICollection<MyObject[]> paths = new Collection<MyObject[]>();

    Stack<MyObject> visited = new Stack<MyObject>();
    visited.Push(sourceObject);

    AllSimplePathsDepthFirstSearch(visited, targetObject, paths);

    return paths;
}

private void AllSimplePathsDepthFirstSearch(Stack<MyObject> visited, MyObject target, ICollection<MyObject[]> paths)
{
    MyObject lastVisited = visited.Peek();

    //Explore adjacent edges
    IEnumerable<TaggedEquatableEdge<MyObject, MyRelation> edges = _graph.AdjacentEdges(lastVisited);
    foreach (TaggedEquatableEdge<MyObject, MyRelation> edge in edges)
    {
        MyObject linkedVertice = lastVisited == edge.Source ? edge.Target : edge.Source;
        if (visited.Contains(linkedVertice))
        {
            continue;
        }
        else if (linkedVertice.Equals(target))
        {
            visited.Push(linkedVertice);
            paths.Add(visited.ToArray().Reverse().ToArray());
            visited.Pop();
            continue;
        }
        visited.Push(linkedVertice);
        AllSimplePathsDepthFirstSearch(visited, target, paths);
        visited.Pop();
    }
}



Do somebody know a better approach, or how i could optimize this....

Thanks in advance for your help.
Posted
Updated 4-Mar-11 0:37am
v2
Comments
Piccadilly Yum Yum 4-Mar-11 7:10am
   
Try working with adjacency matrix ...

This problem is NP-hard. Hundred vertices is enough to make any implementation run almost forever (until it runs out of memory) because it needs to compute way too many things.
<br />
| /*\ /*\ /*\ /*\ /*\ /*\ /*\ /*\ /*\ /*\ /*\ /*\ /*\<br />
|S---*---*---*---*---*---*---*---*---*---*---*---*---T<br />
| \*/ \*/ \*/ \*/ \*/ \*/ \*/ \*/ \*/ \*/ \*/ \*/ \*/<br />
The number of simple paths in the 40-vertex graph above is 3^13, or 1,594,323. With 100 vertices it has a potential of going into trillions!

P.S. Why do you need all paths, anyway?
   
Comments
Yan09 4-Mar-11 8:08am
   
Hi dasblinkenlight,

ok now i understand why it's so long...

For your question: Why do you need all paths, anyway? :
The user has to choose between one of the possible path in a list (to each path, tons of informations, statistiques and so on are added), but you're right, it's a non sense to present 1,594,323 results to a user, because it will not be exploitable....

But:
I was also using all returned paths to restrict my graph to vertices that are between source and target (if it is in a simple path, it's between the two vertices), and i think it's there i'm not right in my aproach.....
So how could i, for a given graph, a source vertex and a target vertex, extract a subgraph that contains only vertices that are between source and taget
   
It is absolutely unclear why providing the user with any paths at all. Even it it is quick, why the user needs more results than number of available nodes? Something is fundamentally wrong in formulation of the goals, which you still don't explain.
--SA
dasblinkenlight 4-Mar-11 8:38am
   
In an undirected graph, "vertices that are between source and target" are such vertices to which there exist non-overlapping paths from the source and from the target. You can check for paths to not overlap by finding <a href="http://www.ibluemojo.com/school/articul_algorithm.html">articulation points</a>. However, the problem you are trying to solve is fundamentally hard. The best way to approach something like that would be to provide user results as you find them. For example, once you get 10 results, show them to the users. If they see an item that satisfies their criteria, you are done. If not, they'd click [Next] and you'd continue searching. The key here would be to search in a smart way, whatever it may mean in your case. Is there a particular statistics they'd wish to maximize? Show the paths that maximize it first. Do they look prefer shorter paths? Show shorter paths ahead of the longer ones. And so on.
Yan09 4-Mar-11 10:07am
   
This is really annoying.....cause the user absolutely want to enter a start point, a destination point and generate a visual graph containing all elements between theses twoo....
When you say: ...to which there exist non-overlapping paths from the source and....., i don't understand this, cause it means that for each vertices, i had to find all paths to source and paths to target, to be able to test if it exist non-overlapping ones, and finding paths is justly the problem....
dasblinkenlight 4-Mar-11 10:41am
   
You can be sure that non-overlapping paths exist without finding all paths. Start by analyzing articulation points in your graph. Find all articulation points (see link above), and then for each articulation point [A] check if the source [S] and the target [T] remain connected when [A] is removed. If removal of [A] does not disconnect [S] from [T], remove [A] and all its edges. The reason this can be done is that [S] and [T] are "on the same side" of [A]; any path from a vertex [X] on the other side of [A] must go through [A] to reach either [S] or [T], meaning that non-overlapping paths do not exist. All vertices connected to [S] and [T] after the algorithm has finished are between [S] and [T]. This algorithm is polynomial - it's complexity is roughly O(V*E).
   
Correct answer, my 5
--SA
Yan09 7-Mar-11 6:01am
   
Hi dasblinkenlight,
imagine this:
1---2---S
\ /
T
If i follow the given logic: 2 is an articulation point, removing 2 do not disconnect S from T, so i should remove it, but removing 2 do remove one path from s to t (S-2-T)...
So this logic do not seem to keep all nodes between s and t......or am i still not understanding something?
dasblinkenlight 7-Mar-11 6:26am
   
I see - the algorithm covers paths [S]-[A]-[X]-[...]-[A]-[T], but I forgot about the case when there's no [X] in between (i.e. [S]-[A]-[T]). To cover it, you can go through the list of articulation points before removing any edges, and create a list of all articulation points reachable from both [S] and [T]. Then add these articulation points back after running the algorithm.
Yan09 7-Mar-11 7:59am
   
Hmmmmmm.....sorry, but i don't understand your solution.....
What did you mean by: reachable from both [S] and [T]. (A neighboor of S and T????, if it is what when [S]-[X]-[A]-[X]-[T])

If you have the time and if it do not annoy you, i would appreciate if you could explain me it kleaver, because i'm lost... and i'm really sorry ;-)
dasblinkenlight 7-Mar-11 10:17am
   
[X] is reachable from [S] means there is a path from [X] to [S]. If your graphs are connected, it's true for all nodes (but I don't know if your graphs are connected). [S]-[A]-[X]-[A]-[T] means a path that goes from [S] to [T] through [X], but it must go through an articulation point [A] two times in order to go through [X] (therefore, [X] is not between [S] and [T]).
Still, it's only a sketch of an algorithm. By adding back some of non-disconnecting articulation points you may get a few nodes (from among the articulation points you added back) that are not between [S] and [T]. Weeding them out may be a bit tricky - I don't have much time to think about it, but I hope implementing a solution would give you some additional insights.
Yan09 8-Mar-11 4:01am
   
Ok, i see and have an idea of what to do...
Thank you very very very much for all your advises, knowledges sharing and patience to help me achieve my goals.
Some different algorithms here. Your choice if you find those efficient.

http://msdn.microsoft.com/library/ms379574.aspx
   

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)




CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900