package weka.clusterers.forMetisMQI;

import java.awt.Dimension;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

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.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;
	
	public static void viewGraph(Graph<Node, Edge> g){
		Layout<Node, Edge> layout = new KKLayout<Node, Edge>(g);
		layout.setSize(new Dimension(800,600)); // sets the initial size of the space
		// The BasicVisualizationServer<V,E> is parameterized by the edge types
		BasicVisualizationServer<Node,Edge> vv =
		new BasicVisualizationServer<Node,Edge>(layout);
		vv.setPreferredSize(new Dimension(800,600)); //Sets the viewing area size
		vv.getRenderContext().setVertexLabelTransformer(new ToStringLabeller<Node>());
		vv.getRenderContext().setEdgeLabelTransformer(new ToStringLabeller<Edge>());

		JFrame frame = new JFrame("Simple Graph View");
		frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
		frame.getContentPane().add(vv);
		frame.pack();
		frame.setVisible(true);
	}

	/**
	 * Given a bisection, returns the cardinality of the larger subgraph.
	 * @param b
	 * @return
	 */
	static private int getMaxCardinality(Bisection b) {
		Subgraph A = null;
		if(b.getSubgraph().getVertexCount() > b.getComplement().getVertexCount()) {
			A = b.getSubgraph();
		}
		else {
			A = b.getComplement();
		}
		return A.getVertexCount();
	}
	
	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;
	}
	
	static public Bisection mqi(Bisection partition) {
		boolean finished = false;
		Bisection bisection = partition;
		int maxFlowThreshold = Integer.MAX_VALUE;
		while (!finished) {
			UndirectedGraph startingGraph = partition.getGraph();
			Node source = new Node("S");
			Node sink = new Node("T");
			DirectedGraph<Node, Edge> g = 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>(
					g, source, sink, capTransformer, edgeFlowMap, edgeFactory);
			
			maxFlowThreshold = getMaxCardinality(bisection) * bisection.edgeCut() / 2; 
			alg.evaluate();
			if(alg.getMaxFlow() < maxFlowThreshold) {
				Set<Node> sinkPartition = alg.getNodesInSinkPartition();
				Set<Node> sourcePartition = alg.getNodesInSourcePartition();
				bisection = prepareBisection(startingGraph, sourcePartition, sinkPartition);
			} else
				finished = true;
		}
		return bisection;
	}
	
	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;
	}
	
}