package util;

import java.util.*;
import static java.lang.Math.*;
import static java.lang.Double.*;

/*
 * NOTES:
 * - Methods such as pathLength will only return correct distances after the
 *   lengths are computed by calling one of the pathfinding methods.
 * - Make sure that the parameterized type implements equals and hashCode!
 *   (It should work fine for common types like String and Integer.)
 */

/*
 * TODO:
 * - int countSpanningTrees()
 * - Graph<Graph<T>> SCCGraph()
 */

class Graph<T extends Comparable<T>> {
	private Map<T, Map<T, Double>> E, P; // edges, paths
	
	// Construct an empty graph
	Graph() {
		E = new HashMap<T, Map<T, Double>>();
		P = new HashMap<T, Map<T, Double>>();
	}
	
	// Construct a graph from a string describing it
	@SuppressWarnings("unchecked")
	Graph(String desc) {
		this();
		String[] lines = desc.split("[\n;]");
		for (String l : lines) {
			String[] parts = l.split("=>");
			String par = parts[0].trim();
			addNode((T) par);
			if (parts.length == 1)
				continue;
			String[] children = parts[1].split(",");
			for (String cdata : children) {
				if ((cdata = cdata.trim()).isEmpty())
					continue;
				String[] data = cdata.split(":");
				String c = data[0].trim(), w = data[1].trim();
				offerEdge((T) par, (T) c, Double.parseDouble(w));
			}
		}
	}
	
	Set<T> nodes() {
		return E.keySet();
	}
	boolean hasNode(T x) {
		return nodes().contains(x);
	}
	void addNode(T x) {
		E.put(x, new HashMap<T, Double>());
		P.put(x, new HashMap<T, Double>());
	}
	
	// Return the set of nodes to which x points
	Set<T> children(T x) {
		return E.get(x).keySet();
	}
	
	// Return the set of nodes which are reachable from src
	Set<T> reachableNodes(T src) {
		Set<T> union = new HashSet<T>(children(src));
		union.addAll(P.get(src).keySet());
		return union;
	}
	
	// Return the number of nodes in the graph
	int size() {
		return E.size();
	}
	
	@SuppressWarnings("unchecked")
	public boolean equals(Object o) {
		Graph<T> g = (Graph<T>) o;
		if (!g.nodes().equals(nodes()))
			return false;
		for (T x : E.keySet()) {
			if (!g.children(x).equals(children(x)))
				return false;
			for (T y : children(x))
				if (g.edgeLength(x, y) != edgeLength(x, y))
					return false;
		}
		return true;
	}
	
	public int hashCode() {
		int p = 0x345678;
		for (T x : nodes())
			p ^= x.hashCode();
		return p ^= size();
	}
	
	// Is there an edge from x to y?
	boolean hasEdge(T x, T y) {
		return E.get(x).containsKey(y);
	}
	
	// Is there a path from x to y?
	boolean hasPath(T x, T y) {
		return x == y || hasEdge(x, y) || P.get(x).containsKey(y);
	}
	
	// The length of the edge from x to y (infinity if there is no edge)
	double edgeLength(T x, T y) {
		return hasEdge(x, y)? E.get(x).get(y) : POSITIVE_INFINITY;
	}
	
	// The length of the shortest path from x to y (infinity if there is no path)
	double pathLength(T x, T y) {
		return x == y? 0 : min(edgeLength(x, y), P.get(x).containsKey(y)?
				P.get(x).get(y) : POSITIVE_INFINITY);
	}
	
	// Add an edge from x to y. If there already is an edge, the shorter one
	// will replace the longer one
	void offerEdge(T x, T y, double c) {
		if ((!hasEdge(x, y) || c < edgeLength(x, y)) && !isInfinite(c))
			E.get(x).put(y, c);
	}
	
	// Assert that there is a path from x to y of a certain distance. If a
	// shorter path is known, the call will be ignored. Used internally.
	void offerPath(T x, T y, double c) {
		if ((!hasPath(x, y) || c < pathLength(x, y)) && !isInfinite(c))
			P.get(x).put(y, c);
	}
	
	// Generate a simple adjacency list representation of the graph
	public String toString() {
		StringBuilder sb = new StringBuilder();
		boolean first = true;
		for (T x : nodes()) {
			if (first) first = false;
			else sb.append("\n");
			sb.append(x); sb.append(" => ");
			boolean firstC = true;
			for (T y : children(x)) {
				if (firstC) firstC = false;
				else sb.append(", ");
				sb.append(y); sb.append(':');
				sb.append(edgeLength(x, y));
			}
		}
		return sb.toString();
	}
	
	Graph<T> transpose() {
		Graph<T> tg = new Graph<T>();
		for (T x : nodes())
			tg.addNode(x);
		for (T x : nodes())
			for (T y : children(x))
				tg.offerEdge(y, x, edgeLength(x, y));
		return tg;
	}
	
	Graph<T> inducedSubgraph(Set<T> nodes) {
		Graph<T> isg = new Graph<T>();
		for (T x : nodes())
			isg.addNode(x);
		for (T x : nodes())
			for (T y : children(x))
				if (isg.hasNode(y))
					isg.offerEdge(x, y, edgeLength(x, y));
		return isg;
	}
	
	// Floyd-Warshall: Θ(N³)
	void floydWarshall() {
		for (T x : nodes())
			for (T y : nodes())
				for (T z : nodes())
					offerPath(y, z, pathLength(y, x) + pathLength(x, z));
	}
	
	// Dijkstra's: O(E log(N))
	void dijkstras(final T src) {
		TreeSet<T> Q = new TreeSet<T>(new Comparator<T>() {
			public int compare(T x, T y) {
				double diff = pathLength(src, x) - pathLength(src, y);
				if (diff == 0 || isNaN(diff)) return x.compareTo(y);
				return (int) Math.signum(diff);
			}
		});
		Q.addAll(nodes());
		while (!Q.isEmpty()) {
			T x = Q.first(); Q.remove(x);
			for (T y : children(x)) {
				if (!Q.remove(y)) continue;
				offerPath(src, y, pathLength(src, x) + pathLength(x, y));
				Q.add(y);
			}
		}
	}
	
	// Bellman-Ford: Θ(N E²)
	void bellmanFord(T src) {
		 for (int i = 0; i < size(); ++i)
			 for (T x : nodes())
				 for (T y : children(x))
					 offerPath(src, y, pathLength(src, x) + pathLength(x, y));
	}
	
	// Edmonds-Karp: O(N E²)
	double edmondsKarp(T src, T dst) {
		Map<T, T> P; Queue<T> Q; Map<T, Double> M;
		Map<T, Map<T, Double>> F = new HashMap<T, Map<T, Double>>();
		for (T x : nodes()) {
			F.put(x, new HashMap<T, Double>());
			for (T y : nodes())
				F.get(x).put(y, 0.0);
		}
		do {
			(P = new HashMap<T, T>()).put(src, src);
			(M = new HashMap<T, Double>()).put(src, POSITIVE_INFINITY);
			(Q = new LinkedList<T>()).offer(src);
			L: while (!Q.isEmpty()) {
				T x = Q.poll();
				for (T y : children(x)) {
					double cap = edgeLength(x, y), flow = F.get(x).get(y);
					if (cap > flow && !P.containsKey(y)) {
						P.put(y, x);
						M.put(y, min(M.get(x), cap - flow));
						if (y.equals(dst)) {
							while (!P.get(y).equals(y)) {
								x = P.get(y);
								F.get(x).put(y, F.get(x).get(y) + M.get(dst));
								F.get(y).put(x, F.get(y).get(x) - M.get(dst));
								y = x;
							}
							break L;
						}
						else Q.offer(y);
					}
				}
			}
		} while (P.containsKey(dst));
		double netF = 0;
		for (T x : children(src))
			netF += F.get(src).get(x);
		return netF;
	}
	
	// Find SCCs via transposition (CLRS): Θ(E)
	Set<Set<T>> SCCs() {
		Stack<T> S; T y;
		Set<T> seen = new HashSet<T>();
		LinkedList<T> topSort = new LinkedList<T>();
		for (T x : nodes()) {
			if (!seen.add(x)) continue;
			(S = new Stack<T>()).add(x);
			L: while (!S.isEmpty()) {
				for (T z : children(y = S.peek()))
					if (seen.add(z) && S.add(z))
						continue L;
				S.remove(y);
				topSort.addFirst(y);
			}
		}
		seen.clear();
		Graph<T> gt = transpose();
		Set<Set<T>> comps = new HashSet<Set<T>>();
		for (T x : topSort) {
			Set<T> comp = new HashSet<T>();
			(S = new Stack<T>()).add(x);
			while (!S.isEmpty()) {
				if (seen.add(y = S.pop()))
					comp.add(y);
				else continue;
				for (T z : gt.children(y))
					S.add(z);
			}
			if (!comp.isEmpty())
				comps.add(comp);
		}
		return comps;
	}
}