Retrieving list from a map mapping to an arraylist

[Mitesh Parmar]

I have a map datastructure in which keys map to an arraylist. The values of the arraylists elements themselves are keys within the map.

For example:

Map List of previous keys
N ----------------> M
M ----------------> I, L
L ----------------> K
K ----------------> J
J ----------------> D
D ----------------> B
I ----------------> G
G ----------------> F,H
H ----------------> D
F ----------------> C
C ----------------> B
B ----------------> A

So from this we can see that to get from the end: N to the start: A
there are 3 possible routes:

N -> M -> I -> G -> F -> C -> B -> A
N -> M -> I -> G -> H -> D -> B -> A
N -> M -> L -> K -> J -> D -> B -> A

I need the above three routes returned in an ArrayList which are all held in a List : List routeCollections

The way to get this done involves recursion, I have the code written in Java but it does not work beyond creating the first route.

public void creatingRoutes(Object o, List singleRoute)
{
      //engine.getPredecessor simply returns a list of previous objects, as        //shown above
List listOfObjects = engine.getPredecessor(o);
 
int sizeOfPreviousObjects = listOfObjects.size();
 
if( sizeOfPreviousObjects > 1)
{
for(int i=0; i< listOfObjects.size(); i++)
{
List copyOfSingleRoute = new ArrayList(singRoute);

Object object = (Object) listOfObjects.get(i);
 
 
if(listOfObjects.indexOf(object) ==0)
{
singleRoute.add(object);
creatingRoutes(object, singleRoute);
}
 
else
{
copyOfSingleRoute.add(object);
creatingRoutes(object, copyOfSingleRoute);
}
}
}
 
else
{
 
Object objAtFirstElement = (Object)listOfObjects.get(0);
 
if(! objAtFirstElement.equals(firstObject))
{
singleRoute.add(objAtFirstElement);
creatingRoutes(objAtFirstElement, singleRoute);
 
else
{
singleRoute.add(firstObject);
Collections.reverse(singleRoute);
routeCollection.add(singleRoute);
}
}
}

This only works for the first run.

Please help...
[ September 03, 2004: Message edited by: Mitesh Parmar ]

[Stefan Wagner]

Your example looks like a tree to me.
But perhaps other examples are only (distinct) graphs:

A->B
C->D

or contain recursions:

A->B
B->C
C->A

And please edit your post and use code-tags.

[Mitesh Parmar]

Originally posted by Stefan Wagner:
Your example looks like a tree to me.
But perhaps other examples are only (distinct) graphs:

A->B
C->D

or contain recursions:

A->B
B->C
C->A

And please edit your post and use code-tags.

PLease could you tell me how to edit the code and add the code tags.
Thank You...

[Stefan Wagner]

On top of your posting is a icon-group.
One shows a piece of paper with a pencil.
That's for editing.

Before inserting code, you hit the code-button below the edit-window.
You insert your code between the two tags.
Here I inserted blanks into the tags, to make them visible:
[ CODE] show (example);[ /CODE]
Result without blanks:

  show (example);

You may add these tags manually.

[Stefan Wagner]

The code-tags make it much better readable - don't you think so?

But your question remains unresponded.
I have to correct myself - the data-structure isn't a tree, it's a directed graph.
I thought about it a while and tested some code but it isn't working properly.
To reconstruct your error, I would need the missing code at least.

I could send you my code - 136 rows in java-1.5 notation as private message. (Guess it's a bit much for the whole audience).

I get:

NMILKJDB
NMIGFHDB
NMIGFCB

, the 'A' allways missing, and the forking a step off.
But at least three lines.
[ September 03, 2004: Message edited by: Stefan Wagner ]

[Stefan Wagner]

Now I got a working approach - interested?