Click here to Skip to main content
15,881,803 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 3-Mar-11 23:37pm
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?
 
Share this answer
 
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
Sergey Alexandrovich Kryukov 4-Mar-11 11:59am    
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).
Some different algorithms here. Your choice if you find those efficient.

http://msdn.microsoft.com/library/ms379574.aspx
 
Share this answer
 

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