<![CDATA[// BreadthFirstSearch.java
//
// Copyright Mark Watson, 1998. Open Source and Open Content.
//
import java.util.Vector;
public class BreadthFirstSearch 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 */
// Breadth first search algorithm from "Algorithms"
// (Cormen, Leiserson, Rivest) page 460:
public int [] findPath(int node_1, int node_2) { // return an array of node indices
System.out.println("Entered BreadthFirstSearch.findPath(" +
node_1 + ", " + node_2 + ")");
if (node_1 == node_2) {
repaintPath(null, 0);
return null;
}
// data structures for depth first search:
boolean [] visitedFlag = new boolean[numNodes];
float [] distanceToNode = new float[numNodes];
int [] predecessor = new int[numNodes];
Queue queue = new Queue(numNodes + 2);
// data structures for graphical display (only):
int [] display_path = new int[2 * numNodes + 1];
int num_display_path = 0;
for (int i=0; i<numNodes; i++) {
visitedFlag[i] = false;
distanceToNode[i] = 10000000.0f;
predecessor[i] = -1;
}
visitedFlag[node_1] = true;
distanceToNode[node_1] = 0.0f;
queue.enqueue(node_1);
outer: while (queue.isEmpty() == false) {
int head = queue.head();
int [] connected = connected_nodes(head);
if (connected != null) {
for (int i=0; i<connected.length; i++) {
if (visitedFlag[connected[i]] == false) {
distanceToNode[connected[i]] = distanceToNode[head] + 1.0f;
predecessor[connected[i]] = head;
queue.enqueue(connected[i]);
display_path[num_display_path++] = head;
display_path[num_display_path++] = connected[i];
repaintPath(display_path, num_display_path);
if (connected[i] == node_2) break outer; // we are done
}
}
visitedFlag[head] = true;
queue.dequeue(); // ignore return value
}
}
// now calculate the shortest path from the predecessor array:
int [] ret = new int[numNodes + 1];
int count = 0;
ret[count++] = node_2;
for (int i=0; i<numNodes; i++) {
ret[count] = predecessor[ret[count - 1]];
count++;
if (ret[count - 1] == node_1) break; // back to starting node
}
num_display_path = 0;
int [] ret2 = new int[count];
for (int i=0; i<count; i++) {
ret2[i] = ret[count - 1 - i];
if (i > 0) { // re-calculate the plot display points:
display_path[num_display_path++] = ret2[i-1];
display_path[num_display_path++] = ret2[i];
}
}
// now re-calculate the display path points:
repaintPath(display_path, num_display_path);
return ret2;
}
// Queue algorithm from "Algorithms" (Cormen, Leiserson, Rivest) page 202:
protected class Queue {
public Queue(int num) {
queue = new int[num];
head = tail = 0;
len = num;
}
public Queue() {
this(400);
}
private int [] queue;
int tail, head, len;
public void enqueue(int n) {
queue[tail] = n;
if (tail >= (len - 1)) {
tail = 0;
} else {
tail++;
}
}
public int dequeue() {
int ret = queue[head];
if (head >= (len - 1)) {
head = 0;
} else {
head++;
}
return ret;
}
public boolean isEmpty() {
return head == (tail + 1);
}
public int head() {
return queue[head];
}
}
protected int [] connected_nodes(int node) {
int [] ret = new int[SearchApplet.MAX];
int num = 0;
for (int n=0; n<numNodes; n++) {
boolean connected = false;
// See if there is a link between node 'node' and 'n':
for (int i=0; i<numLinks; i++) {
if (link_1[i] == node) {
if (link_2[i] == n) {
connected = true;
break;
}
}
if (link_2[i] == 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