/*
 * 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.io.Serializable;
import java.util.* ;


/**
 * Representing a graph.
 * 
 * @author Wishnu Prasetya
 *
 */
public class Graph implements Serializable {
	
	private static final long serialVersionUID = 1L;
	
	/**
	 * This holds the list of nodes of the graph.
	 */
	public List<Vertex> nodes = new LinkedList<Vertex>() ;
	
	public Graph() { super() ; } 
	
	/**
	 * This will recalculate the parents-set of each vertex.
	 * It is assumed that the children-sets are good.
	 */
	public void calcParents() {
		// Clean up parents-sets:
		for (Vertex v : nodes) {
			if (v.children == null) v.children = new LinkedList<Vertex>() ;
			if (v.parents == null) v.parents = new LinkedList<Vertex>() ;
			v.parents.clear();
		}
		// Recalculate:
		for (Vertex v : nodes) {
			for (Vertex child : v.children) child.parents.add(v) ;
		}
	}
	
	/**
	 * Return all vertices with no parent.
	 */
	public List orphans() {
		List res = new LinkedList() ;
		for (Vertex v : nodes) {
			if (v.parents == null || v.parents.isEmpty()) res.add(v) ;
		}
		return res ;
	}
	
	/**
	 * Return all vertices with no children.
	 */
	public List terminals() {
		List res = new LinkedList() ;
		for (Vertex v : nodes) {
			if (v.children == null || v.children.isEmpty()) res.add(v) ;
		}
		return res ;
	}
	
	/**
	 * Return all siblings of v. A vertex y is a sibling if it is not
	 * v itself and if v and y share the same parent.
	 */
	public List siblings(Vertex v) {
		List res = new LinkedList() ;
		if (v.parents == null) return res ;
		for (Vertex parent : v.parents) {
			for (Vertex S : parent.children) 
				if (! res.contains(S)) res.add(S) ;
		}
		return res ;
	}
	
	public int numberOfEdges() {
		int E = 0 ;
		for (Vertex v : nodes) 
			if (v.children == null) continue ;
			else E = E + v.children.size() ;
		return E ;
	}
	
	/**
	 * Return the number of vertices that have multiple branch-out
	 * edges.
	 */
	public int numberOfBranchingVertices(){
		int N = 0 ;
		for (Vertex v : nodes) 
			if (v.children != null && v.children.size()>0) 
				N = N + v.children.size() ;
		return N ;
	}
	
	
	/**
	 * This will perform a DFS, and as it goes it indentifies all cycles
	 * found in the way.
	 * 
	 * @param v  the current node during the DFS walk.
	 */
	private void findCycles(Vertex v,
			// LinkedList<Vertex> visited,
			LinkedList<Vertex> pathSoFar, 
			LinkedList<LinkedList> cyclesFound) {
		
		//System.out.println(">>> " + v.id) ;
		// a cycle is found! With v as the loop-head:
		if (pathSoFar.contains(v)) {
			LinkedList<Vertex> cycle = new LinkedList<Vertex>() ;
			boolean startCycle = false ;
			for (Vertex n : pathSoFar) {
				if (n==v) startCycle = true ;
				if (startCycle) cycle.add(n) ;
			}
			cycle.add(v) ;
			
			for (LinkedList<Vertex> C : cyclesFound) {
				if (isomorphicCycles(cycle,C)) return ;
			}
			// Else the cycle is new, add it:
			cyclesFound.add(cycle) ;
			return ;
		}
		
		// Not in the path-so-far, but v has beed visited; 
		// then no need to visit it again:
		//if (visited.contains(v)) return ;
		
		// Drop the visited list; forcing vertices to be visited only
		// once cause not all cycles all found!
		// Else v is an unvisited vertex:
		// visited.add(v) ;
		pathSoFar.add(v) ;
		for (Vertex child : v.children) {
			findCycles(child,pathSoFar,cyclesFound) ;
		}
		// This will remove v from path-so-far again:
		pathSoFar.removeLast() ;
			
	}
	
	/**
	 * Return true if two cycles are isomorphic.
	 */
	static private boolean isomorphicCycles(
			LinkedList<Vertex> c1,
			LinkedList<Vertex> c2) {
		int N = c1.size() ;
		if (N != c2.size()) return false ;
		int i ;
		Vertex c2head = c2.get(0) ;
		boolean found = false ;
		for (i=0; i<N-1; i++) {
			if (c1.get(i) == c2head) {
				found = true ;
				break ;
			}
		}
		if (!found) return false ;
		int j ;
		for (j=1; i+j<N-1; j++) 
			if (c1.get(i+j) != c2.get(j)) return false ;
		for (int k=0; k<i; k++) 
			if (c1.get(k) != c2.get(j+k)) return false ;
		return true ;
	}
	
	/**
	 * This will return all cycles in the graph. Each cycle will be
	 * represented with a list of the form e.g. [a,b,c,a]. 
	 * 
	 * <p> The first and the last element in the cycle is always 
	 * a loop/cycle head. That is, it is a vertex a such that it 
	 * has an incoming arrow from another vertex v which is not 
	 * part of the cycle. Note a cycle may in principle have multiple
	 * heads.
	 * 
	 * <p>Note that the order in which the vertices are sorted in the
	 * variable "nodes" influence the order with which cycles are listed,
	 * and how the nodes are ordered in each cycle.
	 */
	public LinkedList<LinkedList> getCycles() {
		
		//LinkedList<Vertex> visited = new LinkedList<Vertex>() ;
		LinkedList<Vertex> pathSoFar = new LinkedList<Vertex>() ;
		LinkedList<LinkedList> cycles = new LinkedList<LinkedList>() ;
		
		for (Vertex R : nodes)
			findCycles(R,pathSoFar,cycles) ;
		
		return cycles ;
	}

	
	private void getMaxPathsHelper(Vertex v,
			LinkedList<Vertex> currentPath,
			LinkedList<LinkedList> pathsCollected) {
		
		// v is part of cycle; don't count it:
		if (currentPath.contains(v)) return ;
		
		// else extend current-path with v:
		currentPath.add(v) ;
		
		// If v has no child, then current-path is maximal, add it:
		if (v.children == null || v.children.isEmpty()) {
			LinkedList<Vertex> P = new LinkedList<Vertex>(currentPath) ;
			pathsCollected.add(P) ;
			currentPath.remove(v) ;
			return ;
		}
		
		// Else recursion:
		for (Vertex child : v.children) {
			getMaxPathsHelper(child,currentPath,pathsCollected) ;
		}
		currentPath.remove(v) ;
	}
	
	/**
	 * This returns all maximal paths starting from v. A path (from v) is 
	 * maximal if it starts in v, contains no cycle, and ends in a terminal
	 * vertex (a vertex with no children).
	 */
	public LinkedList<LinkedList> getMaxPaths(Vertex v) {
		LinkedList<LinkedList> res = new LinkedList<LinkedList>() ;
		getMaxPathsHelper(v,new LinkedList<Vertex>(), res) ;
		return res ;
	}
	
	
	
	@Override
	public String toString() {
		StringBuffer res = new StringBuffer("Nodes and edges:") ;
		for (Vertex v : nodes) {
			res.append("\n   " + v + " --> ") ;
			if (v.children == null || v.children.isEmpty()) {
				res.append("no-children.") ;
				continue ;
			}
			int N = v.children.size() ;
			res.append(v.children.get(0).toString()) ;
			for (int i=1; i<N; i++)
				res.append(", " + v.children.get(i)) ; 
		}
				
		return res.toString() ;
	}
	
}