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

package weka.clusterers.forMetisMQI.graph;

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

import edu.uci.ics.jung.algorithms.filters.FilterUtils;


public class Subgraph {
        
        private UndirectedGraph g = null;
        
        private Set<Node> nodes = null;
        
        private HashMap<Node,Integer> ID = null;
        private HashMap<Node,Integer> ED = null;
        private HashMap<Integer,List<Node>> bucketGain = null;
        private SortedSet<Integer> gainSet = null;
        private boolean recomputeGain = true;
        
        public Subgraph(UndirectedGraph g){
                this.g = g;
                nodes = new HashSet<Node>();
                ID = new HashMap<Node,Integer>();
                ED = new HashMap<Node,Integer>();
                bucketGain = new HashMap<Integer, List<Node>>();
                gainSet = new TreeSet<Integer>();
        }
        
        public Subgraph(UndirectedGraph g, Set<Node> nodes) {
                this.g = g;
                this.nodes = new HashSet<Node>();
                this.ID = new HashMap<Node,Integer>();
                this.ED = new HashMap<Node,Integer>();
                this.bucketGain = new HashMap<Integer, List<Node>>();
                this.gainSet = new TreeSet<Integer>();
                Iterator<Node> nodesIterator = nodes.iterator();
                while(nodesIterator.hasNext()) {
                        addVertex(nodesIterator.next());
                }
        }
        
        public UndirectedGraph getGraph() {
                return g;
        }
        
        /**
         * Adds to the subgraph the node u iff u belongs to the graph.
         * @param u
         */
        public void addVertex(Node u) {
                if(g.containsVertex(u)) {
                        nodes.add(u);
                        ID.put(u, 0);
                        ED.put(u, 0);
                        recomputeGain = true;
                }
        }
        
        private void computeDegree() {
                Iterator<Node> subgraphIterator = nodes.iterator();
                while(subgraphIterator.hasNext()) {
                        Node u = subgraphIterator.next();
                        Iterator<Node> nborsIterator = g.getNeighbors(u).iterator();
                        int newID = 0;
                        int newED = 0;
                        while(nborsIterator.hasNext()) {
                                Node v = nborsIterator.next();
                                if(contains(v))
                                        newID = newID + g.findEdge(u, v).getWeight();
                                else
                                        newED = newED + g.findEdge(u, v).getWeight();
                        }
                        ID.put(u, newID);
                        ED.put(u, newED);
                }
        }
        
        private void computeGain() {
                bucketGain.clear();
                gainSet.clear();
                ID.clear();
                ED.clear();
                computeDegree();
                Iterator<Node> subgraphIterator = nodes.iterator();
                while(subgraphIterator.hasNext()) {
                        Node u = subgraphIterator.next();
                        int gainU = ED.get(u) - ID.get(u);
                        if(!bucketGain.containsKey(gainU)) {
                                bucketGain.put(gainU, new ArrayList<Node>());
                        }
                        bucketGain.get(gainU).add(u);
                        gainSet.add(gainU);
                }
                recomputeGain = false;
        }
        
        public Node getCandidate() {
                return getCandidate(new HashSet<Node>());
        }
        
        /**
         * 
         * @param marked 
         * @return the candidate node for swap or <code>null</code> if there aren't available nodes.
         */
        public Node getCandidate(Set<Node> marked) {
                if(recomputeGain)
                        computeGain();
                Node candidate = null;
                Iterator<Integer> iterator = ((TreeSet<Integer>)gainSet).descendingIterator();
                while(iterator.hasNext() && (candidate == null)) {
                        int gain = iterator.next();
                        Iterator<Node> nodes = bucketGain.get(gain).iterator();
                        while(nodes.hasNext() && (candidate == null)) {
                                Node u = nodes.next();
                                if(!marked.contains(u))
                                        candidate = u;
                        }
                }
                return candidate;
        }
        
        public int gain(Node u){
                if(recomputeGain)
                        computeGain();
                return ED.get(u) - ID.get(u);
        }
        
        public void removeVertex(Node u) {
                if(recomputeGain)
                        computeGain();
                int gainU = gain(u);
                nodes.remove(u);
                ID.remove(u);
                ED.remove(u);
                List<Node> l = bucketGain.get(gainU);
                l.remove(l.indexOf(u));
                if(l.size() == 0) {
                        bucketGain.remove(gainU);
                        gainSet.remove(gainU);
                }
                recomputeGain = true;
        }
        
        public int getVertexCount() {
                return nodes.size();
        }
        
        public Edge findEdge(Node v1, Node v2) {
                Edge e = null;
                if(contains(v1) && contains(v2))
                        e = g.findEdge(v1, v2);
                return e;
        }
        
        public int getWeight(Node u, Node v) {
                int ret = -1;
                if(containsEdge(u,v))
                        ret = g.findEdge(u, v).getWeight();
                return ret;
        }
        
        public Iterator<Node> iterator() {
                return nodes.iterator();
        }
        
        public boolean containsEdge(Node u, Node v) {
                return contains(u) && contains(v) && g.containsEdge(u, v);
        }
        
        public boolean contains(Node u) {
                return nodes.contains(u);
        }
        
        public List<Node> getNeighbors(Node u) {
                List<Node> neighbors = new ArrayList<Node>();
                Iterator<Node> iterator = g.getNeighbors(u).iterator(); 
                while(iterator.hasNext()) {
                        Node v = iterator.next();
                        if(contains(v) && containsEdge(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() {
                if(getVertexCount() == 0)
                        return "[]";
                StringBuffer out =new StringBuffer("[");
                Iterator<Node> it = nodes.iterator();
                while(it.hasNext()) {
                        Node u = it.next();
                        out.append(u.toString() + ",");
                }
                out.setLength(out.length() - 1);
                out.append("]");
                return out.toString();
        }
        
        public List<Node> getBoundary() {
                if(recomputeGain)
                        computeGain();
                Iterator<Entry<Node,Integer>> EDIterator = ED.entrySet().iterator();
                List<Node> boundary = new ArrayList<Node>();
                while(EDIterator.hasNext()) {
                        Entry<Node,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 = new HashSet<Node>();
                Iterator<Node> graphIterator =clone.g.getVertices().iterator();
                while(graphIterator.hasNext()) {
                        Node u = graphIterator.next();
                        if(contains(u))
                                clone.nodes.add(u);
                }
                
                clone.bucketGain = new HashMap<Integer, List<Node>>();
                clone.gainSet = new TreeSet<Integer>();
                clone.ID = new HashMap<Node, Integer>();
                clone.ED = new HashMap<Node, Integer>();
                
                clone.computeGain();
                
                return clone;
        }
        
        public UndirectedGraph createInducedSubgraph() {
                return FilterUtils.createInducedSubgraph(nodes,g);
        }
        
        public int totalDegree() {
                int result = 0;
                Iterator<Node> nodeIterator = iterator();
                while(nodeIterator.hasNext()) {
                        int degree = g.degree(nodeIterator.next());
                        result += degree;
                }
                return result;
        }
}