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

package weka.clusterers.forMetisMQI;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.SortedSet;
import java.util.TreeSet;
import java.util.Map.Entry;

public class Subgraph {
        
        private Graph g = null;
        private BitSet nodes = null;
        private List<Integer> listOfNodes = null;
        private HashMap<Integer,Integer> ID = null;
        private HashMap<Integer,Integer> ED = null;
        private HashMap<Integer,List<Integer>> bucketGain = null;
        private SortedSet<Integer> gainSet = null;
        private boolean recomputeGain = true;
        
        public Subgraph(Graph g){
                this.g = g;
                nodes = new BitSet(g.size());
                listOfNodes = new ArrayList<Integer>();
                ID = new HashMap<Integer,Integer>();
                ED = new HashMap<Integer,Integer>();
                bucketGain = new HashMap<Integer, List<Integer>>();
                gainSet = new TreeSet<Integer>();
        }
        
        public Graph getGraph() {
                return g;
        }
        
        public void addNode(int u) {
                nodes.set(g.getIndex(u));
                listOfNodes.add(u);
                ID.put(u, 0);
                ED.put(u, 0);
                recomputeGain = true;
        }
        
        private void computeDegree() {
                for(int i = 0; i < size(); i++) {
                        int u = listOfNodes.get(i);
                        Iterator<Integer> it = g.getNeighbors(u).iterator();
                        int newID = 0;
                        int newED = 0;
                        while(it.hasNext()) {
                                int v = it.next();
                                if(contains(v))
                                        newID = newID + g.getWeight(u, v);
                                else
                                        newED = newED + g.getWeight(u, v);
                                ID.put(u, newID);
                                ED.put(u, newED);
                        }
                }
        }
        
        private void computeGain() {
                bucketGain.clear();
                gainSet.clear();
                ID.clear();
                ED.clear();
                computeDegree();
                for(int i = 0; i < size(); i++) {
                        int u = listOfNodes.get(i);
                        int gainU = ED.get(u) - ID.get(u);
                        if(!bucketGain.containsKey(gainU)) {
                                bucketGain.put(gainU, new ArrayList<Integer>());
                        }
                        bucketGain.get(gainU).add(u);
                        gainSet.add(gainU);
                }
                recomputeGain = false;
        }
        
        public int getCandidate() {
                return getCandidate(new ArrayList<Integer>());
        }
        
        /**
         * 
         * @param marked 
         * @return the candidate node for swap or -1 if there aren't available nodes.
         */
        public int getCandidate(List<Integer> marked) {
                if(recomputeGain)
                        computeGain();
                int candidate = -1;
                Iterator<Integer> iterator = ((TreeSet<Integer>)gainSet).descendingIterator();
                while(iterator.hasNext() && (candidate == -1)) {
                        int gain = iterator.next();
                        Iterator<Integer> nodes = bucketGain.get(gain).iterator();
                        while(nodes.hasNext() && (candidate == -1)) {
                                int u = nodes.next();
                                if(!marked.contains(u))
                                        candidate = u;
                        }
                }
                return candidate;
        }
        
        public int gain(int u){
                if(recomputeGain)
                        computeGain();
                return ED.get(u) - ID.get(u);
        }
        
        public void remove(int u) {
                if(recomputeGain)
                        computeGain();
                int gainU = gain(u);
                nodes.set(g.getIndex(u), false);
                listOfNodes.remove(listOfNodes.indexOf(u));
                ID.remove(u);
                ED.remove(u);
                List<Integer> l = bucketGain.get(gainU);
                l.remove(l.indexOf(u));
                if(l.size() == 0) {
                        bucketGain.remove(gainU);
                        gainSet.remove(gainU);
                }
                recomputeGain = true;
        }
        
        public int size() {
                return listOfNodes.size();
        }
        
        public int getWeight(int u, int v) {
                int ret = -1;
                if(isEdge(u,v))
                        ret = g.getWeight(u, v);
                return ret;
        }
        
        public Iterator<Integer> iterator() {
                return listOfNodes.iterator();
        }
        
        public boolean isEdge(int u, int v) {
                return nodes.get(g.getIndex(u)) && nodes.get(g.getIndex(v)) && g.isEdge(u, v);
        }
        
        public boolean contains(int u) {
                return nodes.get(g.getIndex(u));
        }
        
        public List<Integer> getNeighbours(int u) {
                List<Integer> neighbors = new ArrayList<Integer>();
                Iterator<Integer> iterator = g.getNeighbors(u).iterator(); 
                while(iterator.hasNext()) {
                        int v = iterator.next();
                        if(contains(v) && isEdge(u, v))
                                neighbors.add(v);
                }
                return neighbors;
        }
        
        public int getExternalDegree() {
                if(recomputeGain)
                        computeGain();
                int acc = 0;
                Iterator<Integer> it = ED.values().iterator();
                while(it.hasNext())
                        acc = acc + it.next();
                return acc;
        }
        
        @Override
        public String toString() {
                String out = "[";
                Iterator<Integer> it = listOfNodes.iterator();
                while(it.hasNext()) {
                        int u = it.next();
                        out = out + u + ",";
                }
                out = out + "]";
                return out;
        }
        
        public List<Integer> getBoundary() {
                if(recomputeGain)
                        computeGain();
                Iterator<Entry<Integer,Integer>> EDIterator = ED.entrySet().iterator();
                List<Integer> boundary = new ArrayList<Integer>();
                while(EDIterator.hasNext()) {
                        Entry<Integer,Integer> entry = EDIterator.next();
                        if(entry.getValue() > 0)
                                boundary.add(entry.getKey());
                }
                return boundary;
        }
        
        private Subgraph() {
                
        }
        
        @Override
        public Subgraph clone() {
                Subgraph clone = new Subgraph();
                clone.g = g.clone();
                
                clone.nodes = (BitSet)nodes.clone();
                
                clone.listOfNodes = new ArrayList<Integer>();
                for(int i = 0; i < listOfNodes.size(); i++) {
                        clone.listOfNodes.add(listOfNodes.get(i));
                }
                
                clone.ID = new HashMap<Integer, Integer>();
                Iterator<Entry<Integer,Integer>> i = ID.entrySet().iterator();
                while(i.hasNext()) {
                        Entry<Integer,Integer> entry = i.next();
                        clone.ID.put(entry.getKey(), entry.getValue());
                }
                
                clone.ED = new HashMap<Integer, Integer>();
                i = ED.entrySet().iterator();
                while(i.hasNext()) {
                        Entry<Integer,Integer> entry = i.next();
                        clone.ED.put(entry.getKey(), entry.getValue());
                }
                
                clone.bucketGain = new HashMap<Integer, List<Integer>>();
                Iterator<Entry<Integer,List<Integer>>>it = bucketGain.entrySet().iterator();
                while(it.hasNext()) {
                        Entry<Integer,List<Integer>> entry = it.next();
                        List<Integer> bucketClone = new ArrayList<Integer>();
                        List<Integer> bucket = entry.getValue();
                        for(int j = 0; j < bucket.size(); j++) {
                                bucketClone.add(bucket.get(j));
                        }
                        clone.bucketGain.put(entry.getKey(), bucketClone);
                }
                
                clone.gainSet = new TreeSet<Integer>();
                Iterator<Integer> gainIt = gainSet.iterator();
                while(gainIt.hasNext()) {
                        gainSet.add(gainIt.next());
                }
                
                clone.recomputeGain = recomputeGain;
                
                return clone;
        }
}