carfield.com.hk

AbstractGraphSearch.java

2002-01-20T16:00:00Z

import java.util.Vector;

abstract public class AbstractGraphSearch {

public void addNode(String name, int x, int y) {
	System.out.println("Adding node: " + name + ", " + x + ", " + y);
	nodeNames[numNodes] = name;
	node_x[numNodes] = x;
	node_y[numNodes] = y;
	numNodes++;
    }

public int getNumNodes() { return numNodes; }
    public int getNumLinks() { return numLinks; }

public String getNodeName(int index) {
	try {
	    return nodeNames[index];
	} catch (Exception e) {
	    System.out.println("Error in getNodeName: " + e);
	}
	return "no name"; // error condition
    }

public int getNodeX(int index) {
	try {
	    return node_x[index];
	} catch (Exception e) {
	    System.out.println("Error in getNodePosition: " + e);
	}
	return 0;  // error condition
    }

public int getNodeY(int index) {
	try {
	    return node_y[index];
	} catch (Exception e) {
	    System.out.println("Error in getNodePosition: " + e);
	}
	return 0;  // error condition
    }

public int getLink1(int index) {
      return link_1[index];
    }

public int getLink2(int index) {
      return link_2[index];
    }

public void addLink(int node1, int node2) {
	link_1[numLinks] = node1;
	link_2[numLinks] = node2;
	int dist_squared =
	    (node_x[node1] - node_x[node2]) * (node_x[node1] - node_x[node2]) +
	    (node_y[node1] - node_y[node2]) * (node_y[node1] - node_y[node2]);
	lengths[numLinks] = (int)Math.sqrt(dist_squared);
	numLinks++;
    }

public void addLink(String name1, String name2) {
	int index1 = -1, index2 = -1;
	for (int i=0; i<numNodes; i++) {
	    if (name1.equals(nodeNames[i])) index1 = i;
	    if (name2.equals(nodeNames[i])) index2 = i;
	}
	if (index1 != -1 && index2 != -1)  addLink(index1, index2);
    }

/** findPath - abstract method that is defined in subclasses */
    abstract public int [] findPath(int start_node, int goal_node); // return an array of node indices

protected int getNodeIndex(String name) {
	for (int i=0; i<numNodes; i++) {
	    if (name.equals(nodeNames[i])) return i;
	}
	return -1; // error condition
    }

final public static int MAX = 50; // max number of nodes and max number of links

protected int [] path = new int[AbstractGraphSearch.MAX];
    protected int num_path = 0;

// for nodes:
    protected String [] nodeNames = new String[MAX];
    protected int [] node_x = new int[MAX];
    protected int [] node_y = new int[MAX];
    // for links between nodes:
    protected int [] link_1 = new int[MAX];
    protected int [] link_2 = new int[MAX];
    protected int [] lengths = new int[MAX];

protected int numNodes = 0;
    protected int numLinks = 0;

protected int goalNodeIndex = -1, startNodeIndex = -1;

}

BreadthFirstSearch.java

2002-01-20T16:00:00Z

public class BreadthFirstSearch extends AbstractGraphSearch {

/** findPath - abstract method in super class */
    public int [] findPath(int start_node, int goal_node) { // return an array of node indices
	System.out.println("Entered BreadthFirstSearch.findPath(" +
			   start_node + ", " + goal_node + ")");
	// data structures for depth first search:
	boolean [] alreadyVisitedFlag = new boolean[numNodes];
	int [] predecessor = new int[numNodes];
	IntQueue queue = new IntQueue(numNodes + 2);

for (int i=0; i<numNodes; i++) {
	    alreadyVisitedFlag[i] = false;
	    predecessor[i] = -1;
	}

alreadyVisitedFlag[start_node] = true;
	queue.addToBackOfQueue(start_node);
outer:	while (queue.isEmpty() == false) {
	    int head = queue.peekAtFrontOfQueue();
	    int [] connected = connected_nodes(head);
	    if (connected != null) {
		for (int i=0; i<connected.length; i++) {
		    if (alreadyVisitedFlag[connected[i]] == false) {
			predecessor[connected[i]] = head;
			queue.addToBackOfQueue(connected[i]);
			if (connected[i] == goal_node) break outer; // we are done
		    }
		}
		alreadyVisitedFlag[head] = true;
		queue.removeFromQueue(); // ignore return value
	    }
	}
	// now calculate the shortest path from the predecessor array:
	int [] ret = new int[numNodes + 1];
	int count = 0;
	ret[count++] = goal_node;
	for (int i=0; i<numNodes; i++) {
	    ret[count] = predecessor[ret[count - 1]];
	    count++;
	    if (ret[count - 1] == start_node)  break;  // back to starting node
	}
	int [] ret2 = new int[count];
	for (int i=0; i<count; i++) {
	    ret2[i] = ret[count - 1 - i];
	}
	return ret2;
    }

protected class IntQueue {
	public IntQueue(int num) {
	    queue = new int[num];
	    head = tail = 0;
	    len = num;
	}
	public IntQueue() {
	    this(400);
	}
	private int [] queue;
	int tail, head, len;
	public void addToBackOfQueue(int n) {
	    queue[tail] = n;
	    if (tail >= (len - 1)) {
		tail = 0;
	    } else {
		tail++;
	    }
	}
	public int removeFromQueue() {
	    int ret = queue[head];
	    if (head >= (len - 1)) {
		head = 0;
	    } else {
		head++;
	    }
	    return ret;
	}
	public boolean isEmpty() {
	    return head == (tail + 1);
	}
	public int peekAtFrontOfQueue() {
	    return queue[head];
	}
    }

protected int [] connected_nodes(int node) {
	int [] ret = new int[AbstractGraphSearch.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;
    }

}

DepthFirstSearch.java

2002-01-20T16:00:00Z

public class DepthFirstSearch extends AbstractGraphSearch {

/** findPath - abstract method in super class */
    public int [] findPath(int start_node, int goal_node) { // return an array of node indices
        System.out.println("Entered DepthFirstSearch.findPath(" +
                           start_node + ", " + goal_node + ")");
        path[0] = start_node;
        return findPathHelper(path, 1, goal_node);
    }

public int [] findPathHelper(int [] path, int num_path, int goal_node) {
        System.out.println("Entered DepthFirstSearch.findPathHelper(...," +
                           num_path + ", " + goal_node + ")");
        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];
            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++) {
                path[num_path] = new_nodes[j];
                int [] test = findPathHelper(path, num_path + 1, goal_node);
                if (test != null) {
                    if (test[test.length - 1] == goal_node) {
                        return test;
                    }
                }
            }
        }
        return null;
    }

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[AbstractGraphSearch.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;
    }

}

GraphBreadthFirstSearch.java

2002-01-20T16:00:00Z

import javax.swing.*;
import java.awt.*;

public class GraphBreadthFirstSearch extends JFrame {
  JPanel jPanel1 = new JPanel();

public GraphBreadthFirstSearch() {
    BreadthFirstSearch engine = new BreadthFirstSearch();
	  // Define a test network before calling the super class 'init':
	  engine.addNode("0", 20, 40);
	  engine.addNode("1", 60, 60);
	  engine.addNode("2", 100, 40);
	  engine.addNode("3", 50, 110);
	  engine.addNode("4", 140, 80);
	  engine.addNode("5", 160, 150);
	  engine.addNode("6", 200, 80);
	  engine.addNode("7", 160, 40);
	  engine.addNode("8", 240, 120);
	  engine.addNode("9", 260, 90);

engine.addLink(0,1);
	  engine.addLink(1,2);
	  engine.addLink(2,3);
	  engine.addLink(2,4);
	  engine.addLink(4,5);
	  engine.addLink(4,6);
	  engine.addLink(6,8);
	  engine.addLink(8,9);
	  engine.addLink(2,7);
	  engine.addLink(7,9);
          System.out.println("Before calculating path");
          path = engine.findPath(0, 9);
          System.out.println("After calculating path:");
          for (int i=0; i<path.length; i++) {
            System.out.println("  node # " + path[i]);
          }
          this.engine = engine;
    try {
      jbInit();
    }
    catch(Exception e) {
      e.printStackTrace();
    }
  }
  private int [] path = null;
  private BreadthFirstSearch engine = null;

public static void main(String[] args) {
    GraphBreadthFirstSearch graphBreadthFirstSearch1 = new GraphBreadthFirstSearch();
  }

private void jbInit() throws Exception {
    this.setDefaultCloseOperation(3);
    jPanel1.setBackground(Color.white);
    this.getContentPane().add(jPanel1, BorderLayout.CENTER);
    this.setSize(290, 180);
    this.setVisible(true);
  }
    protected void paintNode(Graphics g, String name, int x, int y) {
	int len = name.length() * 10 + 6;
	int x1 = x - (len / 2);
	int x2 = x + (len / 2);
	int y1 = y - 10;
	int y2 = y + 10;
	g.setColor(Color.cyan);
	g.fill3DRect(x1, y1, len, 20, true);
	g.setColor(Color.black);
	g.drawString(name, x1 + 4, y2 - 6);
    }

public void paint(Graphics g) {
	super.paint(g);
	if (engine != null && path != null) {
            int numNodes = engine.getNumNodes();
            int numLinks = engine.getNumLinks();
            for (int i=0; i<numLinks; i++) {
               int l1 = engine.getLink1(i);
               int l2 = engine.getLink2(i);
               int x1 = engine.getNodeX(l1);
               int y1 = engine.getNodeY(l1);
               int x2 = engine.getNodeX(l2);
               int y2 = engine.getNodeY(l2);
               g.setColor(Color.lightGray);
               g.drawLine(x1, y1, x2, y2);
            }
            for (int i=1; i<path.length; i++) {
               int x1 = engine.getNodeX(path[i-1]);
               int y1 = engine.getNodeY(path[i-1]);
               int x2 = engine.getNodeX(path[i]);
               int y2 = engine.getNodeY(path[i]);
               g.setColor(Color.black);
               g.drawLine(x1, y1, x2, y2);
            }
            for (int i=0; i<numNodes; i++) {
               int x1 = engine.getNodeX(i);
               int y1 = engine.getNodeY(i);
               paintNode(g, engine.getNodeName(i), x1, y1);
            }
        }
    }

}

GraphDepthFirstSearch.java

2002-01-20T16:00:00Z

import javax.swing.*;
import java.awt.*;

public class GraphDepthFirstSearch extends JFrame {
  JPanel jPanel1 = new JPanel();

public GraphDepthFirstSearch() {
    DepthFirstSearch engine = new DepthFirstSearch();
	  // Define a test network before calling the super class 'init':
	  engine.addNode("0", 20, 40);
	  engine.addNode("1", 60, 60);
	  engine.addNode("2", 100, 40);
	  engine.addNode("3", 50, 110);
	  engine.addNode("4", 140, 80);
	  engine.addNode("5", 160, 150);
	  engine.addNode("6", 200, 80);
	  engine.addNode("7", 160, 40);
	  engine.addNode("8", 240, 120);
	  engine.addNode("9", 260, 90);

public static void main(String[] args) {
    GraphDepthFirstSearch graphDepthFirstSearch1 = new GraphDepthFirstSearch();
  }

}