package weka.clusterers.forMetisMQI;

import java.awt.Color;
import java.awt.Dimension;
import java.awt.Paint;
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 javax.swing.JFrame;

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 edu.uci.ics.jung.algorithms.flows.EdmondsKarpMaxFlow;
import edu.uci.ics.jung.algorithms.layout.FRLayout;
import edu.uci.ics.jung.algorithms.layout.KKLayout;
import edu.uci.ics.jung.algorithms.layout.Layout;
import edu.uci.ics.jung.graph.DirectedGraph;
import edu.uci.ics.jung.graph.DirectedSparseGraph;
import edu.uci.ics.jung.graph.Graph;
import edu.uci.ics.jung.visualization.BasicVisualizationServer;
import edu.uci.ics.jung.visualization.decorators.ToStringLabeller;

public class MQI {
	
	static int i = -1;
	
	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) && ((Integer)edgeFlowMap.get(reverseEdge) < reverseEdge.getCapacity())) {
					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);
		
		
		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)) {
					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.getSubgraph().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>();
			// This Factory produces new edges for use by the algorithm
			i=-1;
			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.getSmallerSubgraph().getVertexCount() * bisection.edgeCut() / 2; 
			alg.evaluate();
			System.out.println("MAX FLOW: " + alg.getMaxFlow() + " THRESHOLD: " + maxFlowThreshold);
			if(alg.getMaxFlow() < maxFlowThreshold) {
				Set<Node> sinkPartition = alg.getNodesInSinkPartition();
				System.out.println(sinkPartition);
				Set<Node> sourcePartition = alg.getNodesInSourcePartition();
				System.out.println(sourcePartition);
				bisection = prepareBisection(bisection.getSmallerSubgraph().createInducedSubgraph(), sourcePartition, sinkPartition);
//				bisection = new Bisection(new Subgraph(bisection.getSmallerSubgraph().createInducedSubgraph(), BFSReversed(sink, directedGraph, edgeFlowMap)));
				System.out.println("NEW BISECTION: " + bisection.toString());
				cluster = sinkPartition;
			} else
				finished = true;
		}
		return cluster;
	}
	
	private static Bisection prepareBisection(UndirectedGraph g, Set<Node> sourcePartition, Set<Node> sinkPartition) {
		Bisection b = null;
		Subgraph sourceSubgraph = new Subgraph(g, sourcePartition);
		Subgraph sinkSubgraph = new Subgraph(g, sinkPartition);
		Subgraph subgraph = null;
		if(sourceSubgraph.getVertexCount() > sinkSubgraph.getVertexCount())
			subgraph =sourceSubgraph;
		else
			subgraph = sinkSubgraph;
		b = new Bisection(subgraph);
		return b;
	}
	
}