graphuos.java

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

/* GraphUos.java
 * ---------------------------------------------
 * Copyright (c) 2001 University of Saskatchewan
 * All Rights Reserved
 * --------------------------------------------- */
 
package dslib.graph;

import dslib.base.*;
import dslib.dispenser.LinkedQueueUos;
import dslib.exception.*;
import java.io.*;
import java.util.StringTokenizer;

/**	A graph class that is the base of matrix and linked graph representations.  There are two
	constructors that provide the user with a choice of directed or undirected graph structures.
	This class has all the capabilities of a LinearIteratorUos (goBefore, goFirst, goForth, and
	goAfter) so the graph can be iterated in a linear manner.  There are two ways to construct
	a graph, using console io (read) or using a file input (fileRead). This class defines
	various abstract methods for traversing edges of the current vertex (eGoFirst, eGoForth, and
	eSearch), which are implemented in matrix and linked graph representations.  Classes that
	extend this class need to override the createNewEdge or createNewVertex methods, if they
	use specialized edges or vertices. */
public abstract class GraphUos implements LinearIteratorUos, ContainerUos
{
	/**	Array that stores each vertex in the position corresponding to its index. */
	protected VertexUos[ ] vertexArray;
  
	/**	Is the graph directed? Defaults to undirected. */
	protected boolean directed = false;

	/**	Is the graph directed?. <br> 
		Analysis: Time = O(1) */
	public boolean directed()
	{
		return directed;
	}

	/**	Construct a new undirected graph with capacity for up to cap vertices. <br>
		Analysis: Time = O(cap)
		@param cap maximum number of verticies allowed in the graph */
	public GraphUos(int cap)
	{
		vertexArray = new VertexUos[cap];
		directed = false;
	}
  
	/**	Construct a new graph with capacity for up to cap vertices, 
		and make it directed or undirected according to graphChoice. <br>
		Analysis: Time = O(cap) <br> 
		PRECONDITION: <br>
		<ul>
			((graphChoice.charAt(0) == 'u') || (graphChoice.charAt(0) == 'U')) 
			|| (( graphChoice.charAt(0) == 'd') || (graphChoice.charAt(0) == 'D')) 
		</ul>
		@param cap maximum number of verticies allowed in the graph
		@param graphChoice indicates whether the graph is directed or indirected */
	public GraphUos(int cap, String graphChoice) throws InvalidArgumentUosException 
	{
		vertexArray = new VertexUos[cap];
		if ((graphChoice.charAt(0) == 'u') || (graphChoice.charAt(0) == 'U'))
			directed = false;
		else if ((graphChoice.charAt(0) == 'd') || (graphChoice.charAt(0) == 'd'))
			directed = true;
		else
			throw new InvalidArgumentUosException("Invalid argument--graphChoice "
						+ "must be directed or undirected only");
	}

	/**	Return a new vertex whose type is appropriate for this graph.  This method
		should be overidden by classes that extend this class if they use a 
		specialized type of VertexUos. <br>
		Analysis: Time = O(1) 
		@param n The name of the new vertex
		@param id The id of the new vertex */
	protected VertexUos createNewVertex(String n, int id)
	{
		return new VertexUos(n, id);
	}

	/**	Return a new edge whose type is appropriate for this graph.  This method
		should be overridden by classes that extend this class if they use a 
		specialized type of EdgeUos. <br>
		Analysis: Time = O(1) 
		@param v1 The starting vertex of the edge that is returned
		@param v2 The terminating vertex of the edge that is returned */
	protected EdgeUos createNewEdge(VertexUos v1, VertexUos v2)
	{
		return new EdgeUos(v1, v2);
	}

	/**	Maximum number of vertices for the graph. <br>
		Analysis: Time = O(1) */
	public int capacity()
	{
		return vertexArray.length;
	}

	/**	Number of vertices. */
	protected int n;
  
	/**	Number of vertices. <br>
		Analysis: Time = O(1)*/
	public int n()
	{
		return n;
	}
  
	/**	Number of edges. */
	protected int m;
  
	/**	Number of edges. <br>
		Analysis: Time = O(1) */
	public int m()
	{
		return m;
	}

	/**	Current item (vertex). */
	protected VertexUos item;
  
	/**	Is there a current item?. <br> 
		Analysis: Time = O(1) */
	public boolean itemExists()
	{
		return item != null;
	}

	/**	The current item (vertex); returns an Object so it can safely be typecasted to VertexUos. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			itemExists()
		</ul>*/
	public Object item() throws NoCurrentItemUosException
	{
		if (!itemExists())
			throw new NoCurrentItemUosException("There is no item to return.");
		
		return item;
	}

	/**	Index of the current item. */
	protected int itemIndex;

	/**	Index of the current item. <br>
		Analysis: Time = O(1) */
	public int itemIndex()
	{
		return itemIndex;
	}

	/**	Is there a current edge?. <br> 
		Analysis: Time = O(1) */
	public boolean eItemExists()
	{
		return eItem != null;
	}
  
	/**	The current edge. */
	protected EdgeUos eItem;

	/**	The current edge. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			eItemExists()
		</ul> */
	public EdgeUos eItem() throws NoCurrentItemUosException
	{
		if (!eItemExists())
			throw new NoCurrentItemUosException("Cannot return an edge that does not exist.");
		
		return eItem;
	}

	/**	Set the current vertex (item) to be newItem. <br> 
		Analysis: Time = O(1) 
		@param newItem new vertex to be set as the current vertex */
	public void goToItem(VertexUos newItem) 
	{
		item = newItem;
		itemIndex = newItem.index;
	}

	/**	Construct and insert a vertex into the graph. <br>
		Analysis: Time = O(capacity) <br>
		PRECONDITION: <br>
		<ul>
			!isFull()
		</ul>
		@param name name of the new vertex */
	public void vNew(String name) throws ContainerFullUosException
	{
		if (isFull())
			throw new ContainerFullUosException("Cannot add another vertex since graph is full.");      
		
		int id;      
		if (vertexArrayItem(n + 1) == null)
			id = n + 1;
		else
		{
			id = 1;
			while (vertexArrayItem(id) != null)
				id++;
		}      
		vNewIth(name, id);
	}

	/**	Construct and insert a vertex with index id into the graph,
		where the index id cannot be used for any other vertex of the graph. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			!isFull() <br>
			vertexArrayItem(id) == null
		</ul>
		@param name name of the new vertex
		@param id index of the new vertex  */
	public void vNewIth(String name, int id) throws ContainerFullUosException, DuplicateItemsUosException
	{
		if (isFull())
			throw new ContainerFullUosException("Cannot add another vertex since graph is full.");
		if (vertexArrayItem(id) != null)
			throw new DuplicateItemsUosException("Cannot create vertex since index id is already used");      

		VertexUos newItem = createNewVertex(name, id);
		vertexArraySetItem(newItem, id);
		n++;
	}

	/**	Set item to refer to the vertex with name if found, or null if not found. <br>
		Analysis: Time = O(capacity)
		@param name name of the vertex being sought */
	public void search(String name)
	{
		int id = 1;
		while (id <= capacity() && (vertexArrayItem(id) == null || !vertexArrayItem(id).name.equals(name)))
			id++;      
		goIth(id);
	}

	/**	Is v1 adjacent to v2?. 
		@param v1 vertex to check if adjacent to v2
		@param v2 vertex to check if adjacent to v1*/
	public abstract boolean adjacent(VertexUos v1, VertexUos v2);
  
	/**	Does the graph have any vertices?. <br>  
		Analysis: Time = O(1) */
	public boolean isEmpty()
	{
		return n == 0;
	}
	
	/**	Does the graph have its maximum number of verticies?. <br>  
		Analysis: Time = O(1) */
	public boolean isFull()
	{
		return n == capacity();
	}

	/**	Delete the current item (vertex) and incident edges. <br>
		Analysis: Time = O(n + m)
		PRECONDITION: <br>
		<ul>
			itemExists() 
		</ul> */
	public void deleteItem() throws NoCurrentItemUosException
	{
		if (!itemExists())
			throw new NoCurrentItemUosException("Cannot delete an item that does not exist.");
		
		GraphPositionUos position = currentPosition();
		/* Need to search the graph to find and delete any incoming edges */
		VertexUos delItem = (VertexUos)item();
		goFirst();
		while (!after())
		{
			if (adjacent(delItem, (VertexUos)item())) 
			{
				eSearch(delItem, (VertexUos)item());
				deleteEItem();
			}
			if (adjacent((VertexUos)item(), (VertexUos)delItem))
			{
				eSearch((VertexUos)item(), (VertexUos)delItem);
				deleteEItem();
			}
			goForth();
		}
		goPosition(position);
		vertexArraySetItem(null, itemIndex);
		goIth(nextNonNullVertexIndex());
		n--;
	}
	
	/**	Is the current position after the last vertex?. <br> 
		Analysis: Time = O(1) */
	public boolean after()
	{
		return itemIndex > capacity();
	}

	/**	Is the current position before the first vertex?. <br> 
		Analysis: Time = O(1) */
	public boolean before()
	{
		return itemIndex < 1;
	}

	/**	Set item to refer to the vertex with index id. <br>
		Analysis: Time = O(1)
		@param id index of the vertex to become current */
	public void goIth(int id)
	{
		itemIndex = id;
		if (1 <= id && id <= capacity())
			item = vertexArrayItem(id);
		else
			item = null;
	}