/** Made from the strong need of a mutable UnitGraph and BFS ordering.
 *
 * Bleh.
 * @author Kacper Wysocki */

package soot.toolkits.graph;
import java.util.*;

/** Why is it 'better'? Because it has BFS and a conversion routine
 * Feel free to add more convenience routines */
public class BetterMutableGraph extends HashMutableDirectedGraph {

	/** Build a MutableGraph from any other DirectedGraph */
	public BetterMutableGraph(DirectedGraph g){
		super();
		Iterator bfsit = traverseBFS(g,g.getHeads().get(0)).iterator();
		while(bfsit.hasNext()){
			Object node = bfsit.next();
			if(!containsNode(node))
				addNode(node);
			Iterator pit = g.getPredsOf(node).iterator();
			while(pit.hasNext()){
				Object pred = pit.next();
				if(!containsNode(pred))
					addNode(pred);
				addEdge(pred,node);
			}
			pit = g.getSuccsOf(node).iterator();
			while(pit.hasNext()){
				Object succ = pit.next();
				if(!containsNode(succ))
					addNode(succ);
				addEdge(node,succ);
			}
		}
	}

	/** Breadth-first traversal of the graph.
	 *
	 * Don't be silly: keep in mind that BFS will only find the
	 * connected component reachable from the given start.
	 * @return bfs-ordered list of nodes
	 */
	public static List traverseBFS(DirectedGraph g, Object start){
		ArrayList bfs = new ArrayList();
		ArrayList visit = new ArrayList();
		visit.add(start);
		while(!visit.isEmpty()){
			Object node = visit.remove(0);
			bfs.add(node);
			Iterator it = g.getSuccsOf(node).iterator();
			while(it.hasNext()){
				Object child = it.next();
				if(!bfs.contains(child)){
					visit.add(child);
				}
			}
		}
		return bfs;
	}

	/** Depth-first traversal of the graph.
	 *
	 * @return dfs-ordered list of nodes
	 */
	public static List traverseDFS(DirectedGraph g, Object start){
		ArrayList dfs = new ArrayList();
		Stack visit = new Stack();
		visit.push(start);
		while(!visit.isEmpty()){
			Object node = visit.pop();
			dfs.add(node);
			Iterator it = g.getSuccsOf(node).iterator();
			while(it.hasNext()){
				Object child = it.next();
				if(!dfs.contains(child)){
					visit.push(child);
				}
			}
		}
		return dfs;
	}
/** Get all strongly connected components of the graph that have more
 * than one element.
 * See dava for origins.
 */
	public static List scComponents(DirectedGraph cfg){
		List components = new ArrayList();
		StronglyConnectedComponents scc = new StronglyConnectedComponents(cfg);
		Iterator scomit = scc.getComponents().iterator();
		while (scomit.hasNext()) {
			List wcomp = (List) scomit.next();
			if (wcomp.size() > 1)
				components.add( wcomp);
		}
		return components;
	}
}