Originally Posted by Cudmore

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:

Help with Code Tags

Java Syntax (Toggle Plain Text)

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;
}

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: