package Sequenic.Graph;

import java.util.*;
import org.junit.* ;

public class GraphTest1 {
	
	@Test
	public void test1() {
		System.out.println("\n*** No loop, one node has 2 parents.") ;
		Vertex root = new Vertex() ;
		Vertex v1 = new Vertex() ;
		Vertex v2 = new Vertex() ;
		root.id = 0 ;
		v1.id = 1 ;
		v2.id = 2 ;
		root.children.add(v1) ;
		root.children.add(v2) ;
		v1.children.add(v2) ;
		Graph g1 = new Graph() ;
		g1.nodes.add(root) ;
		g1.nodes.add(v1) ; g1.nodes.add(v2) ;  
		g1.calcParents() ;
		
		System.out.println("Graph:" + g1) ;
		LinkedList<LinkedList> cycles = g1.getCycles() ;
		
		// Cycles:
		System.out.println("Cycles:") ;
		for (LinkedList<Vertex> C : cycles)
			System.out.println("   " + PathUtil.pathSimpleShow(C)) ;
		assert cycles.size() == 0 ;
		
		// Maximal paths:
		LinkedList<LinkedList> paths = g1.getMaxPaths(root) ;
		System.out.println("Max. paths from " + root.id + ":") ;
		for (LinkedList<Vertex> P : paths)
			System.out.println("   " + PathUtil.pathSimpleShow(P)) ;
		assert paths.size() == 2 ;
		LinkedList<Vertex> P1 = paths.get(0) ;
		assert PathUtil.pathSimpleShow(P1).equals("[ 0, 1, 2 ]") ;
		LinkedList<Vertex> P2 = paths.get(1) ;
		assert PathUtil.pathSimpleShow(P2).equals("[ 0, 2 ]") ;
		
		// Prime paths:
		System.out.println("Prime paths:") ;
		paths = PrimePathUtil.getPrimePaths(g1,root) ;
		for (LinkedList<Vertex> P : paths)
			System.out.println("   " + PathUtil.pathSimpleShow(P)) ;
		assert paths.size() == 2 ;
		
	}
	
	@Test
	public void test2() {
		System.out.println("\n** Two roots, one (cross-) cycle.") ;
		Vertex v1 = new Vertex() ;
		Vertex v2 = new Vertex() ;
		Vertex v3 = new Vertex() ;
		Vertex v4 = new Vertex() ;
		Vertex v5 = new Vertex() ;
		v1.id = 1 ;
		v2.id = 2 ;
		v3.id = 3 ;
		v4.id = 4 ; v5.id = 5 ;
		v1.children.add(v3) ;
		v2.children.add(v4) ;
		v3.children.add(v4) ; v3.children.add(v5) ;
		v4.children.add(v3) ;
		Graph g1 = new Graph() ;
		g1.nodes.add(v1) ; g1.nodes.add(v2) ; g1.nodes.add(v3) ; g1.nodes.add(v4) ;
		g1.nodes.add(v5) ;
		g1.calcParents() ;
		
		System.out.println("Graph:" + g1) ;
		LinkedList<LinkedList> cycles = g1.getCycles() ;
		
		// Cycles:
		System.out.println("Cycles:") ;
		for (LinkedList<Vertex> C : cycles)
			System.out.println("   " + PathUtil.pathSimpleShow(C)) ;
		assert cycles.size() == 1 ;
		assert cycles.get(0).size() == 3 ;
		assert v3 == cycles.get(0).get(0) ;
		assert v4 == cycles.get(0).get(1) ;
		assert v3 == cycles.get(0).get(2) ;	
		
		// Max paths:
		LinkedList<LinkedList> paths = g1.getMaxPaths(v1) ;
		System.out.println("Max. paths from " + v1.id + ":") ;
		for (LinkedList<Vertex> P : paths)
			System.out.println("   " + PathUtil.pathSimpleShow(P)) ;
		assert paths.size() == 1 ;
		assert PathUtil.pathSimpleShow(paths.get(0)).equals("[ 1, 3, 5 ]") ;
		
		paths = g1.getMaxPaths(v2) ;
		System.out.println("Max. paths from " + v2.id + ":") ;
		for (LinkedList<Vertex> P : paths)
			System.out.println("   " + PathUtil.pathSimpleShow(P)) ;
		assert paths.size() == 1 ;
		assert PathUtil.pathSimpleShow(paths.get(0)).equals("[ 2, 4, 3, 5 ]") ;
		
		// Prime paths:
		System.out.println("Prime paths:") ;
		paths = PrimePathUtil.getPrimePaths(g1) ;
		for (LinkedList<Vertex> P : paths)
			System.out.println("   " + PathUtil.pathSimpleShow(P)) ;
		assert paths.size() == 3 ;
		
	}
	
	@Test
	public void test3() {
		System.out.println("\n*** One root, 2 cycles, nested.") ;
		Vertex v1 = new Vertex() ;
		Vertex v2 = new Vertex() ;
		Vertex v3 = new Vertex() ;
		Vertex v4 = new Vertex() ;
		v1.id = 1 ;
		v2.id = 2 ;
		v3.id = 3 ;
		v4.id = 4 ; 
		v1.children.add(v2) ;
		v2.children.add(v3) ;
		v3.children.add(v2) ;
		v3.children.add(v4) ; 
		v3.children.add(v1) ;
		Graph g1 = new Graph() ;
		g1.nodes.add(v1) ; g1.nodes.add(v2) ; g1.nodes.add(v3) ; g1.nodes.add(v4) ;
		g1.calcParents() ;
		
		System.out.println("Graph:" + g1) ;
		
		LinkedList<LinkedList> cycles = g1.getCycles() ;
		System.out.println("Cycles: " + cycles.size()) ;
		for (LinkedList<Vertex> C : cycles)
			System.out.println("   " + PathUtil.pathSimpleShow(C)) ;
		assert cycles.size() == 2 ;
		assert cycles.get(0).size() == 3 ;
		assert v2 == cycles.get(0).get(0) ;
		assert v3 == cycles.get(0).get(1) ;
		assert v2 == cycles.get(0).get(2) ;	
		assert cycles.get(1).size() == 4 ;
		assert v1 == cycles.get(1).get(0) ;
		assert v2 == cycles.get(1).get(1) ;
		assert v3 == cycles.get(1).get(2) ;	
		assert v1 == cycles.get(1).get(3) ;	

		LinkedList<LinkedList> paths = g1.getMaxPaths(v1) ;
		System.out.println("Max. paths from " + v1.id + ":") ;
		for (LinkedList<Vertex> P : paths)
			System.out.println("   " + PathUtil.pathSimpleShow(P)) ;
		assert paths.size() == 1 ;
		assert PathUtil.pathSimpleShow(paths.get(0)).equals("[ 1, 2, 3, 4 ]") ;
		
		// Prime paths:
		System.out.println("Prime paths:") ;
		paths = PrimePathUtil.getPrimePaths(g1,v1) ;
		for (LinkedList<Vertex> P : paths)
			System.out.println("   " + PathUtil.pathSimpleShow(P)) ;
		assert paths.size() == 3 ;
		
	}
	
	@Test
	public void test4() {
		System.out.println("\n*** One root, cycle with 2x branches within, --> 2 cycles.") ;
		Vertex v1 = new Vertex() ;
		Vertex v2 = new Vertex() ;
		Vertex v3 = new Vertex() ;
		Vertex v4 = new Vertex() ;
		v1.id = 1 ;
		v2.id = 2 ;
		v3.id = 3 ;
		v4.id = 4 ;
		v1.children.add(v2) ;
		v2.children.add(v3) ;
		v2.children.add(v4) ;
		v3.children.add(v4) ; 
		v4.children.add(v1) ;
		Graph g1 = new Graph() ;
		g1.nodes.add(v1) ; g1.nodes.add(v2) ; g1.nodes.add(v3) ; g1.nodes.add(v4) ;
		g1.calcParents() ;
		
		System.out.println("Graph:" + g1) ;
		
		LinkedList<LinkedList> cycles = g1.getCycles() ;
		System.out.println("Cycles: " + cycles.size()) ;
		for (LinkedList<Vertex> C : cycles)
			System.out.println("   " + PathUtil.pathSimpleShow(C)) ;
		assert cycles.size() == 2 ;
		LinkedList<Vertex> C1 = cycles.get(0) ;
		assert C1.size() == 5 ;
		assert v1 == C1.get(0) ;
		assert v2 == C1.get(1) ;
		assert v3 == C1.get(2) ;	
		assert v4 == C1.get(3) ;	
		assert v1 == C1.get(4) ;
		LinkedList<Vertex> C2 = cycles.get(1) ;
		assert C2.size() == 4 ;
		assert v1 == C2.get(0) ;
		assert v2 == C2.get(1) ;
		assert v4 == C2.get(2) ;	
		assert v1 == C2.get(3) ;	
		
		LinkedList<LinkedList> paths = g1.getMaxPaths(v1) ;
		System.out.println("Max. paths from " + v1.id + ":") ;
		for (LinkedList<Vertex> P : paths)
			System.out.println("   " + PathUtil.pathSimpleShow(P)) ;
		assert paths.size() == 0 ;
		
		// Prime paths:
		System.out.println("Prime paths:") ;
		paths = PrimePathUtil.getPrimePaths(g1,v1) ;
		for (LinkedList<Vertex> P : paths)
			System.out.println("   " + PathUtil.pathSimpleShow(P)) ;
		assert paths.size() == 2 ;
	}
	
	
	@Test
	public void test5() {
		System.out.println("\n*** 2 roots, 2 terminals, X-form.") ;
		Vertex root1 = new Vertex() ;
		Vertex root2 = new Vertex() ;
		Vertex middle = new Vertex() ;
		Vertex end1 = new Vertex() ;
		Vertex end2 = new Vertex() ;
		root1.id = 1 ;
		root2.id = 2 ;
		middle.id = 3 ;
		end1.id = 4 ;
		end2.id = 5 ;
		root1.children.add(middle) ;
		root2.children.add(middle) ;
		middle.children.add(end1) ;
		middle.children.add(end2) ; 
		Graph g1 = new Graph() ;
		g1.nodes.add(root1) ; g1.nodes.add(root2) ; 
		g1.nodes.add(end1) ; g1.nodes.add(end2) ;
		g1.nodes.add(middle) ;
		g1.calcParents() ;
		
		System.out.println("Graph:" + g1) ;
		
		// Cycles:
		LinkedList<LinkedList> cycles = g1.getCycles() ;
		System.out.println("Cycles: " + cycles.size()) ;
		for (LinkedList<Vertex> C : cycles)
			System.out.println("   " + PathUtil.pathSimpleShow(C)) ;
		assert cycles.size() == 0 ;
		
		// Paths:
		LinkedList<LinkedList> paths = g1.getMaxPaths(root1) ;
		System.out.println("Max. paths from " + root1.id + ":") ;
		for (LinkedList<Vertex> P : paths)
			System.out.println("   " + PathUtil.pathSimpleShow(P)) ;
		assert paths.size() == 2 ;
		assert PathUtil.pathSimpleShow(paths.get(0)).equals("[ 1, 3, 4 ]") ;
		assert PathUtil.pathSimpleShow(paths.get(1)).equals("[ 1, 3, 5 ]") ;
		
		paths = g1.getMaxPaths(root2) ;
		System.out.println("Max. paths from " + root2.id + ":") ;
		for (LinkedList<Vertex> P : paths)
			System.out.println("   " + PathUtil.pathSimpleShow(P)) ;
		assert paths.size() == 2 ;
		assert PathUtil.pathSimpleShow(paths.get(0)).equals("[ 2, 3, 4 ]") ;
		assert PathUtil.pathSimpleShow(paths.get(1)).equals("[ 2, 3, 5 ]") ;
		
		// Prime paths:
		System.out.println("Prime paths:") ;
		paths = PrimePathUtil.getPrimePaths(g1) ;
		for (LinkedList<Vertex> P : paths)
			System.out.println("   " + PathUtil.pathSimpleShow(P)) ;
		assert paths.size() == 4 ;

	}
	
	public class VORT extends Vertex {
		
	}
	
	@Test
	public void test6() {
		LinkedList<Vertex> V = new LinkedList<Vertex>() ;
		V.add(new VORT()) ;
		LinkedList<VORT> W = (LinkedList<VORT>) ((LinkedList) V) ;
		VORT a = W.getFirst() ;
	}
	
	
}