source: src/main/java/weka/clusterers/forMetisMQI/KLPartition.java @ 8

package weka.clusterers.forMetisMQI;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;


public class KLPartition {
        
        private Subgraph a = null;
        
        private Subgraph b = null;
        
        private List<Integer> marked = null;

        private KLPartition() {
        }
        
        public KLPartition(Subgraph s) {
                Graph g  = s.getGraph();
                a = s;
                b = new Subgraph(g);
                Iterator<Integer> graphIterator =  g.iterator();
                while(graphIterator.hasNext()) {
                        int u = graphIterator.next();
                        if(!s.contains(u))
                                b.addNode(u);
                }
                marked = new ArrayList<Integer>();
        }
        
        public KLPartition(Graph g){
                a = new Subgraph(g);
                b = new Subgraph(g);
                Iterator<Integer> graph = g.vtxsPermutation().iterator();
                int i = 0;
                while(graph.hasNext()) {
                        int u = graph.next();
                        if((i%2)==0)
                                a.addNode(u);
                        else
                                b.addNode(u);
                        i++;
                }
                marked = new ArrayList<Integer>();
        }
        
        /**
         * Returns the node marked as candidate for swapping or -1 if there aren't node available
         * for swapping.
         * @return
         */
        public int getCandidate() {
                int u;
                if(a.size() > b.size()) {
                        u = a.getCandidate(marked);
                        if(u == -1)
                                u = b.getCandidate(marked);
                } else {
                        u = b.getCandidate(marked);
                        if(u == -1)
                                u = a.getCandidate(marked);
                }
                if(u != -1) {
                        marked.add(u);
                }
                return u;
        }
        
        public void swap(int u) {
                Subgraph from = fromSubgraph(u);
                Subgraph to = toSubgraph(u);
                from.remove(u);
                to.addNode(u);
        }
        
        private Subgraph fromSubgraph(int u) {
                Subgraph ret = null;
                if(a.contains(u))
                        ret = a;
                if(b.contains(u))
                        ret = b;
                return ret;
        }
        
        private Subgraph toSubgraph(int u) {
                Subgraph ret = null;
                if(!a.contains(u))
                        ret = a;
                if(!b.contains(u))
                        ret = b;
                return ret;
        }

        public int edgeCut() {
                int acc = a.getExternalDegree() + b.getExternalDegree();
                return (int)Math.round(0.5 * acc);
        }
        
        public Subgraph getSubgraph() {
                return a;
        }
        
        public Subgraph getComplement() {
                return b;
        }
        
        @Override
        public KLPartition clone(){
                KLPartition clone = new KLPartition();
                clone.a = (Subgraph) a.clone();
                clone.b = (Subgraph) b.clone();
                clone.marked = new ArrayList<Integer>();
                for(int i = 0; i < marked.size(); i++) {
                        clone.marked.add(marked.get(i));
                }
                return clone;
        }
        
        @Override
        public String toString(){
                String out = a.toString();
                out = out + "\n";
                out = out + b.toString();
                return out;
        }
}