// GraphAlgs.java - mjd@cs.auckland.ac.nz
//
// edit log:  fixed off-by-one error in maxDistance           (30-Aug-2000)
//            fixed off-by-one error getBFSparents            (13-Sep-2000)
//            zero initialized parents[] in getBFSparents     (21-May-2006)
//            replaced Queue with LinkList from Java 1.5      (05-Sep-2006)
//            topSort1 now returns 0 for nodes not reached    (03-Sep-2007)


/*
//Update 	- Enumeration completely removed as the class now uses for each loops.
//			- many for incremental loops replaced with for each loops (basically if you used take the ith element in an integer array
//			you now use a for each element of the integer array.) <-- saves you casting and searching
//			- some of the new Integer(v) things have been changed to just v: where its obvious the addition is an integer;
//			i.e it is being added to an ArrayList<Integer>
//			-when making a undirected graph it now checks what the graph coming in is (either a matrix or lists form) then makes
//			the appropriate uGraph of it - FIXED
//          -edited graphADT to take conversion constructors allowing for uGraph = new uGraphLists(G);
//          where G is any representation of the Graph interface
*/


package graphAlgs;


import graphADT.*;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.LinkedList;

public class GraphAlgs{

	public static void getBFSparents(Graph G, int v, int[] parent){  // indices off by one
		int n = G.order();
		for (int i=0; i<n; i++) parent[i]=0;
		parent[v]=v+1;	// root is its own parent

		LinkedList<Integer> toGrow = new LinkedList<Integer>();
		toGrow.addLast(new Integer(v));

		while (toGrow.peek() != null){
			int grow = toGrow.removeFirst();
			ArrayList<Integer> nbrs = G.neighbors(grow);

			for (int i : nbrs){
				if (parent[i] == 0){
					parent[i] = grow+1;
					toGrow.addLast(new Integer(i));
				}
			}
		}
		return;
	}

	public static int BFS(Graph G, int v, int[] LevelOrder){
		int n = G.order();

		for (int i=0; i<n; i++) LevelOrder[i]=0;

		LinkedList<Integer> toGrow = new LinkedList<Integer>();
		int cnt = 0;

		LevelOrder[v] = ++cnt;
		toGrow.addLast(new Integer(v));

		while (toGrow.peek() != null){
			int grow = toGrow.removeFirst();

			ArrayList<Integer> nbrs = G.neighbors(grow);

			for (int i : nbrs){
				if ( LevelOrder[i] == 0 ){
					LevelOrder[i] = ++cnt;
					toGrow.addLast(new Integer(i));
				}
			}
		}
		return cnt;
	}

	private static class countPair{       // private counters for DFS search
		int cnt1, cnt2;
		int inc1() { return ++cnt1; }	// increment and return counters
		int inc2() { return ++cnt2; }
	}

	private static void doDFS(Graph G, int v, int[] PreOrder, int[] PostOrder, countPair cnt){
		PreOrder[v] = cnt.inc1();

		ArrayList<Integer> nbrs = G.neighbors(v);
		for (int i : nbrs){
			if ( PreOrder[i] == 0 ){
				doDFS(G, i, PreOrder, PostOrder, cnt);
			}
		}
		PostOrder[v] = cnt.inc2();
		return;
	}

	public static int DFS(Graph G, int v, int[] PreOrder, int[] PostOrder){
		int n = G.order();
		for (int i=0; i<n; i++) PreOrder[i] = PostOrder[i] = 0;

		// returns number of nodes reached
		//
		countPair cnt = new countPair();
		doDFS(G, v, PreOrder, PostOrder, cnt);
		return PostOrder[v];
	}

	public static boolean isConnected(Graph G){ // is underlying graph connected?
		//makes the incoming graph undirected then checks if its connected by BFSing it.
		if (G instanceof uGraph) { //check to see if its already an undirected graph
			int[] tmp = new int[G.order()];
			return BFS(G,0,tmp) == G.order();
		}else{
			//if its directed
			uGraph L = new uGraphLists(G);
			//uGraph L = new uGraphMatrix(G);
			int[] tmplist = new int[L.order()];
			return BFS(G,0,tmplist) == L.order();
		}
	}

	public static boolean isStronglyConnected(Graph G){
		int n = G.order();
		int[] pre = new int[n];
		int[] post = new int[n];

		if (DFS(G,0,pre,post) < n) return false;

		Graph R = new GraphAdjLists();      // create G with reversed arcs
//		Graph R = new GraphAdjMatrix();

		R.addVertices(n);
		//
		for (int i=0; i<n; i++){
			ArrayList<Integer> nbrs = G.neighbors(i);
			for (int k : nbrs){
				R.addArc(k,i);
			}
		}
		return (DFS(R,0,pre,post) == n);
	}

	public static ArrayList<Integer> strongComponents(Graph G){  // vector of subsets of V(G)
		ArrayList<Integer> SCC = new ArrayList<Integer>();
		// ....
		return SCC;
	}

	public static void getDFSparents(Graph G, int v, int[] parent){  // indices off by one
		if (parent[v]==0) parent[v]=v+1;	// root is its own parent
		ArrayList<Integer> nbrs = G.neighbors(v);

		for (int i : nbrs){
			if ( parent[i] == 0 ){
				parent[i]=v+1;
				getDFSparents(G, i, parent);
			}
		}
	}

	public static boolean isAcyclic(Graph G){ 	// no directed cycles?
		int n=G.order();
		int[] PreOrder = new int[n];
		int[] PostOrder = new int[n];
		boolean[] span = new boolean[n];

		for (int i=0; i<n; i++){    // check if any vertex is on a cycle
			if (span[i]) continue;  // try next component

			int cnt = DFS(G, i, PreOrder, PostOrder);

			for (int j=0; j<n; j++){
				if (PreOrder[j] > 0) span[j] = true;
//				if (PreOrder[j] <= 2) continue;  // no back-edge cycles

				ArrayList<Integer> nbrs = G.neighbors(j);

				for (int k : nbrs){
					if (// PreOrder[k] < PreOrder[j] &&
						PostOrder[k] > PostOrder[j] ) return false;  // Bingo!
						// note: PreOrder[k] > 0 since u is reachable from j
				}
			}

			if (cnt == n) break;  // all vertices spanned
		}
		return true;
	}

	public static boolean isAcyclic(uGraph G){ 	// no undirected cycles?
		int n=G.order();
		int m=G.size();

		// for O(n) running time [adjacency lists]
		if (m >= n) return false;

		int[] PreOrder = new int[n];
		int[] PostOrder = new int[n];
		countPair cnt = new countPair();

		int components = 0;

		for (int i=0; i<n; i++){
			if (PreOrder[i] > 0) continue;  // try next component with root i

			doDFS(G, i, PreOrder, PostOrder, cnt);

			components++;
		}
		return n == m + components;
	}

	public static int girth(Graph Gin){  	// returns minimum girth >= 3.

		//makes an undirected copy of Gin
		uGraph G = new uGraphLists(Gin);
		//uGraph G = new uGraphMatrix(Gin);

		int n=G.order();

		int best = n+1;		// girth n+1 if no cycles found

		for (int i=0; i<n-2; i++){  // look for a cycle from all but last two
			BitSet span = new BitSet(n);
			span.set(i);
			int depth = 1;		// do a BFS search keeping track of depth

			ArrayList<Integer> distList = new ArrayList<Integer>();
			distList.add(i);

			while (depth*2 <= best && best > 3){
				ArrayList<Integer> nextList = new ArrayList<Integer>();
				for(int e : distList){
					ArrayList<Integer> nbrs = G.neighbors(e);

					for (int k : nbrs){

						if (!span.get(k)){
 							span.set(k);
							nextList.add(k);
						}else{	// we have found some walk/cycle
							// is there a cross edge at this level
							//
							if ( distList.contains(k) ){
								best = depth*2-1; break;
							}
							// else even length cycle (as upper bound)
							//
							if ( nextList.contains(k) ){
								best = depth*2;
							}
						}
					}
				} // for vertices at current depth

				distList = nextList;	// next try set of vertices further away
				depth++;
			}
		}
		return best;
	}

	public static boolean isBipartite(Graph Gin){

		//makes an undirected copy of Gin
		uGraph G = new uGraphLists(Gin);		// color underlying graph
		//uGraph G = new uGraphMatrix(Gin);
		int n = G.order();
		int color[] = new int[n];           // will toggle between 1 and 2
		for (int v = 0; v < n; v++){		// start at first vertex
			if (color[v]>0) continue;
			color[v] = 1;

			LinkedList<Integer> toGrow = new LinkedList<Integer>();// use BFS queue search
			toGrow.addLast(new Integer(v));

			while (toGrow.peek() != null){
				int grow = toGrow.removeFirst();

				ArrayList<Integer> nbrs = G.neighbors(grow);

				for (int u : nbrs){
					if ( color[u] == 0 ){			// not colored yet
						color[u] = 3 - color[grow];	// set to other color
						toGrow.addLast(new Integer(u));
					}else{				// check for different color
						if ( color[u] == color[grow] ) return false;
					}
				}

			} // more nodes in this component

		} // while all components have been checked

		return true;
	}


	public static int[] topSort1(Graph G, int firstV){
		int n = G.order();
		int[] PreOrder = new int[n];
		int[] PostOrder = new int[n];
		int[] sort = new int[n];

		int cnt = DFS(G, firstV, PreOrder, PostOrder);

		for (int i=0; i<n; i++)
			if (PostOrder[i]>0) sort[i] = cnt-PostOrder[i]+1;

		return sort;
	}

	public static int[] topSort2(Graph G){
		int n = G.order();
		int[] sort = new int[n];

		int[] inDeg = new int[n];
		for (int i=0; i<n; i++) inDeg[i] = G.inDegree(i);

		int cnt = 0;
		boolean progress = true;
		//
		while (progress){
			progress = false;

			for (int v=0; v<n; v++){
				if (inDeg[v] == 0){
					sort[v] = ++cnt;
					progress = true;
					inDeg[v] = -1;

					ArrayList<Integer> nbrs = G.neighbors(v);
					for (int u : nbrs){
						inDeg[u] = inDeg[u] - 1;
					}
				}
			} // for v

		} // while nodes exist with inDegree == 0.

		return sort;
	}

  public static int maxDistance(Graph G, int v, int dist[]){
		int n = G.order();

		for (int i=0; i<n; i++) dist[i]=n;	// set to maximum distance

		int depth = 0;			// current max distance in BFS
		dist[v]=depth;
		int cnt = 1;

		ArrayList<Integer> distList = new ArrayList<Integer>();
		distList.add( new Integer(v) );

		while ( distList.size() > 0 ){
			depth++;
			ArrayList<Integer> nextList = new ArrayList<Integer>();
			for (int e : distList){
				ArrayList<Integer> nbrs = G.neighbors(e);
				for (int u : nbrs){
					if (dist[u] == n){
						dist[u] = depth;
						cnt++;
						nextList.add(u);
					}
				}
			}

			distList = nextList;	// next try set of vertices further away
		}

		return cnt == n ? depth-1 : n;
	}

	public static int[][] distanceMatrix(Graph G){
		int n = G.order();
		int D[][] = new int[n][n];

		for (int v=0; v<n; v++){
			//System.err.println("dist from " + v + " is " +
			maxDistance(G, v, D[v])
			//)
			;
		}
		return D;
	}

	public static int diameter(Graph G){
		int n = G.order();
		int max = 0;
		int [] dist = new int[n];

		for (int v=0; v<n; v++){
			int d = maxDistance(G, v, dist);
			max = d > max ? d : max;
		}

		return max;
	}


}  // class GraphAlgs