graphmatrixrepuos.java

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

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

import dslib.exception.*;

/**	A graph with n vertices and m edges using a matrix to store the edges
	between adjacent vertex pairs.  The graph is either directed or undirected depending
	upon the creation procedure used.  The current vertex (for searches
	and iteration) is item, and the current edge (for searches and iteration) is eItem. */
public class GraphMatrixRepUos extends GraphUos
{
	/**	Internal representation of adjacency list. */
	protected EdgeUos[ ][ ] adjMatrix;
  
	/**	The index of the adjacent vertex in the edge iteration. */
	protected int adjIndex = 0;
 
	/**	Construct a new undirected graph with capacity for up to cap vertices. <br> 
		Analysis: Time = O(cap * cap)
		@param cap maximum number of verticies allowed in the graph */
	public GraphMatrixRepUos(int cap)
	{
		super(cap);
		adjMatrix = new EdgeUos[cap][cap];
	}

	/**	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 * cap) 
		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 GraphMatrixRepUos(int cap, String graphChoice) throws InvalidArgumentUosException
	{
		super(cap, graphChoice);
		adjMatrix = new EdgeUos[cap][cap];
	}
  
	/**	Is v1 adjacent to v2?. <br> 
		Analysis: Time = O(degree(v1)), worst case
		@param v1 vertex to check if adjacent to v2
		@param v2 vertex to check if adjacent to v1 */
	public boolean adjacent(VertexUos v1, VertexUos v2)
	{
		return adjMatrixItem(v1.index, v2.index) != null;
	}
  
	/**	Construct and insert an edge with ends v1 and v2 into the graph. <br>
		Analysis: Time = O(1)
		@param v1 initial vertex of the new edge
		@param v2 terminal vertex of the new edge */
	public void eNew(VertexUos v1, VertexUos v2)
	{
		eItem = createNewEdge(v1, v2);
		adjMatrixSetItem(eItem, v1.index, v2.index);
		if (!directed)
			adjMatrixSetItem(eItem, v2.index, v1.index);
		m++;
	}
  
	/**	Move to edge (v1,v2), if it exists. <br>
		Analysis: Time = O(1)
		@param v1 initial vertex of the edge being sought
		@param v2 terminal vertex of the edge being soughtr */
	public void eSearch(VertexUos v1, VertexUos v2)
	{
		eItem = adjMatrixItem(v1.index, v2.index);
		iterationIndex = v1.index;
		adjIndex = v2.index;
	}
  
	/**	Remove all vertices from the graph. <br>
		Analysis: Time = O(capacity) */
	public void wipeOut()
	{
		super.wipeOut();
		for (int i = 1; i <= adjMatrix.length; i++)
			for (int j = 1; j <= adjMatrix.length; j++)
				adjMatrixSetItem(null, i, j);
	}

	/**	Go to the first edge of v1 starting an edge list iteration. <br> 
		Analysis: Time = O(n), worst case
		@param v1 vertex whose edges are to be iterated */
	public void eGoFirst(VertexUos v1)
	{
		iterationIndex = v1.index;
		adjIndex = 0;
		eGoForth();
	}
  
	/**	The index of the adjacent vertex in the edge iteration. <br>
		Analysis: Time = O(1) */
	public int adjIndex()
	{
		return adjIndex;
	}
  
	/**	Go to the next edge of the edge list being scanned. <br> 
		Analysis: Time = O(n), worst case <br>
		PRECONDITION: <br>
		<ul>
			!eAfter()
		</ul> */
	public void eGoForth() throws AfterTheEndUosException
	{
		if (eAfter())
			throw new AfterTheEndUosException("Cannot go to next edge since already after.");

		adjIndex = nextNonNullAdjIndex();
		if (eAfter())
			eItem = null;
		else
			eItem = adjMatrixItem(iterationIndex, adjIndex);
	}
  
	/**	Are we off the end of the edge list being scanned?. <br> 
		Analysis: Time = O(1) */
	public boolean eAfter()
	{
		return adjIndex >= capacity();
	}

	/**	Next nonnull vertex. <br>
		Analysis: Time = O(capcity) */
	protected int nextNonNullAdjIndex()
	{
		int result = adjIndex + 1;
		while ((result <= capacity()) && (adjMatrixItem(iterationIndex, result) == null))
			result++;
		return result;
	}

	/**	Delete the current edge. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			eItemExists()
		</ul> */ 
	public void deleteEItem() throws NoCurrentItemUosException
	{
		if (!eItemExists())
			throw new NoCurrentItemUosException("Cannot delete an item that does not exist.");
		
		adjMatrixSetItem(null, ((VertexUos)eItem.firstItem()).index, ((VertexUos)eItem.secondItem()).index);
		if (!directed)
			adjMatrixSetItem(null, ((VertexUos)eItem.secondItem()).index, ((VertexUos)eItem.firstItem()).index);
		adjIndex = nextNonNullAdjIndex();
		if (adjIndex >= capacity())
			eItem = null;
		else
			eItem = adjMatrixItem(iterationIndex, adjIndex);
		m--;
	}
	   
	/**	The current position in the graph. <br>
		Analysis: Time = O(1) */
	public GraphPositionUos currentPosition()
	{
		return new GraphMatrixRepPositionUos(item, itemIndex, iterationIndex, eItem, adjIndex);
	}

	/**	Go to the position pos of the graph. <br> 
		Analysis: Time = O(1) 
		@param pos The graph position that is to become the current position */
	public void goPosition(GraphPositionUos pos)
	{
		GraphMatrixRepPositionUos matrixPos = (GraphMatrixRepPositionUos) pos;
		item = matrixPos.item;
		itemIndex = matrixPos.itemIndex;
		iterationIndex = matrixPos.iterationIndex;
		eItem = matrixPos.eItem;
		adjIndex = matrixPos.adjIndex;
	}

	/**	The edge between the vertices with indices i and j. <br>
		Analysis: Time = O(1) */
	protected EdgeUos adjMatrixItem(int i, int j)
	{
		/*	Vertex indices 1 through n are mapped to 0 through n - 1. */
		return adjMatrix[i-1][j-1];
	}
	
	/**	Set the edge between the vertices with indices i and j. <br>
		Analysis: Time = O(1) */
	protected void adjMatrixSetItem(EdgeUos e, int i, int j)
	{
		/*	Vertex indices 1 through n are mapped to 0 through n - 1. */
		adjMatrix[i-1][j-1] = e;
	}
}