package weka.clusterers.forMetisMQI;

import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.Stack;

import org.apache.commons.collections15.Factory;
import org.apache.commons.collections15.Transformer;

import weka.clusterers.forMetisMQI.graph.Bisection;
import weka.clusterers.forMetisMQI.graph.Edge;
import weka.clusterers.forMetisMQI.graph.Node;
import weka.clusterers.forMetisMQI.graph.Subgraph;
import weka.clusterers.forMetisMQI.graph.UndirectedGraph;
import weka.clusterers.forMetisMQI.util.Util;
import edu.uci.ics.jung.algorithms.flows.EdmondsKarpMaxFlow;
import edu.uci.ics.jung.graph.DirectedGraph;
import edu.uci.ics.jung.graph.DirectedSparseGraph;

public class MQI {

	static int i = -1;

	static private Set<Node> DFSReversed(Node currentNode,
			DirectedGraph<Node, Edge> g, Map<Edge, Number> edgeFlowMap, Set<Node> marked) {
		Collection<Edge> inEdges = g.getInEdges(currentNode);
		Set<Node> result = new HashSet<Node>();
		result.add(currentNode);
		Iterator<Edge> inEdgesIterator = inEdges.iterator();
		while (inEdgesIterator.hasNext()) {
			Edge edge = inEdgesIterator.next();
			Node src = g.getSource(edge);
			Edge reverseEdge = g.findEdge(src, currentNode);
			if (reverseEdge != null && !marked.contains(src)) {
				int flow = (Integer) edgeFlowMap.get(reverseEdge);
				int capacity = reverseEdge.getCapacity();
				if (flow < capacity) {
					marked.add(src);
					result.addAll(DFSReversed(src, g, edgeFlowMap, marked));
				}
			}
		}
		return result;
	}



	static private Set<Node> BFSReversed(Node sink,
			DirectedGraph<Node, Edge> g, Map<Edge, Number> edgeFlowMap) {
		Set<Node> result = new HashSet<Node>();
		Set<Node> visitedNodes = new HashSet<Node>();
		Stack<Node> nodesToVisit = new Stack<Node>();
		result.add(sink);
		nodesToVisit.push(sink);
		while (!nodesToVisit.empty()) {
			Node currentNode = nodesToVisit.pop();
			visitedNodes.add(currentNode);
			Collection<Edge> inEdges = g.getInEdges(currentNode);
			Iterator<Edge> inEdgesIterator = inEdges.iterator();
			while (inEdgesIterator.hasNext()) {
				Edge edge = inEdgesIterator.next();
				Node src = g.getSource(edge);
				Edge reverseEdge = g.findEdge(src, currentNode);
				if (reverseEdge != null) {
					int flow = (Integer) edgeFlowMap.get(reverseEdge);
					int capacity = reverseEdge.getCapacity();
					if (flow < capacity) {
						if (!nodesToVisit.contains(src)
								&& !visitedNodes.contains(src)) {
							nodesToVisit.push(src);
						}
						result.add(src);
					}
				}
			}
		}
		return result;
	}

	static private DirectedGraph<Node, Edge> prepareDirectedGraph(
			Bisection partition, Node source, Node sink) {
		Subgraph A = null;
		Subgraph B = null;
		if (partition.getSubgraph().getVertexCount() < partition
				.getComplement().getVertexCount()) {
			A = partition.getSubgraph();
			B = partition.getComplement();
		} else {
			A = partition.getComplement();
			B = partition.getSubgraph();
		}
		int a = A.getVertexCount();
		int c = partition.edgeCut() / 2;

		DirectedGraph<Node, Edge> g = new DirectedSparseGraph<Node, Edge>();
		Iterator<Node> nodes = A.iterator();
		while (nodes.hasNext()) {
			Node u = nodes.next();
			g.addVertex(u);
		}

		nodes = A.iterator();
		int id = 0;
		while (nodes.hasNext()) {
			Node u = nodes.next();
			Iterator<Node> neighbors = A.getNeighbors(u).iterator();
			while (neighbors.hasNext()) {
				Node v = neighbors.next();
				g.addEdge(new Edge(Integer.toString(id), A.getWeight(u, v), a),
						u, v);
				id++;
			}
		}

		g.addVertex(source);
		g.addVertex(sink);

		
		//build the edges from source to each node of A which previously was connected
		//with a node of B.
		nodes = B.iterator();
		while (nodes.hasNext()) {
			Node u = nodes.next();
			Iterator<Node> neighbors = B.getGraph().getNeighbors(u).iterator();
			while (neighbors.hasNext()) {
				Node v = neighbors.next();
				if (A.contains(v)) {
					Edge e = g.findEdge(source, v);
					if(e != null) {
						e.setCapacity(e.getCapacity() + a);
					} else {
						g.addEdge(new Edge(Integer.toString(id), 1, a), source, v);
						id++;
					}
				}
			}
		}

		nodes = A.iterator();
		while (nodes.hasNext()) {
			Node u = nodes.next();
			g.addEdge(new Edge(Integer.toString(id), 1, c), u, sink);
			id++;
		}
		return g;
	}

	/**
	 * Given a partion of a graph, execute the Max-Flow Quotient-cut Improvement
	 * algorithm, to find an improved cut and then returns the cluster which
	 * yields the best quotient cut.
	 * 
	 * @param partition
	 * @return
	 */
	static public Set<Node> mqi(Bisection partition) {
//		System.out.println("INITIAL BISECTION: " + partition.toString());
		boolean finished = false;
		Bisection bisection = partition;
		Set<Node> cluster = new HashSet<Node>(partition
				.getSmallerNotEmptySubgraph().createInducedSubgraph()
				.getVertices());
		int maxFlowThreshold = Integer.MAX_VALUE;
		while (!finished) {
			Node source = new Node("$$$$S");
			Node sink = new Node("$$$$T");
			DirectedGraph<Node, Edge> directedGraph = prepareDirectedGraph(
					bisection, source, sink);
			Transformer<Edge, Number> capTransformer = new Transformer<Edge, Number>() {
				public Double transform(Edge e) {
					return (double) e.getCapacity();
				}
			};
			Map<Edge, Number> edgeFlowMap = new HashMap<Edge, Number>();
			i = -1;
			// This Factory produces new edges for use by the algorithm
			Factory<Edge> edgeFactory = new Factory<Edge>() {
				public Edge create() {
					i++;
					return new Edge("$$$$" + Integer.toString(i), 1, 1);
				}
			};
			EdmondsKarpMaxFlow<Node, Edge> alg = new EdmondsKarpMaxFlow<Node, Edge>(
					directedGraph, source, sink, capTransformer, edgeFlowMap,
					edgeFactory);

			maxFlowThreshold = bisection.getSmallerNotEmptySubgraph()
					.getVertexCount()
					* bisection.edgeCut() / 2;
			alg.evaluate();
//			Util.viewFlowGraph(directedGraph, edgeFlowMap);
//			System.out.println("MAX FLOW: " + alg.getMaxFlow() + " THRESHOLD: "
//					+ maxFlowThreshold);
			if (alg.getMaxFlow() < maxFlowThreshold) {
				cluster = DFSReversed(sink, directedGraph, edgeFlowMap, new HashSet<Node>());
				cluster.remove(sink);
				 bisection = new Bisection(new Subgraph(bisection.getGraph(),
				 cluster));
//				System.out.println("NEW BISECTION: " + bisection.toString());
			} else
				finished = true;
		}
		return cluster;
	}

}