graphuos.java

国外的数据结构与算法分析用书

	/**	Go to the first vertex. <br> 
		Analysis: Time = O(1) */
	public void goFirst()
	{
		itemIndex = 0;
		goIth(nextNonNullVertexIndex());
	}
  
	/**	Move  prior to the first item. <br>
		Analysis: Time = O(1) */
	public void goBefore()
	{
		itemIndex = 0;
	}
  
	/**	Go to the next vertex. <br>
		Analysis: Time = O(capacity), worst case <br>
		PRECONDITION: <br>
		<ul>
			!after()
		</ul> */
	public void goForth() throws AfterTheEndUosException
	{
		if (after())
			throw new AfterTheEndUosException("Cannot advance to next item since already after.");
		
		goIth(nextNonNullVertexIndex());
	}

	/**	Find the next nonempty location in the vertex array. */
	protected int nextNonNullVertexIndex()
	{
		int i = itemIndex + 1;
		while (i <= capacity() && vertexArrayItem(i) == null)
			i++;     
		return i;
	}

	/**	Move to after the last item. <br>
		Analysis: Time = O(1)*/
	public void goAfter()
	{
		itemIndex = capacity();
	}

	/**	Set directed status for this graph. <br>
		Analysis: Time = O(1)
		@param ndirected indicates whether the graph is directed or not */
	protected void setDirected(boolean ndirected)
	{
		directed = ndirected;
	}

	/**	Construct and insert an edge with ends v1 and v2 into the graph.
		@param v1 initial vertex of the new edge
		@param v2 terminal vertex of the new edge */
	public abstract void eNew(VertexUos v1, VertexUos v2);

	/**	Construct and insert an edge with i and j as the indices of its ends.
		@param i index of the initial vertex of the new edge
		@param j index of the terminal vertex of the new edge */
	public void eNew(int i, int j)
	{
		GraphPositionUos position = currentPosition();
		goIth(i);
		VertexUos v = (VertexUos) item();
		goIth(j);
		eNew(v, (VertexUos)item());
		if (!directed)
			eNew((VertexUos)item(), v);
		goPosition(position);
	}

	/**	Set eItem to refer to the edge (u,v), or null if not found.
		@param v1 initial vertex of the edge being searched for
		@param v2 terminal vertex of the edge being searched for  */
	public abstract void eSearch(VertexUos u, VertexUos v);
  
	/**	Delete the current edge and move to the next edge for the vertex being iterated. <br>
		PRECONDITION: <br>
		<ul>
			eItemExists()
		</ul> */
	public abstract void  deleteEItem() throws NoCurrentItemUosException;	  
  
	/**	Remove all vertices from the graph. <br>
		Analysis: Time = O(capacity)*/
	public void wipeOut()
	{
		n = 0;
		m = 0;
		for (int i = 1; i <= capacity(); i++)
			vertexArraySetItem(null, i);
		item = null;
		itemIndex = 0;
		eItem = null;
		iterationIndex = 0;
	} 

	/**	Go to the first edge of v to start an edge list iteration. 
		@param v1 vertex to move to the first edge of */
	public abstract void eGoFirst(VertexUos v);
  
	/**	Index of the vertex being edge iterated. */
	protected int iterationIndex;

	/**	Index of the vertex being edge iterated. <br>
		Analysis: Time = O(1) */
	public int iterationIndex()
	{
		return iterationIndex;
	}

	/**	The adjacent vertex for an edge list iteration. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			eItemExists()
		</ul>*/
	public VertexUos adjItem() throws NoCurrentItemUosException
	{
		if (!eItemExists())
			throw new NoCurrentItemUosException("There is no adjacent item if there is no item.");
		
		return eItem.other(vertexArrayItem(iterationIndex));
	}

	/**	The index of the adjacent vertex in the edge iteration. */
	public abstract int adjIndex();

	/**	Go to the next edge of the edge list being scanned. <br> 
		PRECONDITION: <br>
		<ul>
			!eAfter() 
		</ul> */
	public abstract void eGoForth() throws AfterTheEndUosException;
  
	/**	Are we off the end of the edge list being scanned?. */
	public abstract boolean eAfter();

	/**	The current position in the graph. */
	public abstract GraphPositionUos currentPosition();
	
	/**	Go to the position pos of the graph. */
	public abstract void goPosition(GraphPositionUos pos);

	/**	Read in a graph. <br>
		Analysis: Time = O(n + m) */
	public void read() 
	{
		try
		{
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			readSizeAndMakeVertices(br);
			goFirst();
			while (!after())
			{
				readAdjList(br);
				goForth();
			}
		} catch (IOException e)
		{
			// Cannot create graph because there was a problem with the console input
	  		System.err.println("error creating graph from interactive input");
	  		e.printStackTrace();
		}
	}

	/**	Read in the size of the matrix from the console and make all the vertices. <br>
		Analysis: Time = O(n), where n = number of vertices */
	protected void readSizeAndMakeVertices(BufferedReader br) throws IOException
	{
		System.out.println("\nInput the size of the graph: ");
		int size = Integer.parseInt(br.readLine());
		while (size > capacity())
		{
			System.out.println("\nError: size exceeds graph's capacity.  Input the size of the graph: ");
			size = Integer.parseInt(br.readLine());
		}
		n = 0;
		for (int i = 1; i <= size; i++)
			vNewIth(null, i);
	}  

	/**	Read adjacency list from the console, with 0 to end the list. <br>
		Analysis: Time = O(m), where m = number of edges */  
	protected void readAdjList(BufferedReader br) throws IOException
	{    
		VertexUos u = item;
		System.out.print("\nInput the index for a vertex adjacent to " 
						 + u + " with 0 to signal the end of the list:");
		int i = Integer.parseInt(br.readLine());
		while (i != 0)
		{
			goIth(i);
			VertexUos v = item;
			if (!adjacent(u, v))
				eNew(u, v);
			System.out.print("\nInput the index for a vertex adjacent to " 
						+ u + " with 0 to signal the end of the list:");
			i = Integer.parseInt(br.readLine());
		}
		goToItem(u);
	}

	/**	Read in a graph from a file. <br>
		Analysis: Time = O(max(n, m)) where n = number of vertices, m = number of edges 
		@param name The name of the file from which the graph is read*/
	public void fileRead(String name) 
	{
		try
		{
        		BufferedReader inFile = new BufferedReader(new FileReader(name)); 
			fileReadSize(inFile);
			for (int i = 1; i <= n; i++)
			{
				StringTokenizer tokenFinder = new StringTokenizer(inFile.readLine());
				goIth(Integer.parseInt(tokenFinder.nextToken()));
				tokenFinder.nextToken();  // read the :
				fileReadAdjList(tokenFinder);
			}     
			inFile.close();
		} catch (IOException e)
		{
			// Cannot create graph because there was a problem reading from file
	  		System.err.println("error creating graph from file input");
	  		e.printStackTrace();
		}
	}  
	
	/**	Read the capacity of the graph from the infile and create all the vertices. <br>
		Analysis: Time = O(n), where n = number of vertices 
		@param infile input file reader */
	protected void fileReadSize(BufferedReader inFile) throws IOException
	{
       		int size = Integer.parseInt(inFile.readLine());
		if (size > capacity())
			throw new RuntimeException("The graph cannot hold that many verticies.");
		n = 0;
		int i = 1;
		while (i <= size)
		{
			vNewIth(null, i);
			i++;
		}
	}

	/**	Read adjacency list from the infile and create all the edges. <br> 
		Analysis: Time = O(m), where m = number of edges 
		@param infile input file reader */  
	protected void fileReadAdjList(StringTokenizer tokenFinder) throws IOException
	{    
		VertexUos u = item;
		int i = Integer.parseInt(tokenFinder.nextToken());      
 		while (i != 0)
		{
			goIth(i);
			VertexUos v = item;
			if (!adjacent(u, v))
				eNew(u, v);
			i = Integer.parseInt(tokenFinder.nextToken());
		}      
		goToItem(u);		
	}

	/**	String representation of the graph for output. <br>
		Analysis: Time = O(max(n, m)) */
	public String toString()
	{
		GraphPositionUos position = currentPosition();
		StringBuffer result = new StringBuffer();
		result.append(n + " ");      

		goFirst();
		while (!after())
		{
			result.append("\n" + item() + " : ");	  
			eGoFirst((VertexUos)item());
			while (!eAfter())
			{
				result.append(" " + adjItem());
				eGoForth();
			}
			result.append(" 0 ");
			goForth();
		}
		goPosition(position);
		return new String(result);
	}

	/**	A shallow clone of this object. <br> 
		Analysis: Time = O(1) */
	public Object clone()
	{
		try
		{
			return super.clone();
		} catch (CloneNotSupportedException e)
		{
			// Should not occur: this is a ContainerUos, which implements Cloneable 
			e.printStackTrace();
 			return null;
		}
	}

	/**	The ith vertex of the graph. <br>
		Analysis: Time = O(1) */
	protected VertexUos vertexArrayItem(int i)
	{
		/* Vertices 1 through n are stored in 0 through n - 1. */
		return vertexArray[i - 1];
	}

	/**	Set the ith vetex of the graph. <br>
		Analysis: Time = O(1) */
	protected void vertexArraySetItem(VertexUos v, int i)
	{
		/* Vertices 1 through n are stored in 0 through n - 1. */
		vertexArray[i - 1] = v;
	}
}