The Graph class is designed primarily to store and retrieve Edge and Vertex objects. But a Graph can also draw itself, determine if any Edge or Vertex contains a given (x,y) coordinate, mark an Edge or Vertex as having beenSelected(), reconstruct itself from a string, and convert all Edge and/or Vertex objects of a given color to a new color.
The Graph class uses two Java util package HashTable objects to handle storage. The built in hashing method provided by the String class is used to generate a hash code. For Vertex objects, the hash code is the hash code of the String representation of the vertex number. For Edge objects, the String representation of the two vertex numbers separated by a space provides a hash code. For example, the hash code for vertex number 3 is the hashcode of the String ``3''. The hash code for a 3,5 edge is the hashcode for the String ``3 5''. The Java HashTable objects grow dynamically, and provide constant average time complexity storage and retrieval. And because the HashTable class implements the Enumeration interface, it is a simple matter to use a HashTable enumeration to create an array of all the Edge or Vertex objects currently in a Graph. The edge() and vertices() methods return such arrays for external use, and every invocation produces a new array. The p_edges() and p_vertices() methods are used internally, and use a lazy allocation method to produce the arrays. That is, the p_edge() and p_vertices() methods check to see if the last array they returned is still valid, and they only allocate new arrays if Edge or Vertex objects have been added or deleted from the Graph. Since the Graph never modifies the array itself, this saves allocation calls and reduces work for the garbage collector.
When a Graph draws itself, it can either draw every Edge and Vertex or only the currently transient or stationary portion. The GraphPanel uses this ability to create a background image and to draw the transient portion to an intermediate image for use in animating movement. To draw the entire Graph, it first draws all of its Edge objects without any text, then draws all the Vertex objects with their text, then draws the text associated with the Edge objects. To draw only its stationary portion, the Graph follows this same process except it skips any selected Vertex, selected Edge, or Edge containing a selected Vertex. How the Graph draws only the transient portion, depends on whether a Edge or Vertex is currently selected. If a Edge is currently selected, then only that edge and its text is drawn. If a Vertex is currently selected, then the Graph invokes that Vertex objects drawWithEdges() method.
To determine whether any Edge or Vertex in the Graph contains a particular (x,y) coordinate, the Graph submits the coordinates to each Edge and Vertex in the reverse order in which they were displayed. This handles the problem of determining the top item on the screen at the location indicated.
package GraphStuff;
import java.util.Enumeration;
import MyUtil.*;
import java.awt.*;
import java.util.Hashtable;
public class Graph {
public static final boolean selectedStuff=true;
protected int maxV;
private Vertex selectedVertex, // currently selected vertex
containsVertex; // most recently selected vertex
private Edge selectedEdge, // currently selected edge
containsEdge; // most recently selected edge
private Hashtable eHt, // storage for edges
vHt; // storage for vertices
private Edge[] p_edges; // lazy array
private Vertex[] p_vertices; // lazy array
private boolean p_altered_eHt,
p_altered_vHt,
p_directed;
// the altered_ methods are for the lazy array updates
private boolean altered_vHt() { return p_altered_vHt; }
private void altered_vHt( boolean hmm ) { p_altered_vHt=hmm; }
private boolean altered_eHt() { return p_altered_eHt; }
private void altered_eHt( boolean hmm ) { p_altered_eHt=hmm; }
public Graph() {
altered_eHt(true);
altered_vHt(true);
selectedVertex=null;
containsVertex=null;
selectedEdge=null;
containsEdge=null;
eHt = new Hashtable(100);
vHt = new Hashtable(35);
}
public Graph(Edge[] eA, Vertex[] vA) {
this();
put(vA);
put(eA);
}
public int numEdges(){
return eHt.size();
}
public int numVertices(){
return vHt.size();
}
public String toString() { return "Graph: \n" + stringRep();}
protected String stringRep () {
Vertex tmV= null;
Edge tmpE= null;
String str= numVertices()+" vertices, and " +numEdges()+" edges\n"
+ Vertex.header() +"\n";
if (numVertices()>0)
for(int v=1;v<=maxV;v++) {
tmV=get(v);
if (tmV!=null)
str=str+tmV+"\n";
}
str=str+Edge.header()+"\n";
if (numEdges()>0)
for(int u=1;u<=maxV;u++)
for(int v=1;v<=maxV;v++){
tmpE=(Edge)eHt.get(""+u+" "+v);
if (tmpE!=null)
str=str+tmpE+"\n";
}
return str;
}
public Graph put(int v, Vertex V) {
if (v>0 && V!=null) {
V.vNum(v);
if (V.vNum()!=v) {
return this;
}
V.lock(true);
maxV=(v>maxV?v:maxV);
if (get(v)==null) {
altered_vHt(true);
vHt.put(""+v,V);
} else {
Edge[] Es = p_edges();
if (Es!=null)
for(int k=0;k<Es.length;k++) {
if (Es[k].U().vNum()==v)
Es[k].U(V);
if (Es[k].V().vNum()==v)
Es[k].V(V);
}
altered_vHt(true);
vHt.remove(""+v);
vHt.put(""+v,V);
}
}
return this;
}
public Graph put(Vertex V) {
if (V==null)
return this;
else return put(V.vNum(),V);
}
public Graph put(Vertex[] VA) {
if (VA!=null)
for(int i=0;i<VA.length;i++)
put(VA[i]);
return this;
}
public Graph put(int u, int v, Edge E) {
/* Puts/replaces an Edge in the Graph. DOES NOT replace the two Vertex
fields in the Graph. Does nothing if E==null, or v<1 or u<1 or the vertices
for u and v do not exist.
*/
if (v>0 && u>0 && E!=null) {
if ((eHt.get(""+u+" "+v))!=null) {
Edge tmp = (Edge)(eHt.remove(""+u+" "+v));
tmp.releaseVertices();
altered_eHt(true);
}
Vertex tu = ((Vertex)vHt.get(""+u));
Vertex tv = ((Vertex)vHt.get(""+v));
if (E.addVertices(tu,tv)) {
eHt.put(""+u+" "+v,E);
altered_eHt(true);
}
}
return this;
}
public Graph put(Edge E) {
if (E==null)
return this;
else if (E.U()!=null && E.V()!=null)
return put(E.U().vNum(),E.V().vNum(),E);
else
return put(E.tmpUNum,E.tmpVNum,E);
}
public Graph put(Edge[] eA) {
if (eA!=null)
for(int i=0;i<eA.length;i++)
put(eA[i]);
return this;
}
public Vertex get(Vertex V){
if (V==null)
return null;
return get(V.vNum());
}
public Vertex get(int v){
return (Vertex)vHt.get(""+v);
}
public Edge get(Edge E){
if (E==null || E.U()==null || E.V()==null)
return null;
return get(E.U().vNum(),E.V().vNum());
}
public Edge get(int u, int v){
return (Edge)eHt.get(""+u+" "+v);
}
public Graph delete(int v){
if (v<1)
return this;
if (selectedVertex!=null && selectedVertex.vNum()==v)
selectedVertex=null;
containsVertex=null;
if (vHt.remove(""+v)!=null) {
altered_vHt(true);
Edge[] Es = p_edges();
if (Es!=null)
for(int k=0;k<Es.length;k++) {
if (Es[k].U().vNum()==v || Es[k].V().vNum()==v)
delete(Es[k]);
}
}
return this;
}
public Graph delete(Vertex V){
if (V==null)
return this;
return delete(V.vNum());
}
public Graph delete(int u,int v){
if (u>0 && v>0) {
Edge tmp=(Edge)(eHt.remove(""+u+" "+v));
if (selectedEdge==tmp)
selectedEdge=null;
containsEdge=null;
if (tmp!=null) {
altered_eHt(true);
tmp.U().removeEdge(tmp);
tmp.V().removeEdge(tmp);
}
}
return this;
}
public Graph delete(Edge E){
if (E!=null)
return delete(E.U().vNum(),E.V().vNum());
return this;
}
public boolean isEdge(int u, int v) {
return (numEdges()>0 && get(u,v)!=null);
}
public boolean isVertex(int v) {
return (numVertices()>0 && get(v)!=null);
}
public void deleteAll() {
Vertex[] v = p_vertices();
if (v!=null)
for(int i=0;i<v.length;i++)
delete(v[i].vNum());
}
public Vertex[] vertices(){
if (numVertices()<1)
return null;
maxV=0;
int i=0;
Vertex[] vertices=new Vertex[numVertices()];
Enumeration X = vHt.elements();
while (X.hasMoreElements()) {
vertices[i]=(Vertex)(X.nextElement());
if (maxV<vertices[i].vNum())
maxV=vertices[i].vNum();
i++;
}
return vertices;
}
private Vertex[] p_vertices(){
if (numVertices()<1)
return null;
if (!altered_vHt() && p_vertices!=null)
return p_vertices;
maxV=0;
int i=0;
p_vertices=new Vertex[numVertices()];
Enumeration X = vHt.elements();
while (X.hasMoreElements()) {
p_vertices[i]=(Vertex)(X.nextElement());
if (maxV<p_vertices[i].vNum())
maxV=p_vertices[i].vNum();
i++;
}
altered_vHt(false);
return p_vertices;
}
public Edge[] edges(){
if (numEdges()<1)
return null;
Enumeration X = eHt.elements();
Edge[] edges = new Edge[numEdges()];
int i=0;
while (X.hasMoreElements())
edges[i++]=(Edge)(X.nextElement());
return edges;
}
private Edge[] p_edges(){
if (numEdges()<1)
return null;
if (!altered_eHt() && p_edges!=null )
return p_edges;
Enumeration X = eHt.elements();
p_edges = new Edge[numEdges()];
int i=0;
while (X.hasMoreElements())
p_edges[i++]=(Edge)(X.nextElement());
altered_eHt(false);
return p_edges;
}
public void mergeEdgeColors(int oldColor, int resultColor){
Edge[] myEdges = p_edges();
for(int i=0;i<myEdges.length;i++)
if (myEdges[i].colorNum()==oldColor)
myEdges[i].colorNum(resultColor);
}
public void mergeVertexColors(int oldColor, int resultColor){
Vertex[] myVertices = p_vertices();
for(int i=0;i<myVertices.length;i++)
if (myVertices[i].colorNum()==oldColor)
myVertices[i].colorNum(resultColor);
}
public void mergeColors(int oldColor, int resultColor){
mergeEdgeColors(oldColor,resultColor);
mergeVertexColors(oldColor,resultColor);
}
public int uncolor() {
Edge[] e = p_edges();
for(int i=0;i<e.length;i++)
e[i].colorNum(General.defaultColorNum);
Vertex[] v = p_vertices();
for(int i=0;i<v.length;i++)
v[i].colorNum(General.defaultColorNum);
return General.defaultColorNum;
}
public void draw(Graphics g) {
draw(g,true,false);
}
public void draw(Graphics g, boolean drawSelected ) {
draw(g,drawSelected,true);
}
public void draw(Graphics g, boolean drawSelected, boolean considerSelected){
if (!considerSelected || !drawSelected ) {
Edge[] Es = p_edges();
if (Es!=null) {
for(int i=0;i<Es.length;i++)
if (!considerSelected ||
(Es[i].V().beenSelected()
|| Es[i].U().beenSelected()
|| Es[i].beenSelected())
==drawSelected) {
Es[i].draw(g);
}
}
Vertex[] Vs = p_vertices();
if (Vs!=null) {
for(int i=0;i<Vs.length;i++)
if (!considerSelected || Vs[i].beenSelected()==drawSelected)
Vs[i].draw(g);
}
if (containsVertex!=null &&
containsVertex.beenSelected()==drawSelected)
containsVertex.draw(g);
if (Es!=null) {
for(int i=0;i<Es.length;i++)
if (!considerSelected ||
(Es[i].V().beenSelected()
|| Es[i].U().beenSelected()
|| Es[i].beenSelected() ) ==drawSelected) {
Es[i].draw(g,true);
}
}
} else if (selectedVertex!=null) {
selectedVertex.drawWithEdges(g);
} else if (selectedEdge!=null) {
selectedEdge.draw(g);
selectedEdge.draw(g,true);
}
}
public boolean contains(xPoint p) {
/*
returns TRUE if a component of the graph occupies point p
returns FALSE otherwise
*/
if (containsVertex!=null && containsVertex.contains(p)) {
return true;
}
if (containsEdge!=null && containsEdge.contains(p)) {
return true;
}
containsVertex=null;
containsEdge=null;
Vertex[] Vs = p_vertices();
if (Vs!=null)
for(int i=Vs.length-1;i>=0;i--) {
if (Vs[i].contains(p)){
containsVertex=Vs[i];
return true;
}
}
Edge[] Es = p_edges();
if (Es!=null)
for(int i=Es.length-1;i>=0;i--) {
if (Es[i].contains(p)) {
containsEdge=Es[i];
return true;
}
}
return false;
}
public boolean beenSelected() {
return ( (selectedVertex!=null && selectedVertex.beenSelected())
|| (selectedEdge!=null && selectedEdge.beenSelected()) );
}
public Object selectedPart() {
if (selectedVertex!=null && selectedVertex.beenSelected())
return selectedVertex;
if (selectedEdge!=null && selectedEdge.beenSelected())
return selectedEdge;
return null;
}
public void unselect() {
if (selectedVertex!=null) {
selectedVertex.beenSelected(false);
selectedVertex=null;
}
if (selectedEdge!=null) {
selectedEdge.beenSelected(false);
selectedEdge=null;
}
}
public Edge select(int u, int v) {
unselect();
if (isEdge(u,v)) {
selectedEdge=get(u,v);
selectedEdge.beenSelected(true);
}
return selectedEdge;
}
public Vertex select(int v) {
unselect();
if (isVertex(v)) {
selectedVertex=get(v);
selectedVertex.beenSelected(true);
}
return selectedVertex;
}
public Object select(xPoint p) {
unselect();
if (!contains(p))
return null;
if (containsVertex!=null) {
selectedVertex=containsVertex;
selectedVertex.beenSelected(true);
return selectedVertex;
}
if (containsEdge!=null) {
selectedEdge=containsEdge;
selectedEdge.beenSelected(true);
return selectedEdge;
}
return null;
}
}