Recursive calls, arraylists, and object passing

[nooneinparticular314159]

I'm doing a depth first search and want to record the least cost path
as I traverse the graph. I create an arraylist. I want to add things
to teh arraylist in a recursive call to teh function where teh
arraylist is created. When the recursion returns, the original
arraylist should be unchanged, but I should be able to return a copy of
the new arraylist with all the changes made.
For some reason, I can't get this to work. If I pass in the arraylist
each time, I wind up with an arraylist with ALL paths recorded on it,
which is not what I want. If I create a new arraylist inside my
recursive method, I am unable to build on the original. I want each
recursion to add on the new nodes on the path, and to return the path
if it reaches the destionation. But I need to iterate over all
possible branches from each node, so I don't want to destroy the state
of the original before each recursive call. Any idea what I can do?

Thanks!

 

[Abrasive Sponge]

I'm doing a depth first search and want to record the least cost path
as I traverse the graph. I create an arraylist. I want to add things
to teh arraylist in a recursive call to teh function where teh
arraylist is created. When the recursion returns, the original
arraylist should be unchanged, but I should be able to return a copy of
the new arraylist with all the changes made.
For some reason, I can't get this to work. If I pass in the arraylist
each time, I wind up with an arraylist with ALL paths recorded on it,
which is not what I want. If I create a new arraylist inside my
recursive method, I am unable to build on the original. I want each
recursion to add on the new nodes on the path, and to return the path
if it reaches the destionation. But I need to iterate over all
possible branches from each node, so I don't want to destroy the state
of the original before each recursive call. Any idea what I can do?

Thanks!

"When the recursion returns, the original
arraylist should be unchanged, but I should be able to return a copy of
the new arraylist with all the changes made."


why create an arraylist if you are not going to use it?

 

[Daniel Cer]

A couple things....

If you're interested in the least cost path between any two nodes in a
graph, depth first search is not the way to go.

This is because, there is no guarantee that a path between any two nodes
that is discovered by depth first search will be optimal. If the cost of
traversing all the links between the nodes is identical, you could find
an optimal path using breadth-first search (BFS). However, if the cost
of the links in the graph varies, then you could find an optimal path
using a uniform-cost search. This is algorithm is vaguely similar to
BFS, with the FIFO queue in BFS being replaced by a priority queue
ordered by the cost of each path so far.

Okay, and now onto you specific question....

I want to add things
to teh arraylist in a recursive call to teh function where teh
arraylist is created. When the recursion returns, the original
arraylist should be unchanged, but I should be able to return a copy

For this, I don't see why something like the following wouldn't work:

ArrayList someDFSMethod(ArrayList originalList) {
ArrayList workingList = new ArrayList(originalList);

/* misc. to perform the search code */

if (foundPath) return workingList;
else return null;
}

Notice that at the beginning of the method, workingList is initialized
to be a copy of the originalList. So, you can then operate over the
workingList in the body of the method without having to worry about
disrupting originalList. When the method, is done, it then returns the
workingList, if it actually represents a path to the destinate node
(presumably, letting it get garbage collected otherwise).

Hope that helps. Also, if you're still having problems, could you post a
snippet of the actually code you're using?

-Dan

 

[nooneinparticular314159]

Well, I am going to use it. But I want paths to build on n distinct
copies of the Path - one for each path taken. Basically, I want a
global Path that contains the best one found so far, and a local path
that is only visible in the scope that it is being used in. So in each
call to findoptimalpath, I want a new copy of the Path containing
everything that has been found so far.