[ b a c k t o i n d e x ]
package robot_graph;
import java.util.*;
import java.applet.*;
import java.awt.*;
/////////////////////////////////////////////////////////////////
// Graph Class - This class is the core class for the graph applet.
// this class contains the bfs search as well as the add vertices
// and edges methods.this class was inspired by another similar
// applet at:
// http://www.cs.strath.ac.uk/teaching/ug/classes/233/GraphDemo/
// GI.html
//
// Complied: 4/29/2000
// Last Modified: 8:00 PM 11/11/2000
// Modified by: William Martin
// Original Author: http://www.cs.strath.ac.uk
/////////////////////////////////////////////////////////////////
public class Graph {
private final int VERTEX_AREA = 50;//depend on yout hall width.
private Vector linePoints;
private String id;//this graphs id
public Vector vertices;//container for our vertices
public Vector edges;// container for our edges
private Color defaultColor = Color.black;//graph
private Color searchColor = Color.yellow;//search
private static int vertexNumber = 0;//how many verts
/////////////////////////////////////////////////////////////////
// Graph Method - this method is a contructor for the graph class.
// 1) give an id.
// 2) set up a vector to contain vertices and edges
//
// Last Modified: 4/29/2000
/////////////////////////////////////////////////////////////////
public Graph(String s){
id = s;
vertices = new Vector();
edges = new Vector();
}
/////////////////////////////////////////////////////////////////
// absdiff Method - this method is a a abs(difference) function
// essential for the findVertex Method.
//
// Last Modified: 4/29/2000
/////////////////////////////////////////////////////////////////
public int absdiff(int x, int y){
if (x<y)
return y-x;
else
return x-y;
}
/////////////////////////////////////////////////////////////////
// addEdge Method - this method adds an edge into the graph.
// RETURNS: an edge from vert.1 to vert.2.
//
// Last Modified: 4/29/2000
/////////////////////////////////////////////////////////////////
public Edge addEdge(Graphics g, Vertex v1, Vertex v2){
Edge e = new Edge(g,this,v1,v2);
return e;
}
/////////////////////////////////////////////////////////////////
// NON-PAINT
// addEdge Method - this method adds an edge into the graph.
// RETURNS: an edge from vert.1 to vert.2.
//
// Last Modified: 4/29/2000
// 11/28/2000 - made non-paint
/////////////////////////////////////////////////////////////////
public Edge addEdge(Vertex v1, Vertex v2){
Edge e = new Edge(this,v1,v2);
return e;
}
/////////////////////////////////////////////////////////////////
// addNewElement Method - this method is essential to pass vertices
// and edges into the container Vectors. These are treated as type
// Object.
//
// Last Modified: 4/29/2000
/////////////////////////////////////////////////////////////////
private void addNewElement(Vector v, Object e){
if (!v.contains(e))
v.addElement(e);
}
/////////////////////////////////////////////////////////////////
// NON - PAINT VERSION
// addVertex Method - this method adds a vertex into the graph.
// INCREMENTS: vertexNumber
// RETURNS: a new vertex @ coordinates x,y.
//
// landmark gives each vertex a scenerio.
//
// Date Created: 4/29/2000
// Last Modification: 10:58 AM 11/28/2000
/////////////////////////////////////////////////////////////////
public Vertex addVertex(int landmark, int x, int y){
vertexNumber++;
Vertex v = new Vertex(this,vertexNumber,landmark,x,y);
return v;
}
/////////////////////////////////////////////////////////////////
// PAINT VERSION
// addVertex Method - this method adds a vertex into the graph.
// INCREMENTS: vertexNumber
// RETURNS: a new vertex @ coordinates x,y.
//
// landmark gives each vertex a scenerio. Complete specs in
// Vertex.paint() method and DrawLandmark class.
//
// Date Created: 4/29/2000
// Last Modification: 10:58 AM 11/18/2000
/////////////////////////////////////////////////////////////////
public Vertex addVertex(Graphics g, int landmark,
int x,
int y){
vertexNumber++;
Vertex v = new Vertex(g,this,vertexNumber,landmark,x,y);
return v;
}
/**
* NON-PAINT VERSION
* This method is used to search out
* vertexs that may have the same x or y plane.
* If found than it is adjusted.
* If one such vertes is found than a boolean
* true is returned else false.
*
* Upgrade possibility: A good upgrade is to
* have the adjusted vertex an average of the
* two to be adjusted. To do this however a
* recursive must be used as the new address
* woulod require all vertexes to be adjusted.
* As it now stands the old vertex range or domain
* is adjusted to the new vertex domain or range.
*
* Creation date: (11/20/2000 4:23:30 PM)
* @param x int
* @param y int
*/
public boolean adjustAllVertex(int x, int y) {
Vertex v = null;
boolean found = false;
int vertexNumber, landmark;
for (int i = 0; i < vertices.size(); i++) {
v = (Vertex) vertices.elementAt(i);
vertexNumber = v.id();
landmark = v.landmark();
if(absdiff(x, v.xCoord()) < VERTEX_AREA){
vertices.removeElementAt(i);
v.xCoord= x;
vertices.add(i, v);
found = true;
}
else if(absdiff(y, v.yCoord()) < VERTEX_AREA){
vertices.removeElementAt(i);
v.yCoord= y;
vertices.add(i, v);
found = true;
}
}
return found;
}
/**
* This method is used to search out
* vertexs that may have the same x or y plane.
* If found than it is adjusted.
* If one such vertes is found than a boolean
* true is returned else false.
*
* Upgrade possibility: A good upgrade is to
* have the adjusted vertex an average of the
* two to be adjusted. To do this however a
* recursive must be used as the new address
* woulod require all vertexes to be adjusted.
* As it now stands the old vertex range or domain
* is adjusted to the new vertex domain or range.
*
* Creation date: (11/20/2000 4:23:30 PM)
* @param x int
* @param y int
* @param g Graphics
*/
public boolean adjustAllVertex(Graphics g, int x, int y) {
Vertex v = null;
boolean found = false;
int vertexNumber, landmark;
for (int i = 0; i < vertices.size(); i++) {
v = (Vertex) vertices.elementAt(i);
vertexNumber = v.id();
landmark = v.landmark();
if(absdiff(x, v.xCoord()) < VERTEX_AREA){
vertices.removeElementAt(i);
v.xCoord= x;
vertices.add(i, v);
found = true;
paint(g);
}
else if(absdiff(y, v.yCoord()) < VERTEX_AREA){
vertices.removeElementAt(i);
v.yCoord= y;
vertices.add(i, v);
found = true;
paint(g);
}
}
return found;
}
/**
* NON_PAINT VERSION
* This method is used to search out a
* vertex that may be near here and change
* that vertex to the average vertex address
* because they must be one in the same.
* If one such vertes is found than a boolean
* true is returned else false.
*
* Creation date: (11/20/2000 12:42:30 AM)
* @param x int
* @param y int
* @param g Graphics
*/
public boolean adjustedVertex(int x, int y) {
Vertex v = null;
boolean found = false;
int vertexNumber, landmark;
for (int i = 0; i < vertices.size(); i++) {
v = (Vertex) vertices.elementAt(i);
vertexNumber = v.id();
landmark = v.landmark();
if(absdiff(x, v.xCoord()) < VERTEX_AREA &&
absdiff(y, v.yCoord()) < VERTEX_AREA){
vertices.removeElementAt(i);
v.xCoord=((x+v.xCoord)/2);//average of the two x,s
v.yCoord=((y+v.yCoord)/2);//average of the two y,s
vertices.add(i, v);
found = true;
break;
}
}
return found;
}
/**
* PAINT VERSION
* This method is used to search out a
* vertex that may be near here and change
* that vertex to the average vertex address
* because they must be one in the same.
* If one such vertes is found than a boolean
* true is returned else false.
*
* Creation date: (11/20/2000 12:42:30 AM)
* @param x int
* @param y int
* @param g Graphics
*/
public boolean adjustedVertex(Graphics g, int x, int y) {
Vertex v = null;
boolean found = false;
int vertexNumber, landmark;
for (int i = 0; i < vertices.size(); i++) {
v = (Vertex) vertices.elementAt(i);
vertexNumber = v.id();
landmark = v.landmark();
if(absdiff(x, v.xCoord()) < VERTEX_AREA &&
absdiff(y, v.yCoord()) < VERTEX_AREA){
vertices.removeElementAt(i);
v.xCoord=((x+v.xCoord)/2);//average of the two x,s
v.yCoord=((y+v.yCoord)/2);//average of the two y,s
vertices.add(i, v);
paint(g);
found = true;
break;
}
}
return found;
}
/////////////////////////////////////////////////////////////////
// bfs Method - this method is a breth first search algorythm
// for this graph.
//
// while there is no more edges to explore
// explore next edge and mark it as visited
// while still more vertices
// explore next vertex
// if vertex is fresh
// mark it visited and continue on
//
// Last Modified: 4/29/2000
/////////////////////////////////////////////////////////////////
public void bfs(Vertex v) {
Vertex v1, v2;
Edge e;
Vector edgesToExplore = new Vector();
edgesToExplore.addElement(v);
while (!edgesToExplore.isEmpty()) {
v1 = (Vertex) edgesToExplore.elementAt(0);
edgesToExplore.removeElement(v1);
v1.setMark(true);
for (Enumeration E = v1.adjacentVertices();
E.hasMoreElements();) {
v2 = (Vertex) E.nextElement();
if (!v2.mark()) {
v2.setMark(true);
e = findEdge(v1, v2);
e.setMark(true);
e.setColor(searchColor);
e.flash();
pause();
edgesToExplore.addElement(v2);
}
}
}
}
public Color defaultColor(){return defaultColor;}
public Enumeration edges(){
return edges.elements();//so we can travers
}
/////////////////////////////////////////////////////////////////
// findEdge Method - this method checks for an edge and returns
// it. If not found than null.
//
// Last Modified: 4/29/2000
/////////////////////////////////////////////////////////////////
public Edge findEdge(Vertex v1, Vertex v2){
Edge e = null;
boolean found = false;
for (int i=0;i<edges.size() && !found;i++){
e = (Edge)edges.elementAt(i);
found = (v1.equals(e.v1()) && v2.equals(e.v2())) ||
(v1.equals(e.v2()) && v2.equals(e.v1()));
}
if (!found)
e=null;
return e;
}
/////////////////////////////////////////////////////////////////
// findLine Method - this method checks for an edge and returns
// it. If not found than null.
//
// Last Modified: 8:06 PM 11/11/2000
/////////////////////////////////////////////////////////////////
public String findLine(int x, int y) {
boolean found = false;
Edge e = null;
String str = new String("null");
for (int i = 0; i < edges.size() && !found; i++) {
e = (Edge)edges.elementAt(i);
if (e.isitThere(x, y)){
found = true;
str = e.id;
}
}
return str;
}
/////////////////////////////////////////////////////////////////
// findVertex Method - this method checks for an vertex and
// returns it. If not found than null.
//
// Last Modified: 4/29/2000
/////////////////////////////////////////////////////////////////
public Vertex findVertex(int x, int y) {
Vertex v = null;
boolean found = false;
for (int i = 0; i < vertices.size() && !found; i++) {
v = (Vertex) vertices.elementAt(i);
found = (absdiff(x, v.xCoord()) < 20 && absdiff(y, v.yCoord()) < 20);
}
if (!found)
v = null;
return v;
}
public String id(){return id;}
/////////////////////////////////////////////////////////////////
// info Method - this method returns a string with information
// on id and number of vertices.
//
// Last Modified: 4/29/2000
/////////////////////////////////////////////////////////////////
public String info(){
String s = "Graph:";
s = s + " " + id;
s = s + " n = " + vertices.size();
return s;
}
/////////////////////////////////////////////////////////////////
// paint Method - this method paints the vertices and edges in
// the graph.
//
// Last Modified: 4/29/2000
/////////////////////////////////////////////////////////////////
public void paint(){
for (int i=0;i<vertices.size();i++)
((Vertex)vertices.elementAt(i)).paint();
for (int i=0;i<edges.size();i++)
((Edge)edges.elementAt(i)).paint();
}
/////////////////////////////////////////////////////////////////
// paint Method - this method paints the vertices and edges in
// the graph but first unpaints the canvas.
//
// Date Built: 4/29/2000
// Date Modified: 8:52 AM 11/20/2000
/////////////////////////////////////////////////////////////////
public void paint(Graphics g){
//g.clearRect(0,0,800,600);
for (int i=0;i<vertices.size();i++)
((Vertex)vertices.elementAt(i)).paint();
for (int i=0;i<edges.size();i++)
((Edge)edges.elementAt(i)).paint();
}
/////////////////////////////////////////////////////////////////
// pause Method - this method puts the process thread to sleep
// momentarly. This method is essential for the visual bfs
// search
//
// Last Modified: 4/29/2000
/////////////////////////////////////////////////////////////////
public void pause(){
try{Thread.sleep(2);}
catch (Exception e) {e.printStackTrace();}
}
/////////////////////////////////////////////////////////////////
// pause Method - this method puts the process thread to sleep
// momentarly. The length of pause is defined by the incoming
// parameter l (length). This method is essential for the visual
// bfs search
//
// Last Modified: 4/29/2000
/////////////////////////////////////////////////////////////////
public void pause(long l){
try{Thread.sleep(l);}
catch (Exception e) {e.printStackTrace();}
}
/**
* Repaint!
* Creation date: (11/20/2000 6:01:26 PM)
*/
public void repaint() {
paint();
}
/////////////////////////////////////////////////////////////////
// reset Method - this method resets each vertex and edge in the
// graph.
//
// Last Modified: 4/29/2000
/////////////////////////////////////////////////////////////////
public void reset(){
for (int i=0;i<vertices.size();i++)
((Vertex)vertices.elementAt(i)).reset();
for (int i=0;i<edges.size();i++)
((Edge)edges.elementAt(i)).reset();
}
public Color searchColor(){return searchColor;}
public void setDefaultColor(Color color){
defaultColor = color;//vertexes and edges
}
public void setSearchColor(Color color){
searchColor = color;//for the visul bfs search
}
public Vector vectorOfEdges(){//container for our edges
return edges;
}
public Vector vectorOfVertices(){//container for our vertices
return vertices;
}
public Enumeration vertices(){ //with elements as Objects
return vertices.elements();//useful for our bfs search
}
}