File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Java in General and the fly likes Algorithm � Find all the available paths in a graph Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "Algorithm � Find all the available paths in a graph" Watch "Algorithm � Find all the available paths in a graph" New topic
Author

Algorithm � Find all the available paths in a graph

avihai marchiano
Ranch Hand

Joined: Jan 10, 2007
Posts: 342
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
(instanceof Sidekick)
Ranch Hand

Joined: Jan 29, 2003
Posts: 8791
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 ...

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


A good question is never answered. It is not a bolt to be tightened into place but a seed to be planted and to bear more seed toward the hope of greening the landscape of the idea. John Ciardi
avihai marchiano
Ranch Hand

Joined: Jan 10, 2007
Posts: 342
I think this is DFS
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Algorithm � Find all the available paths in a graph