source: src/main/java/weka/clusterers/forMetisMQI/Graph.java @ 7

package weka.clusterers.forMetisMQI;

import java.io.PrintStream;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map.Entry;

import weka.core.Attribute;
import weka.core.Instance;
import weka.core.Instances;

public class Graph {
        
        protected static class NodeInfo {
                /** The weight of the node */
                protected int vwgt;
                /** The size of the adjacency list of the node */
                protected int nedges;
                /**
                 * The index into the adjacency list that is the beginning of the
                 * adjacency list of v
                 */
                protected int iedges;
                /** The weight of the edges that have been contracted to create the node */
                protected int cewgt;
                /** The sum of the weight of the edges adjacent to v */
                protected int adjwgt;

                public NodeInfo() {
                        this.vwgt = 1;
                        this.cewgt = 0;
                        this.iedges = 0;
                        this.nedges = 0;
                        this.adjwgt = 0;

                }

                @Override
                public String toString() {
                        return "Vwgt: " + vwgt + " Cewgt: " + cewgt + " Iedges: " + iedges
                                        + " Nedges: " + nedges + " Adjwgt: " + adjwgt;
                }
                
                @Override
                public NodeInfo clone() {
                        NodeInfo ni = new NodeInfo();
                        ni.adjwgt = adjwgt;
                        ni.cewgt = cewgt;
                        ni.iedges = iedges;
                        ni.nedges = nedges;
                        ni.vwgt = vwgt;
                        return ni;
                }
        }

        /**
         * Additional node info for all vertices..
         */
        private List<NodeInfo> vtxs;
        /**
         * Adjacency vector.
         */
        private List<Integer> adjncy;
        /**
         * Weights vector
         */
        private List<Integer> weights;
        
        private HashMap<Integer,Integer> label;
        private HashMap<Integer,Integer> index;

        /**
         * Build a new graph given a set of instances.
         * 
         * @param data
         */
        public Graph(Instances data) {
                vtxs = new ArrayList<NodeInfo>();
                adjncy = new ArrayList<Integer>();
                weights = new ArrayList<Integer>();
                label = new HashMap<Integer,Integer>();
                index = new HashMap<Integer,Integer>();
                Iterator<Instance> dataIterator = data.iterator();
                Attribute from = data.attribute("from");
                Attribute to = data.attribute("to");
                if (from == null || to == null)
                        throw new RuntimeException(
                                        "Unsupported data: check the list of attributes (from and to are needed).");
                while (dataIterator.hasNext()) {
                        Instance edge = dataIterator.next();
                        int node1 = (int) Math.round(edge.value(from));
                        int node2 = (int) Math.round(edge.value(to));
                        addNode(node1); addNode(node2);
                        addEdgeUndirected(node1, node2, 1);
                }
        }

        public Graph() {
                vtxs = new ArrayList<NodeInfo>();
                adjncy = new ArrayList<Integer>();
                weights = new ArrayList<Integer>();
                label = new HashMap<Integer,Integer>();
                index = new HashMap<Integer,Integer>();
        }
        
        /**
         * Returns an iterator over the nodes of the graph.
         * @return
         */
        public Iterator<Integer> iterator() {
                return label.keySet().iterator();
        }
        
        /**
         * Returns the label associated with a given index.
         * @param index
         * @return
         */
        public int getLabel(int index) {
                return this.index.get(index);
        }
        
        /**
         * Returns the index associated with a given label.
         * @param index
         * @return
         */
        public int getIndex(int label) {
                return this.label.get(label);
        }
        
        private void updateAssociation(int index, int label) {
                this.index.put(index,label);
                this.label.put(label,index);
        }
        
        /**
         * Returns the weight of the edge (u,v).
         * @param u
         * @param v
         * @return
         */
        public int getWeight(int u, int v) {
                int i = getIndex(u);
                int istart = vtxs.get(i).iedges;
                int iend = vtxs.get(i).iedges + vtxs.get(i).nedges;
                int weight = -1; boolean found = false;
                for(int k = istart; k < iend && !found; k++) {
                        if(adjncy.get(k) == v) {
                                weight = weights.get(k);
                                found = true;
                    }
                }
                return weight;
        }
        
        public void setWeight(int u, int v, int weight) {
                int i = getIndex(u);
                int j = getIndex(v);
                int istart = vtxs.get(i).iedges;
                int iend = istart + vtxs.get(i).nedges;
                for(int k = istart; k < iend; k++){
                        if(adjncy.get(k) == v) {
                                weights.set(k, weight);
                        }
                }
                int jstart = vtxs.get(j).iedges;
                int jend = jstart + vtxs.get(j).nedges;
                for(int k = jstart; k < jend; k++){
                        if(adjncy.get(k) == u)
                                weights.set(k, weight);
                }
        }
        
        public NodeInfo getNode(int u) {
                int i = getIndex(u);
                return vtxs.get(i);
        }
        
        public int nedge() {
                return adjncy.size();
        }
        
        public boolean isNode(int u) {
                return label.containsKey(u);
        }
        
        public void addNode(int u) {
                if(!isNode(u)) {
                        int index = size();
                        updateAssociation(index, u);
                        NodeInfo node = new NodeInfo();
                        node.iedges = nedge();
                        node.nedges = 0;
                        node.vwgt = 1;
                        node.adjwgt = 0;
                        node.cewgt = 0;
                        vtxs.add(index, node);
                }
        }
        
        public int size() {
                return vtxs.size();
        }
        
        public List<Integer> getNeighbors(int u) {
                int i = getIndex(u);
                List<Integer> neighbors = new ArrayList<Integer>();
                int istart = vtxs.get(i).iedges;
                int iend = vtxs.get(i).iedges + vtxs.get(i).nedges;
                for(int k = istart; k < iend; k++) {
                        neighbors.add(adjncy.get(k));
                }
                return neighbors;
        }
        
        /**
         * Return true if u is neighbor of v.
         * @param u
         * @param v
         * @return
         */
        public boolean isNeighbor(int u, int v){
                return getNeighbors(u).contains(v);
        }
        
        public void addEdgeUndirected(int i, int j, int w) {
                addEdgeDirectedl(i, j, w);
                addEdgeDirectedl(j, i, w);
        }
        
        /**
         * Add an edge from i to j of weight w if previously it doesn't exists, otherwise
         * simply update the weight of the edge.
         * @param i
         * @param j
         * @param w
         */
        public void addEdgeDirectedl(int u, int v, int w) {
                int i = getIndex(u);
                if(!isNeighbor(u,v)) {
                        int istart = getNode(u).iedges;
                        adjncy.add(istart,v);
                        for(int k = i + 1; k < size(); k++) {
                                vtxs.get(k).iedges++;
                        }
                        vtxs.get(i).nedges++;
                        vtxs.get(i).adjwgt += w;
                        weights.add(istart, w);
                } else
                        setWeight(u, v, w);
        }
        
        public boolean isEdge(int u, int v) {
                int i = getIndex(u);
                int istart = vtxs.get(i).iedges;
                int iend = vtxs.get(i).iedges + vtxs.get(i).nedges;
                boolean found = false;
                for(int k = istart; k < iend && !found; k++) {
                        found = (adjncy.get(k) == v);
                }
                return found;
        }

        /**
         * Print the graph structure.
         */
        public void printGraph(PrintStream io) {
                for(int i = 0; i < vtxs.size(); i++) {
                        int u = getLabel(i);
                        io.print("Node: " + u + " Neighbors: ");
                        Iterator<Integer> neighbors = getNeighbors(u).iterator();
                        while(neighbors.hasNext()) {
                                int v = neighbors.next();
                                io.print(v + " [w: " + getWeight(u, v) + "] ");
                        }
                        io.println(getNode(u).toString());
                }
        }
        
        /**
         * Return a list containing a random permutation of the vertices.
         * 
         * @return a random permutation of vertices
         */
        public List<Integer> vtxsPermutation() {
                Random r = Random.instance(); 
                List<Integer> perm = new ArrayList<Integer>();
                for (int i = 0; i < vtxs.size(); i++) {
                        perm.add(getLabel(i));
                }
                for (int i = 0; i < perm.size(); i++) {
                        int k = r.nextInt(perm.size());
                        int swap = perm.get(k);
                        perm.set(k, perm.get(i));
                        perm.set(i, swap);
                }
                return perm;
        }
        
        /**
         * Randomize the adjacency list.
         */
        public void adjncyPermutation() {
                Random r = Random.instance();
                for (int i = 0; i < vtxs.size(); i++) {
                        NodeInfo n = vtxs.get(i);
                        for (int j = n.iedges; j < n.nedges + n.iedges; j++) {
                                int k = r.nextInt(n.nedges) + n.iedges;
                                int swap = adjncy.get(k);
                                adjncy.set(k, adjncy.get(j));
                                adjncy.set(j, swap);
                                swap = weights.get(k);
                                weights.set(k, weights.get(j));
                                weights.set(j, swap);
                        }
                }
        }
        
        
        @Override
        public Graph clone() {
                Graph g = new Graph();
                g.adjncy = new ArrayList<Integer>();
                for(int i = 0; i < adjncy.size(); i++) {
                        g.adjncy.add(adjncy.get(i));
                }
                
                g.weights = new ArrayList<Integer>();
                for(int i = 0; i < weights.size(); i++) {
                        g.weights.add(weights.get(i));
                }
                
                g.vtxs = new ArrayList<NodeInfo>();
                for(int i = 0; i < vtxs.size(); i++) {
                        g.vtxs.add(vtxs.get(i).clone());
                }
                
                g.index = new HashMap<Integer, Integer>();
                Iterator<Entry<Integer,Integer>> i = index.entrySet().iterator();
                while(i.hasNext()) {
                        Entry<Integer,Integer> entry = i.next();
                        g.index.put(entry.getKey(), entry.getValue());
                }
                
                g.label = new HashMap<Integer, Integer>();
                i = label.entrySet().iterator();
                while(i.hasNext()) {
                        Entry<Integer,Integer> entry = i.next();
                        g.label.put(entry.getKey(), entry.getValue());
                }
                
                
                return g;
        }
}