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

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 edu.uci.ics.jung.algorithms.flows.EdmondsKarpMaxFlow;
import edu.uci.ics.jung.graph.DirectedGraph;
import edu.uci.ics.jung.graph.DirectedSparseGraph;
import weka.clusterers.forMetisMQI.util.Util;

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 bisection, Node source, Node sink, boolean forConductance) {
                Subgraph B = bisection.getLargerSubgraph();
                Subgraph A = bisection.getSmallerSubgraph();
                int a = 0;
                if (!forConductance)
                        a = A.getVertexCount();
                else {
//                      a = Math.min(B.totalDegree(),A.totalDegree());
                        a = A.totalDegree();
                }
                int c = bisection.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();
                        if(forConductance)
                                g.addEdge(new Edge(Integer.toString(id), 1, c * bisection.getGraph().degree(u)), u, sink);
                        else
                                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, boolean forConductance) {
//              System.out.println("INITIAL BISECTION: " + partition.toString());
                boolean finished = false;
                Bisection bisection = partition;
                Set<Node> cluster = new HashSet<Node>(partition.getSmallerSubgraph()
                                .createInducedSubgraph().getVertices());
//              System.out.println("IMPROVING SUBGRAPH: " + cluster);
                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, true);
                        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);

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

}