searchgraphmatrixrepuos.java

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

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

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

/**	A search graph with n vertices and m edges using an adjacency matrix to store
    the edge for each adjacent pair.  The graph is either directed 
  	or undirected dependent 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 Search, with and without 
	a trace of the search progress (methods dfs, dfsTrace, bfs, bfsTrace).  */
public class SearchGraphMatrixRepUos extends GraphMatrixRepUos
{
	
	/**	Construct a new undirected graph with capacity for up to cap vertices. <br>  
		Analysis: Time = O(cap*cap)
		@param cap maximum number of verticies in the graph */
	public SearchGraphMatrixRepUos (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*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 undirected */
	public SearchGraphMatrixRepUos(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);
	}
}