source: src/main/java/weka/clusterers/forMetisMQI/GraphAlgorithms.java @ 6

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;

public class GraphAlgorithms {
        
        boolean debug = true;
        PrintStream debugStream = System.err;
        
        /**
         * Return true if the vertex v is matched
         * 
         * @param v
         *            the index of the vertex
         * @return true if the vertex v is matched, false o.w.
         */
        private boolean isMatched(List<Integer> match, int v) {
                return match.get(v) != v;
        }

        private 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(match,u));
                        if (!isMatched(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(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(u, matchedNode);
                                        match.set(matchedNode, u);
                                        map.set(u, labelCounter);
                                        map.set(matchedNode, labelCounter);
                                        if(debug) debugStream.println("Contracting node " + u + " with " + matchedNode + ". Node id: " + map.get(u));
                                } else
                                        map.set(u, labelCounter);
                                labelCounter++;
                        }
                }
        }
        
        /**
         * Return a new contracted graph.
         */
        private 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(map.get(u));
                        Iterator<Integer> it = g.getNeighbors(u).iterator();
                        Set<Integer> neighbors = new HashSet<Integer>();
                        while(it.hasNext()) {
                                int v = it.next();
                                neighbors.add(map.get(v));
                        }
                        it = g.getNeighbors(match.get(u)).iterator();
                        while(it.hasNext()) {
                                int v = it.next();
                                neighbors.add(map.get(v));
                        }
                        neighbors.remove(map.get(u));
                        it = neighbors.iterator();
                        while(it.hasNext()) {
                                int v = it.next();
                                output.addNode(v);
                                output.addEdgeUndirected(map.get(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(map.get(u) != map.get(v) && output.isEdge(map.get(u), map.get(v)) && u < v) {
                                        output.setWeight(map.get(u), map.get(v), output.getWeight(map.get(u), map.get(v)) + g.getWeight(u, v));
                                }
                        }
                }
                for(int u = 0; u < g.size(); u++) {
                        if(isMatched(match,u)) {
                                int v = match.get(u);
                                if(u < v) {
                                        output.getNode(map.get(u)).vwgt = g.getNode(u).vwgt + g.getNode(v).vwgt;
                                        output.getNode(map.get(u)).cewgt = g.getNode(u).cewgt + g.getNode(v).cewgt +
                                        g.getWeight(u, v);
                                        output.getNode(map.get(u)).adjwgt = g.getNode(u).adjwgt + g.getNode(v).adjwgt - 2 *
                                        g.getWeight(u, v);
                                }
                        } else {
                                output.getNode(map.get(u)).vwgt = g.getNode(u).vwgt;
                                output.getNode(map.get(u)).cewgt = g.getNode(u).cewgt;
                                output.getNode(map.get(u)).adjwgt = g.getNode(u).adjwgt;
                        }
                }
                return output;
        }

        /**
         * Performs the first stage of the METIS algorithm, using RM.
         */
        private CoarserGraphElement coarseOneStep(Graph g) {
                List<Integer> match = new ArrayList<Integer>();
                List<Integer> map = new ArrayList<Integer>();
                RMMatch(g,match,map);
                g = contract(g,match,map);
                return new CoarserGraphElement(g, match, map);
        }
        
        public void coarse(Graph g) {
                int n = 1;
                Graph prev = g;
                CoarserGraphElement e;
                g.printGraph(System.out);
            do {
                e = coarseOneStep(g);
                prev = g;
                g = e.getGraph();
                g.printGraph(System.out);
            } while(prev.size() > g.size() && g.size() > n);
        }

}