_______________________________________________________________
This tutorial follows in sequence to my Linked List tutorial. It builds off of many of the concepts of Linked Lists, so if you are uncomfortable working with custom Linked Lists, you should check out my Linked List Tutorials.
So let's start with talking about what a Graph is. Basically, a Graph is a group of points, also called edges or vertices, which can be connected by pointers or connectors that (can) record the distances between the two points. So we see two classes beginning to develop already- an Edge class and a Connector class.
Since the Edges are the basis of Graphs, let's talk about them a little. Just like in high school Geometry, Edges are basically points that can connect to an infinite number of other points. However, they also act like Linked Nodes in the fact that they can store data. So visually, our "Linked List" is now becoming more web-like and less linear.
Now that we've talked about Edges, let's define the Edge class:
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package datastructures;
import java.util.*;
public class Edge<E>{
private static int ID = 0; //counts how many Edges exist
/*
When working with weighted Graphs,
having an element becomes important.
For example, in game programming, the
weights could represent a lag or a hidden
bonus that could make winning significantly
easier.
*/
private E elem;
private int id; //the individual Edge identifier
private int weight;
//holds Pointer objects, which reference other Edges
private LinkedList<Connector<E>> pointers;
//constructors
public Edge(){
//invoke constructor to initialize elem to null pointer
this(null, Integer.MAX_VALUE);
}
public Edge(E elem, int distance){
this.elem = elem;
id = ID++; //assign indv id and increment static ID counter
pointers = new LinkedList<Connector<E>>();
this.weight = distance;
}
//accessors and mutators
public int getId(){return id;}
public E getElem(){return elem;}
public void setElem(E elem){this.elem = elem;}
public int getDistance(){return weight;}
public void setDistance(int dist){weight = dist;}
//add a connection not taking distances into account
public void connectTo(Edge<E> other){
Connector<E> c = new Connector<E>(this, other);
//prevents adding duplicate connectors
if(!pointers.contains(c)) pointers.add(c);
//reference Connector in other Edge as well
LinkedList<Connector<E>> conn = other.getConnections();
if(!conn.contains(c)) conn.add(c);
}
public void connectTo(Edge<E> other, int distance){
Connector<E> c = new Connector<E>(this, other, distance);
if(!pointers.contains(c)) pointers.add(c);
}
public LinkedList<Connector<E>> getConnections(){return pointers;}
public void sortConnections(){ Collections.sort(pointers); }
public Iterator<Connector<E>> iterator(){ return pointers.iterator(); }
//one Edge is equal to another if the two elems are equal to each other
//and they have the same Connections
public boolean equals(Edge<E> other){
if(other.pointers.size() != pointers.size())
return false;
LinkedList<Connector<E>> temp = new LinkedList<Connector<E>>(pointers);
//if the elems are equal and the Lists are equal, regardless of order
//then the Edges are equal
return elem.equals(other.getElem()) &&
temp.retainAll(other.pointers);
}
public String toString(){return this.elem.toString();}
}
As we can see, the Edge<E> class for a Graph is significantly more involved than a Linked Node for a standard Linked List.
The next component of a Graph we need to discuss is the Connector class. Basically, a Connector (as the name implies) connects two Edges together. In applications of Graphs, like game programming, distances are important from a Connector standpoint for purposes like travel distance. However, from a more theoretical standpoint, distances or "weights" are generally included with the Edge. To keep this Graph adaptable for theoretical and practical applications, I included an E elem in the Edge class, and a distance in the Connector class. So now, let's take a look at the Connector class:
public class Connector<E> implements Comparable<Connector<E>>{
private Edge<E> one, two;
private int distance;
/*this two-args constructor creates
a Connector object to Connect two Nodes
together with a standard distance of 0
By using this constructor, it is assumed
That distance is either weighted through the
Edges or otherwise is irrelevant
*/
public Connector(Edge<E> one, Edge<E> two){
this(one, two, 0);
}
public Connector(Edge<E> one, Edge<E> two, int distance){
this.one = one;
this.two = two;
this.distance = distance;
}
//accessors and mutators
public Edge<E> getOne(){return one;}
public Edge<E> getTwo(){return two;}
public int getDistance(){return distance;}
public void setDistance(int distance){this.distance = distance;}
//Two connectors are equal if the two Edges
//are equal and the distance is equal
public boolean equals(Connector<E> other){
return one.equals(other.getOne()) &&
two.equals(other.getTwo()) &&
distance == other.getDistance();
}
public String toString(){ return "(" + one.getElem() + ", " + two.getElem() + "): " + distance; }
public int compareTo(Connector<E> other){
return this.distance - other.distance;
}
}
So unlike Edge which has a lot going on inside of it, the Connector class is significantly simpler, as its only function is to link two Edges together.
The last class we have to design is our Graph class. If we look back at our Edge and Connector classes, we see that they really do all the work of holding the physical Graph together. We just need a class to encapsulate this web. So:
public class Graph<E>{
//Because we will need random access to the Edges
//We will use an ArrayList to hold them
private ArrayList<Edge<E>> edges;
public Graph(){
edges = new ArrayList<Edge<E>>();
}
//add Edge to the List
public boolean addEdge(Edge<E> vertex){
if(edges.contains(vertex)) return false;
edges.add(vertex);
return true;
}
public boolean contains(Edge<E> vertex){
return edges.contains(vertex);
}
public Edge<E> get(int index){
return edges.get(index);
}
//returns number of Edges in Graph
public int count(){return edges.size();}
public boolean equals(Graph<E> other){
if(other.edges.size() != edges.size())
return false;
//store all of Edges of larger Graph
ArrayList<Edge<E>> temp = new ArrayList<Edge<E>>(other.edges);
//if temp changed, then the Graphs are not equal
return temp.retainAll(edges);
}
}
MultiQuote
| 