Algorithm � Find all the available paths in a graph

[avihai marchiano]

Hey,

I need to find all the available paths from a root object.
Since in java objects can have references in the two directions, we are talking on a graph.

I want to get a reference to a class type and return a list of all the available paths from this object type.
If I have a reference from A->B->C->D and also A->D I need to have the two paths.

Performance is not important because this process run in offline. Simplicity is much important.

Can you please advice on the suitable algorithm for this?

Thank you

[Stan James]

Are you comfortable with recursion? You can make a "brute force" routine to try every path and report the ones that get to "D". Off the top of my head, no verification, something like ...

main()
{
   visitNode( "", first )
}
 
visitNode( path, node )
{
   path = path + node.name
   if node.name is "D"
      print path 
   else
      for each child of node
         visitNode( path, child )
      next
   end if
}

See if you can make that run in Java, show us your code, and we'll talk about some optimizations.

[avihai marchiano]

I think this is DFS

[avihai marchiano]

I will explain my main goal and it will explain more why i have problem with simple DFS

My goal is to know what is the paths to an Object.

if i create a paths wil DSF i will have see that object B have a lot of paths, because i have :
A->B
A->B->C
A->B->C->D

I need some how to organize the path in order to get a result of 1 path for the example i show above.

Thank you

[Stefan Wagner]

Is this a directed graph?

Your arrows suggest so.
Else, you could run into a problem, if you have:
a-b-c-d
and
a-d

this could lead to a-b-c-d-a-b-c-d-a .... infinite loops.

Else, I would see Stans suggestion as valid.

[Jim Yingst]

Is DFS a depth-first search, or something else?

Originally you said you wanted to find all paths from a root object. Now you say you want to find one. Which one? The shortest? (There may be more than one with equal length.) Or is there some other way to tell which one path is the answer?

[avihai marchiano]

The graph is objects in java, so it is indirect.
there is no problem to run DFS (Depth First Serach)because it support circles.

i want to find all paths that are avilable to a certain object from the root (but in need to find it on all objects).

if i print the paths like this:
A->B
A->B->C
A->B->C->D


and than i go to the result and ask what are the avilable paths to B, i get 3 avilable paths, but it is not correct because as you see i have only one.

tahnk you

[Jim Yingst]

OK, I see. But isn't that solved by the algorithm Stan gave? He was talking about finding all paths to D, and you're talking about paths to B, but the idea is the same.

   if node.name is "D"
      print path 
   else
      for each child of node
         visitNode( path, child )
      next
   end if

If the node is "D" (or "B" for your example), print the path. And you only execute the remaining code, the code that calls visitNode() for subsequent nodes, if the current nod e is not D (or B in your example). So you shouldn't get any paths that go from D (or B) to some other node. Or am I missing something?

[avihai marchiano]

Yes, you missed.

I need all the avilable paths to all nodes from the root.

DFS can give you all the paths, but DFS also will give you duplicates paths that are the same.

I want to get the avilable paths to B
to C
to D
and etc

But,
A->B
A->B->E->F...

considers as the same path.

This is not the same path:
A->B
A->C->B

[Stan James]

Can you iterate the nodes and run DFS with each one as a target? When you draw B as the target you'll get A-B and A-C-B. When you draw D as the target you'll get A-B-D and A-C-B-D. I suppose you could even run for all possible combinations of start node and target node. I was careful to make my recursion handle "find the path from A to A"
[ August 30, 2007: Message edited by: Stan James ]