/*______________________________________________________________________________
 * 
 * org.eidola.util.GraphUtil
 * 
 * Part of the Eidola Kernel Reference Implementation
 * See http://eidola.org for oodles of relevant fun!
 * 
 *______________________________________________________________________________
 * 
 * Copyright 2000-2001 Paul Cantrell
 * 
 * This program is free software; you can redistribute it and/or modify it under
 * the terms of the GNU General Public License version 2, as published by the
 * Free Software Foundation. See the file LICENSE.html for more information.
 * 
 * This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY, including the implied warranty of MERCHANTABILITY or FITNESS
 * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License along with
 * this program; if not, write to the Free Software Foundation, Inc. / 59 Temple
 * Place, Suite 330 / Boston, MA 02111-1307 / USA.
 *_______________________________________________________________________________
 */

package org.eidola.util;

import java.util.*;

/**
	Graph utilities.
	
	@author Paul Cantrell
	@version [Development version]
*/

public class GraphUtil
	{
	/** Returns the set of all nodes reachable along directed paths
	 *  from a given node in a given graph.  The implementation is
	 *  smart about cycle detection. */
	
	static public Set reachableNodes(Set initial, GraphWalker walker)
		{
		Set
			nodes = new HashSet(),
			newNodes = new HashSet(initial),
			newerNodes = new HashSet();
		
		while(!newNodes.isEmpty())
			{
			nodes.addAll(newNodes);   // Put the new nodes in the current list.
			
			// Now put all the newly reachable nodes a list of even newer nodes.
			
			for(Iterator i = newNodes.iterator(); i.hasNext(); )
				newerNodes.addAll(walker.getEdgesFrom(i.next()));
			
			// Look through all the newer nodes
			
			newNodes.clear();
			for(Iterator i = newerNodes.iterator(); i.hasNext(); )
				{
				Object cur = i.next();
				if(!nodes.contains(cur))  // Put the ones we hadn't already found
					newNodes.add(cur);    // into the list of new nodes.
				}
			}
		
		return nodes;
		}
	
	private GraphUtil() { } // To prevent instantiation
	}