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> reversedLookup(Node sink, DirectedGraph<Node, Edge> g, Map<Edge, Number> edgeFlowMap) {
		Set<Node> result = new HashSet<Node>();
		Collection<Edge> inEdges = g.getInEdges(sink);
		Iterator<Edge> inEdgesIterator = inEdges.iterator();
		while (inEdgesIterator.hasNext()) {
			Edge edge = inEdgesIterator.next();
			Node src = g.getSource(edge);
			Edge reverseEdge = g.findEdge(src, sink);
			if ((reverseEdge != null)
					&& ((Integer) edgeFlowMap.get(reverseEdge) < reverseEdge
							.getCapacity())) {
				result.add(src);
			}
		}
		return result;
	}
	
	static private Set<Node> DFSReversed(Node sink, DirectedGraph<Node, Edge> g, Map<Edge, Number> edgeFlowMap) {
		Stack<Node> stack = new Stack<Node>();
		stack.push(sink);
		Set<Node> result = new HashSet<Node>();
		Set<Node> discardedNodes = new HashSet<Node>();
		result.add(sink);
		while (!stack.empty()) {
			boolean founded = false;
			Node currentNode = stack.pop();
			discardedNodes.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) && !discardedNodes.contains(src)
						&& ((Integer) edgeFlowMap.get(reverseEdge) < reverseEdge
								.getCapacity()) && !founded) {
					founded=true;
					stack.push(src);
					result.add(src);
				}
				discardedNodes.add(src);
			}
		}
		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) && ((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.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);
//			Util.viewGraph(directedGraph);
			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("f" + 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) {
//				bisection = prepareBisection(bisection.getSmallerNotEmptySubgraph().createInducedSubgraph(), sourcePartition, sinkPartition);
				cluster = BFSReversed(sink, directedGraph, edgeFlowMap);
//				System.out.println("DFSReversed: " + DFSReversed(sink, directedGraph, edgeFlowMap));
//				bisection = new Bisection(new Subgraph(bisection.getSmallerNotEmptySubgraph().createInducedSubgraph(), DFSReversed(sink, directedGraph, edgeFlowMap)));
//				cluster = reversedLookup(sink, directedGraph, edgeFlowMap);
				cluster.remove(sink);
				bisection = new Bisection(new Subgraph(bisection.getSmallerNotEmptySubgraph().createInducedSubgraph(), cluster));
				System.out.println("NEW BISECTION: " + bisection.toString());
			} 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;
	}
	
}