source: branches/MetisMQI/src/main/java/weka/clusterers/forMetisMQI/Coarse.java

package weka.clusterers.forMetisMQI;

import java.io.PrintStream;
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 weka.clusterers.forMetisMQI.graph.Edge;
import weka.clusterers.forMetisMQI.graph.Node;
import weka.clusterers.forMetisMQI.graph.UndirectedGraph;
import weka.clusterers.forMetisMQI.util.CoarserGraphElement;

import edu.uci.ics.jung.graph.util.Pair;

public class Coarse {
        
        private static boolean debug = false;
        private static PrintStream debugStream = System.err;
        private static int finerSize = 5;

        /**
         * Return true if the vertex v is matched
         * 
         * @param g graph
         * @param v
         *            the index of the vertex
         * @return true if the vertex v is matched, false o.w.
         */
        private static boolean isMatched(Map<Node,Node> match, Node v) {
                if(match.containsKey(v))
                        return !match.get(v).equals(v);
                else
                        return false;
        }

        private static void RMMatch(UndirectedGraph g, Map<Node,Node> match, Map<Node,Node> map) {
                int labelCounter = 0;
                Iterator<Node> nodeIterator = g.vtxsPermutation().iterator();
                while (nodeIterator.hasNext()) {
                        Node u = nodeIterator.next();
                        if (debug)
                                debugStream.println("Visiting node " + u + " Matched = " + isMatched(match,u));
                        if (!isMatched(match,u)) {
                                boolean foundMatch = false;
                                Node matchedNode = null;
                                Iterator<Node> iterator = g.getNeighborsPermutation(u).iterator();
                                while(iterator.hasNext() && !foundMatch){
                                        Node v = iterator.next();
                                        if (!isMatched(match,v)) {
                                                matchedNode = v;
                                                foundMatch = true;
                                                if (debug)
                                                        debugStream.println("Found a match with node "
                                                                        + matchedNode);
                                        }
                                }
                                if (debug && !foundMatch)
                                        debugStream.println("There aren't unmatched neighbors.");
                                Node newNode = new Node(Integer.toString(labelCounter));
                                if(foundMatch) {
                                        match.put(u, matchedNode);
                                        match.put(matchedNode, u);
                                        map.put(u, newNode);
                                        map.put(matchedNode, newNode);
                                        if(debug) debugStream.println("Contracting node " + u + " with " + matchedNode + ". Node id: " + getMappedNode(map, u));
                                } else {
                                        match.put(u, u);
                                        map.put(u, newNode);
                                        if(debug) debugStream.println("Node " + u + " with " + " new node id: " + getMappedNode(map, u));
                                }
                                labelCounter++;
                        }
                }
        }
        
        private static Node getMatchedNode(Map<Node,Node> match, Node u) {
                return match.get(u);
        }
        
        private static Node getMappedNode(Map<Node,Node> map, Node u) {
                return map.get(u);
        }
        
        /**
         * Return a new contracted graph.
         */
        private static UndirectedGraph contract(UndirectedGraph g, Map<Node,Node> match, Map<Node,Node> map) {
                UndirectedGraph output = new UndirectedGraph();
                Iterator<Node> iterator = g.getVertices().iterator();
                int i = 0;
                while(iterator.hasNext()) {
                        Node u = iterator.next();
                        output.addVertex(getMappedNode(map,u));
                        
                        Set<Node> neighbors = new HashSet<Node>();
                        Iterator<Node> it = g.getNeighbors(u).iterator();
                        while(it.hasNext())
                                neighbors.add(getMappedNode(map, it.next()));
                        it = g.getNeighbors(getMatchedNode(match, u)).iterator();
                        while(it.hasNext())
                                neighbors.add(getMappedNode(map, it.next()));
                        neighbors.remove(getMappedNode(map,u));
                        it = neighbors.iterator();
                        while(it.hasNext()) {
                                Node v = it.next();
                                output.addVertex(v);
                                output.addEdge(new Edge(Integer.toString(i),0,0),getMappedNode(map,u), v);
                                i++;
                        }
                }
                
                //calcolo dei pesi del nuovo grafo: per ogni arco (u,v) && u < v.
                //w(map(u),map(v)) += w(u,v).
                
                Iterator<Edge> edgeIterator = g.getEdges().iterator();
                while(edgeIterator.hasNext()) {
                        Edge oldEdge = edgeIterator.next();
                        Pair<Node> srcDst = g.getEndpoints(oldEdge);
                        Node src = srcDst.getFirst();
                        Node dst = srcDst.getSecond();
                        Node srcMapped = getMappedNode(map, src);
                        Node dstMapped = getMappedNode(map, dst);
                        if(!srcMapped.equals(dstMapped) && output.containsEdge(srcMapped, dstMapped)) {
                                Edge newEdge = output.findEdge(srcMapped, dstMapped);
                                newEdge.setWeight(newEdge.getWeight() + oldEdge.getWeight());
                        }
                }
                iterator = g.getVertices().iterator();
                Set<Node> nodesComplete = new HashSet<Node>();
                while(iterator.hasNext()) {
                        Node u = iterator.next();
                        if(isMatched(match,u)) {
                                Node v = getMatchedNode(match,u);
                                if(!nodesComplete.contains(u)) {
                                        getMappedNode(map,u).setVwgt(u.getVwgt() + v.getVwgt());
                                        getMappedNode(map,u).setCewgt(u.getCewgt() + v.getCewgt() + g.findEdge(u, v).getWeight());
                                        nodesComplete.add(u);
                                        nodesComplete.add(v);
                                }
                        } else {
                                getMappedNode(map,u).setVwgt(u.getVwgt());
                                getMappedNode(map,u).setCewgt(u.getCewgt());
                        }
                }
                return output;
        }

        /**
         * Performs the first stage of the METIS algorithm, using RM.
         */
        private static CoarserGraphElement coarseOneStep(UndirectedGraph g) {
                UndirectedGraph projected = g;
                UndirectedGraph contracted = null;
                Map<Node,Node> match = new HashMap<Node,Node>();
                Map<Node,Node> map = new HashMap<Node,Node>();
                RMMatch(g,match,map);
                contracted = contract(g,match,map);
                return new CoarserGraphElement(contracted, projected, match, map);
        }

        
        /**
         * Performs at least one contraction of the given the graph, and goes on until the graph
         * is under the desidered size (see setFinerSize()).
         * @param g
         * @return the stack of contracted graphs
         */
        public static Stack<CoarserGraphElement> coarse(UndirectedGraph g) {
                Stack<CoarserGraphElement> stack = new Stack<CoarserGraphElement>();
                CoarserGraphElement e = null;
                UndirectedGraph curr = g;
                int i = 0;
                
            do {
                if(debug)
                        debugStream.println("--------CONTRACTION-nr" + i +"------------------------------");
                e = coarseOneStep(curr);
                stack.push(e);
                curr = e.getContracted();
                if(debug) {
                        debugStream.println("-----------EXPANDED----------------------------------");
                        debugStream.println(e.getProjected().toString());
                        debugStream.println("-----------CONTRACTED--------------------------------");
                        debugStream.println(e.getContracted().toString());
                }
                i++;
            } while(e.getProjected().getVertexCount() > e.getContracted().getVertexCount() && e.getContracted().getVertexCount() > finerSize);
            return stack;
        }

        public static void setFinerSize(int i) {
                finerSize = i;
        }
}