algorithm problem with recursion
 

I have an algorithm problem with recursion:

i have a route from A to D and it looks like this

[A, B, C, D]

the alphabet in the above list is an object of a class, lets call that class Nodes

each of this Nodes object they have some attributes... these are of type set..

the first set will store a bunch of other Nodes (these represent the current nodes neighbour)
the second set will store a bunch of tracks (Integer object representing what tracks the current nodes belong to)

(... bare with me here... )

so now i write up some code that initialise all the nodes... and here is the output...

A: [B, Z, E] // A's next neighbour

A: [2, 1, 3] // A belongs to these tracks

B: [C, A]        

B: [1]                

C: [B, D]

C: [4, 1]

D: [F, C]

D: [4]

and here is the code: (i removed the System.out... to shorten the code..)

public class Path {

    private Nodes a, b, c, d, e, f, z;

    private List path = new ArrayList();

    public Path() {

     

         a = new Nodes("A"); //used nodes

         b = new Nodes("B"); //used nodes

         c = new Nodes("C"); //used nodes

         d = new Nodes("D"); //used nodes

         e = new Nodes("E"); // wont be used directly

         f = new Nodes("F"); // wont be used directly

         z = new Nodes("Z"); // wont be used directly

         path.add(a);

         path.add(b);

         path.add(c);

         path.add(d);

         

        // setting Nodes a 

        a.getNext().add(b);

        a.getNext().add(e);

        a.getNext().add(z);



        Integer[] iA = {1, 2, 3};

        a.getTrackID().addAll(Arrays.asList(iA));



        // setting Nodes b 

        b.getNext().add(a);

        b.getNext().add(c);

        b.getTrackID().add(Integer.valueOf(1));



        // setting Nodes c 

        c.getNext().add(b);

        c.getNext().add(d); 

        c.getTrackID().add(Integer.valueOf(1));

        c.getTrackID().add(Integer.valueOf(4));



        // setting Nodes d 

        d.getNext().add(c);   

        d.getNext().add(f);   

        d.getTrackID().add(Integer.valueOf(4));



    }

    

    public static void main(String[] args) { new Path();}

}



class Nodes{

    private Set next = new HashSet();

    private Set trackID = new HashSet();

    private String name = "";

    Nodes(String name){ this.name = name;}

    public Set getNext() {   return next;} 

    public Set getTrackID() { return trackID;} 

    public String toString() {return this.name;}    

}

what i want to do is to come up with some recursive algorithm so that it would print out something like this...

        Path = A - B - C - D

        A to C track 1

        C to D track 4

so i've come up with a pseudo code...

method1(Node startNode, List path){



iterate through startNode.getNext set

        

 

        if nodes return is in the list path{

        

        newNodes = returned nodes;

        

        path.remove(startNodes);

        if(startNodes.getTrack() == newNodes.getTrack())

                { // if startNodes shares the same track as the next nodes 

                then line = the track;

                method1(newNodes, path);

                }else{

                   print startNode "to" newNodes "track" line

                        if there is still some journey

                                method(newNodes, path)        

                }



        

        }



}

i've also come up with an actuall code but for some reason it'll only prints out the first step...

the code for this to follow...

Re: algorithm problem with recursion
 

Is it just me, but I don't get what you're doing at all.

Re: algorithm problem with recursion
 

:!: Hey "fdrage",

I think u r not very clear wat r u doing or if I have misunderstood u r not able to say clearly wat do u wanna say actually.

If u dont mine can u just make it more clear and understandable.

Bye,
Live and Let Live!!!

Re: algorithm problem with recursion
 

I think I may know what you're talking about, as I faced the apparent issue myself just last week. It was quite something. If I've misunderstood and all the following information is unrelated, then I guess I'm just practicing my explanatory skills.

Basically, you have Nodes, and each Node can have some number of links to other Nodes. You want a function to find the quickest rout through the network from one Node to another, by searching for a the second Node recursively, starting at the first Node.

Think of it in terms of traffic:
http://i12.photobucket.com/albums/a2...rums/Paths.gif
Someone is at the Green house, and wants to find their way to the Red house. Each Blue block is an intersection, and they're linked by roads. You want a method to determine the shortest path the person could follow, from which node to which node until they reach their destination. In the example I've provided (I quickly marked it up, excuse the sloppiness) the fastest rout would be Green - A - B - E - Red, right? There are many options, such as ACDE, ACDBE, ABDE, ABDCABE, etc etc etc, but the shortest is ABE.

Now, to get your program to search for the Red house, it will work its way out from the Green house and search up and down streets recursively.

Each House is a Node, and the Blue intersections are Nodes as well. As I've mentioned, Nodes have links, and the link-tree for this network would look like:

Green house: A
Red house: E
A: B, C, Green house
B: A, D, E
C: A, D
D: B, C, E
E: B, D, Red house

The program will work its way out from the Green house, checking its children (its links) for the Red house, and if the Red house is not found, the program moves one step further into the network, checking the Nodes of the Nodes it just checked. Complicated? Yes, and No.

One major issue is that the roads loop back, so theoretically, if the program just checks a Node's children and then checks the grandchildren, and then the great-grandchildren, and so on, it will throw its self into an infinite loop and continue to come back and re-check the same nodes over and over again. We have to prevent this from happening. The way I did this, was that I kept a Binary Hash Tree of the Nodes already checked, and I only considered a Node if it hadn't already been looked at.

Here's what the program would do while searching for the Red house:
(Bold is the children that were returned to be checked. Only those which haven't previously been checked are included)

{Green house} does not include Red house, (take children)
{A} does not include Red house, (take children)
{B, C} does not include Red house, (take children)
{D, E} does not include Red house, (take children)
{Red house} includes Red house!

If you understand the logic by now, then good. Write some new Psudo-Code and think your way through the extensive process of writing the Java. Here are the methods I wrote to help me complete the task. Though I haven't included the code for all of my methods, maybe the following can provide some additional clues:

public Node CheckLevelRecusrive (Node FromNode, Node ToNode);

private Node CheckLevel (Node[] Choices, Node SearchForMe);

private Node[] ReturnLevelChildren (Node[] Parents);



// =========================



private Object HashLock = new Object (); // Used to lock the Hash table

private BHI HashesCheckedRoot = null; // Prevent search back-tracking/blocking

        

private class BHI { // Binary Hash Item

        int HashVal;

        BHI LessThanMe, MoreThanMe; // Used in Binary Search

        public BHI (int Hash) { HashVal = Hash; }

}



private boolean FindOrAddHash (int Hash) {

        // Search for an existing hash entry which matches NewHash

        // Return true if found, false if not

        // If not found, add Hash to HashesCheckedRoot table

        // ----------

        BHI ParentBHI = null;

        BHI CurrentBHI = HashesCheckedRoot;

        // ----------

        // STEP 1: Search for the Hash record

        while (CurrentBHI != null) {

                if (CurrentBHI.HashVal == Hash) return true; // Found

                ParentBHI = CurrentBHI;

                CurrentBHI = (Hash < CurrentBHI.HashVal) ? CurrentBHI.LessThanMe : CurrentBHI.MoreThanMe;

        }

        // ----------

        // STEP 2: Not found, Insert Hash at ParentBHI

        if (ParentBHI == null) HashesCheckedRoot = new BHI (Hash);

        else if (Hash < ParentBHI.HashVal) ParentBHI.LessThanMe = new BHI (Hash);

        else ParentBHI.MoreThanMe = new BHI (Hash);

        // -----

        return false;

}

I hope I've been at least somewhat helpful :rolleyes:

Re: algorithm problem with recursion
 

Ah so basically he/she's trying to find a shortest path algo of which there are many to choose from.