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

package weka.clusterers.forMetisMQI.graph;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

import weka.clusterers.forMetisMQI.util.Random;



public class Bisection {
        
        private Subgraph a = null;
        
        private Subgraph b = null;
        
        private Set<Node> marked = null;
        
        private UndirectedGraph g = null;

        private Bisection() {
        }
        
        /**
         * Initialize the bisection with a given subgraph.
         * @param s
         */
        public Bisection(Subgraph s) {
                g  = s.getGraph();
                a = s;
                b = new Subgraph(g);
                Iterator<Node> graphIterator =  g.getVertices().iterator();
                while(graphIterator.hasNext()) {
                        Node u = graphIterator.next();
                        if(!s.contains(u))
                                b.addVertex(u);
                }
                marked = new HashSet<Node>();
        }
        
        /**
         * Creates a bisection choosing randomly the nodes for each subgraph.
         * @param g
         */
        public Bisection(UndirectedGraph g){
                double limitingProbabilities = 0.1;
                this.g = g;
                a = new Subgraph(g);
                b = new Subgraph(g);
                Iterator<Node> graph = g.vtxsPermutation().iterator();
                while(graph.hasNext()) {
                        Node u = graph.next();
                        if(Random.instance().nextDouble() < limitingProbabilities)
                                a.addVertex(u);
                        else
                                b.addVertex(u);
                }
                marked = new HashSet<Node>();
        }
        
        public UndirectedGraph getGraph() {
                return g;
        }
        
        /**
         * Returns the node marked as candidate for swapping or <code>null</code> if there aren't node available
         * for swapping.
         * @return
         */
        public Node getCandidate() {
                Node u;
                if(a.getVertexCount() > b.getVertexCount()) {
                        u = a.getCandidate(marked);
                        if(u == null)
                                u = b.getCandidate(marked);
                } else {
                        u = b.getCandidate(marked);
                        if(u == null)
                                u = a.getCandidate(marked);
                }
                if(u != null) {
                        marked.add(u);
                }
                return u;
        }
        
        public void swap(Node u) {
                Subgraph from = fromSubgraph(u);
                Subgraph to = toSubgraph(u);
                from.removeVertex(u);
                to.addVertex(u);
        }
        
        private Subgraph fromSubgraph(Node u) {
                Subgraph ret = null;
                if(a.contains(u))
                        ret = a;
                if(b.contains(u))
                        ret = b;
                return ret;
        }
        
        private Subgraph toSubgraph(Node 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 acc;
        }
        
        public Subgraph getSubgraph() {
                return a;
        }
        
        public Subgraph getComplement() {
                return b;
        }
        
        public Bisection clone(){
                Bisection clone = new Bisection();
                clone.a = (Subgraph) a.clone();
                clone.b = (Subgraph) b.clone();
                clone.g = g.clone();
                clone.marked = new HashSet<Node>();
                return clone;
        }
        
        @Override
        public String toString(){
                String out = a.toString();
                out = out + "\n";
                out = out + b.toString();
                return out;
        }
        
        public Subgraph getLargerSubgraph() {
                if(a.getVertexCount() < b.getVertexCount())
                        return b;
                else
                        return a;
        }
        
        /**
         * Returns the smaller subgraph of this bisection, null otherwise.
         * @return
         */
        public Subgraph getSmallerSubgraph() {
                if(a.getVertexCount() < b.getVertexCount())
                        return a;
                else
                        return b;
        }
}