graphlinkedrepuos.java

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

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

import dslib.list.*;
import dslib.exception.*;

/**	A graph with n vertices and m edges using a linked list to store the list of
	adjacent vertices for each vertex.  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 GraphLinkedRepUos extends GraphUos
{
	/**	Internal representation of adjacency list. */
	protected LinkedListUos[ ] adjListsArray;
    
	/**	Construct an undirected graph with capacity for up to cap vertices. <br> 
		Analysis: Time  = O(cap) 
		@param cap maximum number of verticies in the graph */
	public GraphLinkedRepUos(int cap)
	{
		super(cap);
		adjListsArray = new LinkedListUos[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) <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 undirected */
	public GraphLinkedRepUos(int cap , String graphChoice) throws InvalidArgumentUosException
	{
		super(cap, graphChoice);
		adjListsArray = new LinkedListUos[cap];
	}

	/**	Construct and insert a vertex with index id into the graph. <br> 
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			!isFull() <br>
			!(vertexList[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 insert another vertex since the graph is full.");
		if (vertexArrayItem(id) != null) 
			throw new DuplicateItemsUosException("Cannot insert a vertex that already exists.");		
		
		super.vNewIth(name, id);
		adjListsArraySetItem(new LinkedListUos(), id);
	}
  
	/**	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) 
	{
		EdgeUos newEItem = createNewEdge(v1, v2);
		adjListsArrayItem(v1.index).insertLast(newEItem);
		if (!directed)
			adjListsArrayItem(v2.index).insertLast(newEItem);
		m++;
	}
  
	/**	Move to the edge (v1, v2), if it exists. <br>
		Analysis: Time = O(n), where n = size of the edge list associated with v1
		@param v1 initial vertex of the edge being sought
		@param v2 terminal vertex of the edge being sought */
	public void eSearch(VertexUos v1, VertexUos v2) 
	{
		eGoFirst(v1);
		while (!eAfter() && (adjItem() != v2))
			eGoForth();
	}

	/**	Delete the current edge and move to the next edge for the vertex being iterated. <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.");

		adjListsArrayItem(((VertexUos)eItem.firstItem()).index).delete(eItem);
		if (!directed)
			adjListsArrayItem(((VertexUos)eItem.secondItem()).index).delete(eItem);
		if (adjListsArrayItem(((VertexUos)eItem.firstItem()).index).after())
			eItem = null;
		else 
			eItem = (EdgeUos)adjListsArrayItem(((VertexUos)eItem.firstItem()).index).item();
		m--;
	}
  
	/**	Go to the first edge of v1 starting edge list iteration. <br>
		Analysis: Time = O(1) 
		@param v1 The vertex whose adjacency list is to be iterated */
	public void eGoFirst(VertexUos v1)
	{
		iterationIndex = v1.index();
		LinkedListUos adjList = adjListsArrayItem(iterationIndex);
		adjList.goFirst();

		if (adjList.after())
			eItem = null;
		else
			eItem = (EdgeUos)adjList.item();
	}
  
	/**	Go to the next edge of the edge list being scanned. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			!eAfter() 
		</ul> */
	public void eGoForth() throws AfterTheEndUosException
	{
		if (eAfter())
			throw new AfterTheEndUosException("Cannot proceed to next edge since already after.");
	
		LinkedListUos adjList = adjListsArrayItem(iterationIndex);
		adjList.goForth();
		if (adjList.after())
			eItem = null;
		else
			eItem = (EdgeUos)adjList.item();
	}
  
	/**	Are we after the last edge for current adjacency list?. <br>  
		Analysis: Time = O(1) */
	public boolean eAfter()
	{
		return adjListsArrayItem(iterationIndex).after();
	}

	/**	The index of the adjacency vertex for an edge list iteration. <br>
		Analysis: Time = O(1) */
	public int adjIndex()
	{
		int result = 0;

		if (eItemExists())
			result = adjItem().index();
		else
			result = capacity();
		return result;
	}

	/**	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)
	{
		GraphPositionUos position = currentPosition();
		eSearch(v1, v2);
		boolean result = (eItem != null);      
		goPosition(position);
		return result;
	}
  
	/**	Remove all vertices from the graph. <br>
		Analysis: Time = O(capacity) */
	public void wipeOut()
	{
		super.wipeOut();
		for (int i = 1; i <= adjListsArray.length; i++) // wipe out array
			adjListsArraySetItem(null, i);
	}

	/**	The current position in the graph. <br>
		Analysis: Time = O(1) */
	public GraphPositionUos currentPosition()
	{
		if (iterationIndex != 0)
			return new GraphLinkedRepPositionUos(item, itemIndex, iterationIndex, 
			                         eItem, adjListsArrayItem(iterationIndex).currentPosition());
		else
			return new GraphLinkedRepPositionUos(item, itemIndex, iterationIndex, eItem, null);
	}
    
	/**	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)
	{
		GraphLinkedRepPositionUos linkedPos = (GraphLinkedRepPositionUos) pos;
		item = linkedPos.item;
		itemIndex = linkedPos.itemIndex;
		iterationIndex = linkedPos.iterationIndex;
		eItem = linkedPos.eItem;
		if (iterationIndex != 0)
			adjListsArrayItem(iterationIndex).goPosition(linkedPos.listPosition);
	}

	/**	The ith adjacency list of the graph. <br>
		Analysis: Time = O(1) */
	protected LinkedListUos adjListsArrayItem(int i)
	{
		/* lists 1 through n are stored in 0 through n-1. */
		return adjListsArray[i-1];
	}

	/**	Set the ith adjacency list of the graph. <br>
		Analysis: Time = O(1) */
	protected void adjListsArraySetItem(LinkedListUos x, int i)
	{
		/* vertices 1 through n are stored in 0 through n-1. */
		adjListsArray[i-1] = x;
	}
}