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

package weka.clusterers.forMetisMQI.graph;

import java.io.PrintStream;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.TreeMap;

import weka.clusterers.forMetisMQI.util.Random;
import weka.core.Attribute;
import weka.core.Instance;
import weka.core.Instances;
import edu.uci.ics.jung.graph.UndirectedSparseGraph;
import edu.uci.ics.jung.graph.util.Pair;

public class UndirectedGraph extends UndirectedSparseGraph<Node, Edge> {
        
        private static final long serialVersionUID = 1L;

        public List<Node> vtxsPermutation() {
                Random r = Random.instance(); 
                List<Node> perm = new ArrayList<Node>();
                Iterator<Node> vtxsIterator = getVertices().iterator();
                while(vtxsIterator.hasNext()) {
                        Node node = vtxsIterator.next();
                        perm.add(node);
                }
                for (int i = 0; i < perm.size(); i++) {
                        int k = r.nextInt(perm.size());
                        Node swap = perm.get(k);
                        perm.set(k, perm.get(i));
                        perm.set(i, swap);
                }
                return perm;
        }
        
        public boolean containsEdge(Node v1, Node v2) {
                return (findEdge(v1, v2) != null);
        }
        
        public Node findVertex(Node v1) {
                Iterator<Node> graphIterator = getVertices().iterator();
                while(graphIterator.hasNext()) {
                        Node v2 = graphIterator.next();
                        if(v1.equals(v2)) return v2;
                }
                return null;
        }
        
        public Collection<Node> getNeighborsPermutation(Node n) {
                Random r = Random.instance();
                ArrayList<Node> perm = new ArrayList<Node>();
                Iterator<Node> vtxsIterator = getNeighbors(n).iterator();
                while(vtxsIterator.hasNext()) {
                        Node node = vtxsIterator.next();
                        perm.add(node);
                }
                for (int i = 0; i < perm.size(); i++) {
                        int k = r.nextInt(perm.size());
                        Node swap = perm.get(k);
                        perm.set(k, perm.get(i));
                        perm.set(i, swap);
                }
                return perm;
        }
        
        public void loadFromInstance(Instances data) {
                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).");
                int edgeId = 0;
                while (dataIterator.hasNext()) {
                        Instance edge = dataIterator.next();
                        Node node1 = new Node(edge.stringValue(from));
                        Node node2 = new Node(edge.stringValue(to));
                        addVertex(node1);
                        addVertex(node2);
                        addEdge(new Edge(Integer.toString(edgeId),1,1),node1,node2);
                        edgeId++;
                }
        }
        
        @Override
        public UndirectedGraph clone() {
                UndirectedGraph g = new UndirectedGraph();
                Iterator<Node> nodesIterator = getVertices().iterator();
                while(nodesIterator.hasNext()) {
                        g.addVertex(nodesIterator.next().clone());
                }
                Iterator<Edge> edgesIterator = getEdges().iterator();
                while(edgesIterator.hasNext()) {
                        Edge e = edgesIterator.next();
                        g.addEdge(e.clone(), getEndpoints(e));
                }
                return g;
        }
        
        public int getAdjcncyWeight(Node v1){
                Iterator<Node> nbsIterator = getNeighbors(v1).iterator();
                int adjcncyWgt = 0;
                while(nbsIterator.hasNext()) {
                        Node v2 = nbsIterator.next();
                        Edge edge = findEdge(v1, v2);
                        adjcncyWgt += edge.getWeight();
                }
                return adjcncyWgt;
        }
        
        public void printForMetis(PrintStream output) {
                TreeMap<Integer,Node> map = new TreeMap<Integer,Node>();
                HashMap<Node,Integer> reverseMap = new HashMap<Node,Integer>();
                Iterator<Node> nodesIterator = getVertices().iterator();
                int id = 1;
                while(nodesIterator.hasNext()) {
                        Node node = nodesIterator.next();
                        map.put(id, node);
                        reverseMap.put(node,id);
                        id++;
                }
                output.println(getVertexCount() + " "+ getEdgeCount());
                Iterator<Integer> mappedIterator = map.keySet().iterator();
                while(mappedIterator.hasNext()) {
                        id = mappedIterator.next();
                        Iterator<Node> neighbors = getNeighbors(map.get(id)).iterator();
                        while(neighbors.hasNext()){
                                output.print(reverseMap.get(neighbors.next()));
                                if(neighbors.hasNext()) output.print(" ");
                        }
                        output.println();
                }
        }
        
        public String toString() {
                StringBuffer sb = new StringBuffer("Vertices:");
        for(Node v : getVertices()) {
                sb.append(v+ " Adjw: "+ getAdjcncyWeight(v) + ",");
        }
        sb.setLength(sb.length()-1);
        sb.append("\nEdges:");
        for(Edge e : getEdges()) {
                Pair<Node> ep = getEndpoints(e);
                sb.append(e+"["+ep.getFirst()+","+ep.getSecond()+"] ");
        }
        return sb.toString();
        }
}