www.pudn.com > campusleader.rar > Graph.java, change:2012-01-04,size:7848b


package GraphPackage; 
import java.util.Iterator; 
import java.util.Iterator; 
//import QueueInterfacePackage.*; 
import GraphPackage.Vertex.Edge; 
//import ListQueuePackage.*; 
//import StackInterfacepackage.*; 
//import Stackpackage.*; 
import java.util.PriorityQueue; 
 
import sun.misc.GC; 
//import java.util.*; 
public class Graph<T> implements GraphInterface<T>{ 
	private VertexInterface<T> origin; 
	private QueueInterface<VertexInterface<T>> entry; 
	private ListWithIteratorInterface<VertexInterface<T>>orderList; 
	private int edgeNumbers; 
	public Graph() 
	{ 
		edgeNumbers=0; 
		origin=null; 
		entry=new ListQueue<VertexInterface<T>>(); 
		orderList=new LinkedListWithIterator<VertexInterface<T>>(); 
	} 
	public void addVertex(T vertexLabel) { 
		VertexInterface<T> newVertex=new Vertex<T>(vertexLabel); 
		if(orderList.isEmpty()) 
		{ 
			origin=newVertex; 
			orderList.add(newVertex); 
		} 
		else 
		orderList.add(newVertex); 
	} 
	public boolean addEdge(T begin, T end, double edgeWeight,int edgeFlag) { 
		VertexInterface<T> beginVertex=null; 
		VertexInterface<T> endVertex=null; 
		beginVertex=findLabel(begin); 
		endVertex=findLabel(end); 
		beginVertex.connect(endVertex,edgeWeight,edgeFlag); 
		endVertex.connect(beginVertex,edgeWeight,edgeFlag); 
		edgeNumbers++; 
		return true; 
	} 
 
	public boolean addEdge(T begin, T end) { 
		VertexInterface<T> beginVertex=null; 
		VertexInterface<T> endVertex=null; 
		beginVertex=findLabel(begin); 
		endVertex=findLabel(end); 
		beginVertex.connect(endVertex); 
		edgeNumbers++; 
		return true; 
	} 
	public Iterator<VertexInterface<T>> getorderIterator() 
	{ 
		return new orderIterator(); 
	} 
	private class orderIterator implements Iterator<VertexInterface<T>> 
	{ 
		private Iterator<VertexInterface<T>> order; 
		private orderIterator() 
		{ 
			order=orderList.getIterator(); 
		} 
		public boolean hasNext() { 
			return order.hasNext(); 
		} 
		public VertexInterface<T> next() { 
			VertexInterface<T> next=null; 
			if(hasNext()) 
			{ 
				next=order.next(); 
			} 
			return next; 
		} 
		public void remove() { 
			 
		} 
		 
	} 
	public boolean hasEdge(T begin, T end) { 
		VertexInterface<T> beginVertex=null; 
		VertexInterface<T> endVertex=null; 
		beginVertex=findLabel(begin); 
		endVertex=findLabel(end); 
		Iterator<VertexInterface<T>> beginVertexneighbors=beginVertex.getNeighborIterator(); 
		Iterator<VertexInterface<T>> endVertexneighbors=beginVertex.getNeighborIterator(); 
		while(beginVertexneighbors.hasNext()) 
		{ 
			if(endVertex==beginVertexneighbors.next()) 
			{ 
				return true; 
			} 
		} 
		while(endVertexneighbors.hasNext()) 
		{ 
			if(endVertex==endVertexneighbors.next()) 
			{ 
				return true; 
			} 
		} 
		return false; 
	} 
	public boolean isEmpty() { 
		return origin==null; 
	} 
	public int getNumberOfVertices() { 
		int count=0; 
		Iterator<VertexInterface<T>> orderList=this.getorderIterator(); 
		while(orderList.hasNext()) 
		{ 
			orderList.next(); 
			count++; 
		} 
		return count; 
	} 
	public int getNumberOfEdge() { 
		return edgeNumbers; 
	} 
	public void clear() { 
		origin=null; 
	} 
	public QueueInterface<VertexInterface<T>> getDepthFirstTraversal() { 
		QueueInterface<VertexInterface<T>> traversal=new ListQueue<VertexInterface<T>>(); 
		StackInterface<VertexInterface<T>> vertexStack=new Stack<VertexInterface<T>>(); 
		origin.visit(); 
		vertexStack.push(origin); 
		traversal.enqueue(origin); 
		while(!vertexStack.isempty()) 
		{ 
			VertexInterface<T> topVertex=vertexStack.peek(); 
			if(topVertex.getUnvisitedNeighbor()!=null) 
			{ 
				VertexInterface<T> nextNeighbor=topVertex.getUnvisitedNeighbor(); 
				nextNeighbor.visit(); 
				traversal.enqueue(nextNeighbor); 
				vertexStack.push(nextNeighbor); 
			} 
			else 
				vertexStack.pop(); 
		} 
		while(!traversal.isempty()) 
		{ 
			System.out.println(traversal.getFront().getLabel()); 
			traversal.dequeue(); 
		} 
		return traversal; 
	} 
	public QueueInterface<VertexInterface<T>> getBreadthFirstTraversal() { 
		QueueInterface<VertexInterface<T>> traversal=new ListQueue<VertexInterface<T>>(); 
		QueueInterface<VertexInterface<T>> vertexQueue=new ListQueue<VertexInterface<T>>(); 
		origin.visit(); 
		traversal.enqueue(origin); 
		vertexQueue.enqueue(origin); 
		while(!vertexQueue.isempty()) 
		{ 
			VertexInterface<T> frontVertex=vertexQueue.getFront(); 
			vertexQueue.dequeue(); 
			while(frontVertex.getUnvisitedNeighbor()!=null) 
			{ 
				VertexInterface<T> nextNeighbor=frontVertex.getUnvisitedNeighbor(); 
				nextNeighbor.visit(); 
				traversal.enqueue(nextNeighbor); 
				vertexQueue.enqueue(nextNeighbor); 
			} 
		} 
		while(!traversal.isempty()) 
		{ 
			System.out.println(traversal.getFront().getLabel()); 
			traversal.dequeue(); 
		} 
		return traversal; 
	} 
	private class PathEntry implements Comparable 
	{ 
		private VertexInterface<T> vertex; 
		private VertexInterface<T> predecessor; 
		private double cost; 
		private PathEntry(VertexInterface<T> vertex,double cost,VertexInterface<T>predecessor){ 
			this.vertex=vertex; 
			this.cost=cost; 
			this.predecessor=predecessor; 
		} 
		private VertexInterface<T> getVertex() 
		{ 
			return vertex; 
		} 
		private VertexInterface<T> getPredecessor() 
		{ 
			return predecessor; 
		} 
		private double getCost(){ 
			return cost; 
		} 
		public int compareTo(Object newcost) { 
			int result=0; 
			if(this.getCost()<((PathEntry)newcost).getCost()) 
				result=-1; 
			else if(this.getCost()>((PathEntry)newcost).getCost()) 
				result=1; 
			else if(this.getCost()==((PathEntry)newcost).getCost()) 
				result=0; 
			return result; 
		} 
	} 
	public StackInterface <VertexInterface<T>>getCheapestPath(T begin,T end) 
	{ 
		VertexInterface<T> originVertex=findLabel(begin); 
		VertexInterface<T> endVertex=findLabel(end); 
		boolean done=false; 
		PriorityQueue<PathEntry> priorityQueue=new PriorityQueue<PathEntry>(15); 
		priorityQueue.add(new PathEntry(originVertex,0,null)); 
		while(!done&&!priorityQueue.isEmpty()) 
		{ 
			VertexInterface<T> frontVertex; 
			PathEntry frontEntry=priorityQueue.remove(); 
			frontVertex=frontEntry.getVertex(); 
			if(!frontVertex.isVisited()) 
			{ 
				frontVertex.visit(); 
				frontVertex.setCost(frontEntry.getCost()); 
				frontVertex.setPredecessor(frontEntry.getPredecessor()); 
				if(frontVertex==endVertex) 
					done=true; 
				else 
				{ 
					VertexInterface<T> nextNeighbor; 
					Iterator<VertexInterface<T>> NeighborIterator= frontVertex.getNeighborIterator(); 
					while(NeighborIterator.hasNext()) 
					{ 
						nextNeighbor=NeighborIterator.next(); 
						double Weight=frontVertex.getNeighborWeight(nextNeighbor); 
						if(!nextNeighbor.isVisited()) 
						{ 
							double nextCost=Weight+frontVertex.getCost(); 
							priorityQueue.add(new PathEntry(nextNeighbor,nextCost,frontVertex)); 
						} 
					} 
				} 
			} 
		} 
		StackInterface<VertexInterface<T>> path=new Stack<VertexInterface<T>>(); 
		path.push(endVertex); 
		while(endVertex.hasPredecessor()) 
		{ 
			endVertex=endVertex.getPredecessor(); 
			path.push(endVertex); 
		} 
		/*while (!path.isempty()){ 
			System.out.print(path.peek().getLabel()+" "); 
			path.pop(); 
		}*/ 
		remove(); 
		return path; 
	} 
	public void remove() 
	{ 
		VertexInterface<T> beginVertex=null; 
		Iterator<VertexInterface<T>> orderList=getorderIterator(); 
		VertexInterface<T> next; 
		while(orderList.hasNext()) 
		{ 
			next=orderList.next(); 
			next.setPredecessor(null); 
			next.unVisit(); 
		} 
	} 
	private VertexInterface<T> findLabel(T begin) 
	{ 
		VertexInterface<T> beginVertex=null; 
		Iterator<VertexInterface<T>> orderList=getorderIterator(); 
		VertexInterface<T> next; 
		while(orderList.hasNext()) 
		{ 
			next=orderList.next(); 
			if(next.getLabel()==begin) 
				beginVertex=next; 
		} 
		return beginVertex; 
	} 
}