cyclegraphlinkedrepuos.java

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

import dslib.graph.*;

/**	A directed search graph with a function to determine whether 
	a specified vertex is within a cycle.  */
public class CycleGraphLinkedRepUos extends SearchGraphLinkedRepUos
{
	/**	Construct a new directed graph with capacity for up to cap vertices.
		Analysis: Time  = O(cap) */
	public CycleGraphLinkedRepUos(int cap)
	{
		super(cap);
		directed = true;
	}

	/**	Is there a cycle that includes s?
		Analysis: Time = O(n + m) */
	public boolean isInCycle(SearchVertexUos s)
	{
		setAllUnreached();
		return scanForPath(s, s);
	}

	/**	Test for a path from p that ends with an edge back to the origin vertex.
		Analysis: Time = O(n + m), where n = number of vertices, m = number of edges */
	public boolean scanForPath(SearchVertexUos p, SearchVertexUos origin)
	{
		GraphPositionUos position = currentPosition();
		boolean found = false;
		p.setReached(true);
		eGoFirst(p);
		while (!found & !eAfter())
			if (!((SearchVertexUos)adjItem()).reached())
			{
				/*	Continue the search from the unreached adjacent vertex. */
				found = scanForPath((SearchVertexUos)adjItem(), origin);
				if (!found)
					eGoForth();
			}
			else if (adjItem() == origin)
				found = true;
			else	
				/*	As adjacent vertex is reached, it has already been unsuccessfully searched. */
				eGoForth();
		goPosition(position);
		return found;
	}
}