directedgraph.java

Specification File adjacencyListGragh class GeneralGraph: use adjacency list to implement the gr

/*
Accessor methods:
* endVertices(e): an array of the two endvertices of e
* opposite(v, e): the vertex opposite of v on e
* areAdjacent(v, w): true iff v and w are adjacent
* replace(v, x): replace element at vertex v with x
* replace(e, x): replace element at edge e with x

Update methods :
* insertVertex(o): insert a vertex storing element o
* insertEdge(v, w, o): insert an edge (v,w) storing element o
* removeVertex(v): remove vertex v (and its incident edges)
* removeEdge(e): remove edge e

Iterator methods:
* incidentEdges(v): edges incident to v
* vertices(): all vertices in the graph
* edges(): all edges in the graph
*/
package adjacencyListGragh;
/* It is a Directed Graph using an Adjacency List structure.*/
import java.util.Vector;
public class DirectedGraph {
	/* creat a graph list table use Vector, 
	 * graph is a vertex list store the all the 
	 * vertex in the graph, and every vertex has
	 * the property incident edges which is stored
	 * in a Vector, so in all the graph contain two
	 * list, one is vertex list, the other is the 
	 * edge list*/
	private Vector<Vertex> graph;

	public DirectedGraph(){
		this.graph = new Vector<Vertex>();
		/* use adjacency list to implement the graph use data structure is vector
		 * */
	}
	
	public Vertex[] endVertices(Edge edge){
		Vertex[] result = new Vertex[2];
		/*store the result in an array which type is Vertex*/
		result[0] = edge.getOriginVertex();
		result[1] = edge.getDestinyVertex();
		/*if the edge doesn't exist, it will return null, 
		 * this will be helpful in the following method opposite()*/
		return result;
	}
	
	public Vertex opposite(Vertex v , Edge e ){
		//v is one end of the edge e 
		Vertex[] vertices = this.endVertices(e);
		if (vertices[0] == v){
			return vertices[1];
		}
		else if (vertices[1] == v){
			return vertices[0];
		}
		//if e does not exist, return null
		else 
			return null;
	}
	
	public Integer outDegree(Vertex v){
		Vertex headVertex = graph.get(0);
		for ( int i=0; i < graph.size();i++){
			headVertex = graph.get(i);
			if (headVertex == v)
				return headVertex.getIncidentEdges().size();
		}
		return null;
	}
	
	public Integer inDegree(Vertex v){
		int degree = 0;
		if (v!=null){
			Vertex headVertex = graph.get(0);
			for ( int i=0; i < graph.size();i++){
				headVertex = graph.get(i);
				for (int j=0; j<headVertex.getIncidentEdges().size(); j++){ 
					if (headVertex.getIncidentEdges().get(j).getDestinyVertex() == v)
						degree++;
				}
			}
			return degree;
		}
		else 
			return null;
	}
	
	public boolean areAdjacent(Vertex v , Vertex w ){
		Vertex headVertex = graph.get(0);//initialize the headVertex from the beginning element
			
		//get the head position of v in the headVertex of the adjacency list 
		for ( int i=0; i < graph.size();i++){
			/*if the v is the origin vertex, w is the destiny*/
			headVertex = graph.get(i);//get w in the the adjacency list of v
			if (headVertex == v){
				for (int j=0 ;j < headVertex.getIncidentEdges().size() ;j++){
					if (headVertex.getIncidentEdges().get(j).getDestinyVertex() == w) return true;
				}
			}
			/*if the v is the destiny vertex, w is the origin*/
			if (headVertex == w){
				for (int j=0 ;j < headVertex.getIncidentEdges().size() ;j++){
					if (headVertex.getIncidentEdges().get(j).getDestinyVertex() == v) return true;
				}
			}
		}
		return false;
	}
	
	public void replace(Edge e , Object element){
		e.setElement(element);
	}
	
	public void replace(Vertex v , Object element){
		v.setElement(element);
	}
	
	public Vertex insertVertex(Object element){
		Vertex headVertex = new Vertex(element);
		graph.add(headVertex);
		return headVertex;
	}
	
		/* insert a edge from v to w, determine whether the 
		 * insertion is succeed, may be the vertex doesn't exist*/
	public Edge insertEdge(Vertex v , Vertex w, Object element){
		Edge edge = new Edge( v , w , element);
		Vertex headVertex = graph.get(0);//initialize the headVertex from the beginning element
		// find the head position to insert
		for ( int j=0; j< graph.size();j++){
			headVertex = graph.get(j);
			if (headVertex == v){
				headVertex.getIncidentEdges().add(edge);
				//return edge;
			}
		}
		return edge;
	}

	public void removeVertex(Vertex v){
		/* when we remove a vertex v we have to remove all the edge
		 * which destiny is v, also we should remove all the edge
		 * which is orginate from v(that is to say we remove the 
		 * headVertex in the graph list);
		 * */
		Vertex headVertex = graph.get(0);//initialize the headVertex from the beginning element
		for (int i = 0; i< graph.size();i++){
			headVertex = graph.get(i);
			//remove all the edge which is orginate from v
			if (headVertex == v){
				graph.remove(i);
				i--;//because the vector's length is changing at the same time
			}
			//remove all the edge which destiny is v
			else{
				for (int j=0; j<headVertex.getIncidentEdges().size(); j++){
					if (headVertex.getIncidentEdges().get(j).getDestinyVertex() == v)
						headVertex.getIncidentEdges().remove(j);
				}
			}

		}
	}
	
	/* remove a edge in graph, determine whether the 
	 * remove is succeed*/
	public boolean removeEdge(Edge e){
		Vertex headVertex = graph.get(0);
		for ( int i=0; i< graph.size();i++){
			headVertex = graph.get(i);
			// find one edge of e in the graph list
			if (headVertex == e.getOriginVertex()){
				for (int j=0 ;j<headVertex.getIncidentEdges().size();j++){
					// find another edge of e in the edge list
					if (headVertex.getIncidentEdges().get(j) ==e){
						headVertex.getIncidentEdges().remove(j);
						return true;
					}
				}
			}
		}
		return false;
	}
	
	public Vector<Edge> incidentEdges(Vertex v){
		Vertex headVertex = graph.get(0);
		Vector<Edge> result = new Vector<Edge>();//result stored in a vector
		//add all the edge which is orginate from v to the result
		for (int i=0; i< graph.size();i++){
			headVertex = graph.get(i);
			if(headVertex == v){
				if (headVertex ==null)	//v is not existed
					return null;
				else if(headVertex.getIncidentEdges().isEmpty())	//v is a trivial vertex
					return null;
				/*else{					//v has incident edges
					for (int j=0; j< headVertex.getIncidentEdges().size();j++){
						result.add(headVertex.getIncidentEdges().get(j));
					}
				}*/
				else{					//v has incident edges
					result.addAll(headVertex.getIncidentEdges());
				}
				
			}
		}
		//add all the edge which destiny is v to the result
		for (int i=0; i< graph.size();i++){
			headVertex = graph.get(i);
			for (int j=0; j<headVertex.getIncidentEdges().size(); j++){
				if(headVertex.getIncidentEdges().get(j).getDestinyVertex() == v){
					result.add(headVertex.getIncidentEdges().get(j));
				}
			}
		}
		return result;
	}
	
	public Vector<Vertex> vertices(){
		return graph;
	}
	
	public Vector<Edge> edges(){
		Vertex headVertex = graph.get(0);
		Vector<Edge> result = new Vector<Edge>();//result stored in a vector
		for (int i=0 ;i< graph.size();i++){
			headVertex = graph.get(i);
			result.addAll(headVertex.getIncidentEdges());
		}
		return result;
	}

}