searchgraphlinkedrepuos.java

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

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

import dslib.dispenser.LinkedQueueUos;
import dslib.exception.*;
import dslib.base.PairUos;
import dslib.list.*;

/**	A search 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 constructor used.  The current vertex (for searches
	and iteration) is item, and the current edge (for searches and iteration) is eItem.
	The vertices are search vertices, and edges are standard edges. The class implements 
	depth- and breadth-first searches, with and without a trace of the search 
	progress (methods dfs, dfsTrace, bfs, bfsTrace).  */
public class SearchGraphLinkedRepUos extends GraphLinkedRepUos
{
	/**	Construct a new undirected graph with capacity for up to cap vertices. <br>
		Analysis: Time  = O(cap)
		@param cap maximum number of verticies in the graph */
	public SearchGraphLinkedRepUos(int cap)
	{
		super(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 SearchGraphLinkedRepUos(int cap, String graphChoice)throws InvalidArgumentUosException
	{
		super(cap, graphChoice);
	}
  
	/**	Return a new vertex that is appropriate for this graph, i.e., a SearchVertexUos. <br>
		Analysis: Time = O(1)
		@param n The name of the vertex that is returned
		@param id The id of the vertex that is returned */
	protected VertexUos createNewVertex(String n, int id)
	{
		return new SearchVertexUos(n, id);
	}

	/**	Depth-first search of the graph. <br> 
		Analysis: Time = O(n + m) 
		@param v The start vertex for the depth first search */
	public void dfs(SearchVertexUos v)
	{
		setAllUnreached();
		scan(v);
	}


	/**	Set all the vertices to unreached. <br>
		Analysis: Time = O(n), where n = number of vertices */
	public void setAllUnreached()
	{
		GraphPositionUos position = currentPosition();
		goFirst();
		while (!after())
		{
			((SearchVertexUos)item()).setReached(false);
			goForth();
		}
		goPosition(position);
	}
  
	/**	Scan v and all of its dfs descendants (used for dfs). <br>
		Analysis: Time = O(n + m), where n = number of vertices, m = nuber of edges
		@param v The vertex whose adjacency list is to be scanned */
	public void scan(SearchVertexUos v)
	{
		GraphPositionUos position = currentPosition();
		v.setReached(true);
		eGoFirst(v);
		while (!after())
		{
			if (!((SearchVertexUos)adjItem()).reached())
				scan((SearchVertexUos)adjItem());
			goForth();
		}
		goPosition(position);
	}
	
	/**	Depth-first search of the graph printing vertices and edges. <br>
		Analysis: Time = O(n + m) 
		@param v The start vertex for the depth first search */
	public void dfsTrace(SearchVertexUos v)
	{		
		setAllUnreached();
		scanTrace(v, "");
	}

	/**	Print v and its unreached dfs descendents each preceded by indent. <br> 
		Analysis: Time = O(n + m), where n = number of unreached vertices
		@param v vertex to search the graph for 
		@param indent indent to use in printing out the graph */
	public void scanTrace(SearchVertexUos v, String indent)
	{	
		GraphPositionUos position = currentPosition(); 
		v.setReached(true);
		System.out.print("\n" + indent + v.toString());
		String edgeIndent =indent + "   ";
		String newIndent = indent + "          ";
		eGoFirst(v);
		while (! eAfter())
		{
			System.out.print("\n" + edgeIndent +  eItem().toString());
			if (!((SearchVertexUos) adjItem()).reached())
				scanTrace((SearchVertexUos) adjItem(), newIndent);
			 eGoForth();
		}
		goPosition(position);
	}

	/**	Breadth-first search of the graph. <br> 
		Analysis: Time = O(n + m)
		@param v The start vertex for the breadth first search */
	public void bfs(SearchVertexUos v)
	{		
		GraphPositionUos position = currentPosition();
		setAllUnreached();
		LinkedQueueUos q = new LinkedQueueUos();
		v.setReached(true);
		q.insert(v);
		while (!q.isEmpty())
		{	
			SearchVertexUos temp = (SearchVertexUos)q.item();
			q.deleteItem();
			eGoFirst(temp);

			while (!eAfter()) 
			{
				if (!((SearchVertexUos)adjItem()).reached())
				{
					((SearchVertexUos)adjItem()).setReached(true);
					q.insert(adjItem());
				}
				eGoForth();
			}
		}
		goPosition(position);
	}

	/**	Breadth-first search of the graph printing the vertices and edges. <br>
		Analysis: Time = O(n + m) 
		@param The start vertex for the breadth first search */
	public void bfsTrace(SearchVertexUos v)
	{
		GraphPositionUos position = currentPosition();
		setAllUnreached();
		LinkedQueueUos q = new LinkedQueueUos();
		v.setReached(true);
		System.out.print("\n" + v.toString() + " reached");
		q.insert(new PairUos(v, ""));
		while (!q.isEmpty())
		{
			PairUos deletePair = (PairUos)q.item();
			q.deleteItem();
			System.out.print("\n" + deletePair.secondItem().toString()
							 + deletePair.firstItem().toString());
			String edgeIndent = (String)deletePair.secondItem() + "   ";
			String newIndent = (String)deletePair.secondItem() + "          ";
			eGoFirst((VertexUos)deletePair.firstItem());
			while (!eAfter())
			{
				System.out.print("\n" + edgeIndent + eItem().toString());
				if (!((SearchVertexUos)adjItem()).reached())
				{
					((SearchVertexUos)adjItem()).setReached(true);
					System.out.print("  " + adjItem().toString() + " reached");
					q.insert(new PairUos(adjItem(), newIndent));
				}
				eGoForth();
			}
		}
		goPosition(position);
	}
}