/*
 * Copyright 2009 Wishnu Prasetya.
 *
 * You can redistribute and/or modify this class under the terms of 
 * the GNU General Public License (GPL) as published by the Free 
 * Software Foundation; either version 3 of the License, or any
 * later version.
 */

package Sequenic.Graph;

import java.util.* ;

/**
 * Utility to calculate the prime paths of a graph.
 * 
 * @author Wishnu Prasetya
 */
public class PrimePathUtil {
	
	/**
	 * This will return all maximal paths starting from a root in the graph,
	 * plus all cycles in the graph. This should correspond to the set of
	 * prime paths through the graph.
	 * 
	 * <p>This is a different prime path algorithm than that of Maaike's.
	 * She's based on Ammann & Offutt.
	 * 
	 * <p>A root is here defined as a vertex with no parent. Note that some
	 * graphs may thus have no root.
	 */
	static public LinkedList<LinkedList> getPrimePaths(Graph g) {
		
		LinkedList<LinkedList> allpaths = new LinkedList<LinkedList>() ;
		
		List<Vertex> roots = g.orphans() ;
		
		for (Vertex R : roots)
			allpaths.addAll(g.getMaxPaths(R)) ;
		
		allpaths.addAll(g.getCycles()) ;

		return allpaths  ;
	}
	
	/**
	 * A variant of getPrimePaths where you can pass a "root". If this 
	 * root is as defined above (a vertex with no parent), then this
	 * method will behave the same as the other getPrimePaths.
	 * 
	 * <p>Otherwise it will add all maximal paths starting from the given
	 * root.
	 */
	static public LinkedList<LinkedList> getPrimePaths(Graph g, Vertex root) {
		List<Vertex> roots = g.orphans() ;		
		if (! roots.contains(root) ) {
			LinkedList<LinkedList> allpaths = g.getMaxPaths(root) ;
			allpaths.addAll(getPrimePaths(g)) ;
			return allpaths ;
		}
		else return getPrimePaths(g) ;
	}

}