source: src/main/java/weka/clusterers/forMetisMQI/Coarse.java @ 7

package weka.clusterers.forMetisMQI;

import java.io.PrintStream;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
import java.util.Stack;

public class Coarse {
        
        private static boolean debug = true;
        private static PrintStream debugStream = System.err;
        private static int nodesContracted = 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(Graph g, List<Integer> match, int v) {
                return match.get(g.getIndex(v)) != g.getIndex(v);
        }

        private static void RMMatch(Graph g, List<Integer> match, List<Integer> map) {
                int labelCounter = 0;
                for (int i = 0; i < g.size(); i++) {
                        match.add(i);
                        map.add(i);
                }
                g.adjncyPermutation();
                Iterator<Integer> nodeIterator = g.vtxsPermutation().iterator();
                while (nodeIterator.hasNext()) {
                        int u = nodeIterator.next();
                        if (debug)
                                debugStream.println("Visiting node " + u + " Matched = " + isMatched(g,match,u));
                        if (!isMatched(g,match,u)) {
                                boolean foundMatch = false;
                                int matchedNode = -1;
                                Iterator<Integer> iterator = g.getNeighbors(u).iterator();
                                while(iterator.hasNext() && !foundMatch){
                                        int v = iterator.next();
                                        if (!isMatched(g,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.");
                                if(foundMatch) {
                                        match.set(g.getIndex(u), g.getIndex(matchedNode));
                                        match.set(g.getIndex(matchedNode), g.getIndex(u));
                                        map.set(g.getIndex(u), labelCounter);
                                        map.set(g.getIndex(matchedNode), labelCounter);
                                        if(debug) debugStream.println("Contracting node " + u + " with " + matchedNode + ". Node id: " + getMappedNode(g, map, u));
                                } else
                                        map.set(g.getIndex(u), labelCounter);
                                labelCounter++;
                        }
                }
        }
        
        private static int getMatchedNode(Graph g, List<Integer> match, int u) {
                return g.getLabel(match.get(g.getIndex(u)));
        }
        
        private static int getMappedNode(Graph g, List<Integer> map, int u) {
                return map.get(g.getIndex(u));
        }
        
        /**
         * Return a new contracted graph.
         */
        private static Graph contract(Graph g, List<Integer> match, List<Integer> map) {
                Graph output = new Graph();
                Iterator<Integer> iterator = g.iterator();
                while(iterator.hasNext()) {
                        int u = iterator.next();
                        output.addNode(getMappedNode(g,map,u));
                        Iterator<Integer> it = g.getNeighbors(u).iterator();
                        Set<Integer> neighbors = new HashSet<Integer>();
                        while(it.hasNext()) {
                                int v = it.next();
                                neighbors.add(getMappedNode(g,map,v));
                        }
                        it = g.getNeighbors(getMatchedNode(g,match,u)).iterator();
                        while(it.hasNext()) {
                                int v = it.next();
                                neighbors.add(getMappedNode(g,map,v));
                        }
                        neighbors.remove(getMappedNode(g,map,u));
                        it = neighbors.iterator();
                        while(it.hasNext()) {
                                int v = it.next();
                                output.addNode(v);
                                output.addEdgeUndirected(getMappedNode(g,map,u), v, 0);
                        }
                }       
                //calcolo dei pesi del nuovo grafo: per ogni arco (u,v) && u < v.
                //w(map(u),map(v)) += w(u,v). 
                for(int u=0; u < g.size(); u++) {
                        Iterator<Integer> it = g.getNeighbors(u).iterator();
                        while(it.hasNext()) {
                                int v = it.next();
                                if(getMappedNode(g,map,u) != getMappedNode(g,map,v) && output.isEdge(getMappedNode(g,map,u), getMappedNode(g,map,v)) && u < v) {
                                        output.setWeight(getMappedNode(g,map,u), getMappedNode(g,map,v), output.getWeight(getMappedNode(g,map,u), getMappedNode(g,map,v)) + g.getWeight(u, v));
                                }
                        }
                }
                for(int u = 0; u < g.size(); u++) {
                        if(isMatched(g,match,u)) {
                                int v = getMatchedNode(g,match,u);
                                if(u < v) {
                                        output.getNode(getMappedNode(g,map,u)).vwgt = g.getNode(u).vwgt + g.getNode(v).vwgt;
                                        output.getNode(getMappedNode(g,map,u)).cewgt = g.getNode(u).cewgt + g.getNode(v).cewgt +
                                        g.getWeight(u, v);
                                        output.getNode(getMappedNode(g,map,u)).adjwgt = g.getNode(u).adjwgt + g.getNode(v).adjwgt - 2 *
                                        g.getWeight(u, v);
                                }
                        } else {
                                output.getNode(getMappedNode(g,map,u)).vwgt = g.getNode(u).vwgt;
                                output.getNode(getMappedNode(g,map,u)).cewgt = g.getNode(u).cewgt;
                                output.getNode(getMappedNode(g,map,u)).adjwgt = g.getNode(u).adjwgt;
                        }
                }
                return output;
        }

        /**
         * Performs the first stage of the METIS algorithm, using RM.
         */
        public static CoarserGraphElement coarseOneStep(Graph g) {
                Graph projected = g;
                Graph contracted = null;
                List<Integer> match = new ArrayList<Integer>();
                List<Integer> map = new ArrayList<Integer>();
                RMMatch(g,match,map);
                contracted = contract(g,match,map);
                return new CoarserGraphElement(contracted, projected, match, map);
        }
        
        public static Stack<CoarserGraphElement> coarse(Graph g) {
                Stack<CoarserGraphElement> stack = new Stack<CoarserGraphElement>();
                CoarserGraphElement e;
                Graph curr = g;
            do {
                if(debug)
                        debugStream.println("-----------------------------------------------------");
                e = coarseOneStep(curr);
                stack.push(e);
                curr = e.getContracted();
                if(debug)
                        debugStream.println("-----------------------------------------------------");
            } while(e.getProjected().size() > e.getContracted().size() && e.getContracted().size() > nodesContracted);
            return stack;
        }
}