generalgraph.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;

import java.util.Vector;
public class GeneralGraph {
	private boolean isDirected;//whether the graph is directed or not
	private Vector<Vertex> graph;
	public GeneralGraph(){
		/* use adjacency list to implement the graph use data structure is vector
		 * */
		this.graph = new Vector<Vertex>();
		this.isDirected = false;//default is a undirected graph
	}
	
	public GeneralGraph(boolean bool){
		/* use adjacency list to implement the graph use data structure is vector
		 * */
		this.graph = new Vector<Vertex>();
		this.isDirected = bool;//whether the graph is directed or not
	}
	
	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 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 Integer Degree(Vertex v){
		if(!isDirected){
			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 outDegree(Vertex v){
		if(isDirected){
			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(isDirected){
			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;
			}
		}
		return null;
	}
	
	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;
	}
	
	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
		
		for ( int j=0; j< graph.size();j++){
		
			headVertex = graph.get(j);
			// find the head position of vertex v to insert
			if (headVertex == v){
				headVertex.getIncidentEdges().add(edge);
			}
			// find the head position of vertex w to insert
			if (!isDirected){
				if (headVertex == w){
					headVertex.getIncidentEdges().add(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);
			//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
							||((!isDirected) && headVertex.getIncidentEdges().get(j).getOriginVertex() ==v))
						headVertex.getIncidentEdges().remove(j);
				}
			}

		}
	}
	public void 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() || headVertex == e.getDestinyVertex()){
				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);
					}
				}
			}
			
		}
	}
	
	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());
				}
				
			}
		}
		//if the graph is undirected, the edge list of v contain all the edge incident to v
		//else if the graph is directed, then add all the edge which destiny is v to the result
		if (isDirected){
			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);
			for (int j=0; j< headVertex.getIncidentEdges().size();j++){
				if (!headVertex.getIncidentEdges().get(j).printed){
					result.add(headVertex.getIncidentEdges().get(j));
					headVertex.getIncidentEdges().get(j).printed = true; 
				}
			}
		}
		for (int i=0 ;i< graph.size();i++){
			for (int j=0; j< graph.get(i).getIncidentEdges().size();j++){
				graph.get(i).getIncidentEdges().get(j).printed = false; 
			}
		}
		return result;
	}
}