source: src/main/java/weka/clusterers/forMetisMQI/MQI.java @ 15

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;
        }
        
}