<![CDATA[// DepthFirstSearch.java
//
// Copyright Mark Watson, 1998. Open Source and Open Content.
//
import java.util.Vector;
public class DepthFirstSearch extends SearchApplet {
public void init() {
// Define a test network before calling the super class 'init':
addNode("0", 0.0f, 0.0f);
addNode("1", 1.0f, 1.0f);
addNode("2", 5.0f, 2.0f);
addNode("3", 2.0f, 5.0f);
addNode("4", 7.0f, 5.0f);
addNode("5", 8.0f, 8.0f);
addNode("6", 10.0f, 5.0f);
addNode("7", 8.0f, 2.0f);
addNode("8", 12.0f, 8.0f);
addNode("9", 13.0f, 5.0f);
addLink(0,1);
addLink(1,2);
addLink(2,3);
addLink(2,4);
addLink(4,5);
addLink(4,6);
addLink(6,8);
addLink(8,9);
addLink(2,7);
addLink(7,9);
// Now that we have defined the network to search, we
// can now call the super class init:
super.init();
}
/** findPath - abstract method in super class */
public int [] findPath(int node_1, int node_2) { // return an array of node indices
System.out.println("Entered DepthFirstSearch.findPath(" +
node_1 + ", " + node_2 + ")");
num_path = 1;
path[0] = node_1; // the starting node
return findPathHelper(path, 1, node_2);
}
public int [] findPathHelper(int [] path, int num_path, int goal_node) {
System.out.println("Entered DepthFirstSearch.findPathHelper(...," +
num_path + ", " + goal_node + ")");
System.out.println("ici1");
repaintPath(path, num_path);
if (goal_node == path[num_path - 1]) {
int [] ret = new int[num_path];
for (int i=0; i<num_path; i++) ret[i] = path[i];
System.out.println("ici2");
repaintPath(ret);
return ret; // we are done!
}
int [] new_nodes = connected_nodes(path, num_path);
if (new_nodes != null) {
for (int j=0; j<new_nodes.length; j++) {
int [] new_path = copy_path(path, num_path);
new_path[num_path] = new_nodes[j];
int [] test = findPathHelper(new_path, num_path + 1, goal_node);
if (test != null) {
if (test[test.length - 1] == goal_node) {
//System.out.println("ici3");
//repaintPath(test);
return test;
}
}
}
}
return null;
}
public void repaintPath(int [] path, int num) {
int [] path2 = new int[2 * num + 1];
int count = 0;
for (int i=0; i<(num - 1); i++) {
path2[count++] = path[i];
path2[count++] = path[i+1];
}
super.repaintPath(path2, count);
}
protected int [] connected_nodes(int [] path, int num_path) {
// find all nodes connected to the last node on 'path'
// that are not already on 'path'
int [] ret = new int[SearchApplet.MAX];
int num = 0;
int last_node = path[num_path - 1];
for (int n=0; n<numNodes; n++) {
// see if node 'n' is already on 'path':
boolean keep = true;
for (int i=0; i<num_path; i++) {
if (n == path[i]) {
keep = false;
break;
}
}
boolean connected = false;
if (keep) {
// now see if there is a link between node 'last_node' and 'n':
for (int i=0; i<numLinks; i++) {
if (link_1[i] == last_node) {
if (link_2[i] == n) {
connected = true;
break;
}
}
if (link_2[i] == last_node) {
if (link_1[i] == n) {
connected = true;
break;
}
}
}
if (connected) {
ret[num++] = n;
}
}
}
if (num == 0) return null;
int [] ret2 = new int[num];
for (int i=0; i<num; i++) {
ret2[i] = ret[i];
}
return ret2;
}
private int [] path = new int[SearchApplet.MAX];
private int num_path = 0;
private int [] copy_path(int [] path, int num_to_copy) {
int [] ret = new int[SearchApplet.MAX];
for (int i=0; i<num_to_copy; i++) {
ret[i] = path[i];
}
return ret;
}
}
]]>
Back to main page