Changeset 9


Ignore:
Timestamp:
Sep 14, 2010, 2:11:28 PM (14 years ago)
Author:
gnappo
Message:

Migrato il resto del codice verso Jung.

Location:
src/main/java/weka/clusterers
Files:
1 added
1 deleted
10 edited

Legend:

Unmodified
Added
Removed

  • src/main/java/weka/clusterers/SimpleClusterer.java

    r7 r9  
    22
    33
    4 import weka.clusterers.forMetisMQI.Graph;
    54import weka.clusterers.forMetisMQI.GraphAlgorithms;
     5import weka.clusterers.forMetisMQI.UndirectedGraph;
    66import weka.core.Capabilities;
    77import weka.core.Instance;
    … …  
    2222                getCapabilities().testWithFail(data);
    2323               
    24                 Graph g = new Graph(data);
     24                UndirectedGraph g = new UndirectedGraph();
     25                g.loadFromInstance(data);
    2526                GraphAlgorithms ga = new GraphAlgorithms();
    2627                ga.METIS(g);

  • src/main/java/weka/clusterers/forMetisMQI/Coarse.java

    r8 r9  
    22
    33import java.io.PrintStream;
    4 import java.util.ArrayList;
     4import java.util.HashMap;
    55import java.util.HashSet;
    66import java.util.Iterator;
    7 import java.util.List;
     7import java.util.Map;
    88import java.util.Set;
    99import java.util.Stack;
     10
     11import edu.uci.ics.jung.graph.util.Pair;
    1012
    1113public class Coarse {
    … …  
    2325         * @return true if the vertex v is matched, false o.w.
    2426         */
    25         private static boolean isMatched(Graph g, List<Integer> match, int v) {
    26                 return match.get(g.getIndex(v)) != g.getIndex(v);
    27         }
    28 
    29         private static void RMMatch(Graph g, List<Integer> match, List<Integer> map) {
     27        private static boolean isMatched(Map<Node,Node> match, Node v) {
     28                if(match.containsKey(v))
     29                        return !match.get(v).equals(v);
     30                else
     31                        return false;
     32        }
     33
     34        private static void RMMatch(UndirectedGraph g, Map<Node,Node> match, Map<Node,Node> map) {
    3035                int labelCounter = 0;
    31                 for (int i = 0; i < g.size(); i++) {
    32                         match.add(i);
    33                         map.add(i);
    34                 }
    35                 g.adjncyPermutation();
    36                 Iterator<Integer> nodeIterator = g.vtxsPermutation().iterator();
     36                Iterator<Node> nodeIterator = g.vtxsPermutation().iterator();
    3737                while (nodeIterator.hasNext()) {
    38                         int u = nodeIterator.next();
     38                        Node u = nodeIterator.next();
    3939                        if (debug)
    40                                 debugStream.println("Visiting node " + u + " Matched = " + isMatched(g,match,u));
    41                         if (!isMatched(g,match,u)) {
     40                                debugStream.println("Visiting node " + u + " Matched = " + isMatched(match,u));
     41                        if (!isMatched(match,u)) {
    4242                                boolean foundMatch = false;
    43                                 int matchedNode = -1;
    44                                 Iterator<Integer> iterator = g.getNeighbors(u).iterator();
     43                                Node matchedNode = null;
     44                                Iterator<Node> iterator = g.getNeighborsPermutation(u).iterator();
    4545                                while(iterator.hasNext() && !foundMatch){
    46                                         int v = iterator.next();
    47                                         if (!isMatched(g,match,v)) {
     46                                        Node v = iterator.next();
     47                                        if (!isMatched(match,v)) {
    4848                                                matchedNode = v;
    4949                                                foundMatch = true;
    … …  
    5555                                if (debug && !foundMatch)
    5656                                        debugStream.println("There aren't unmatched neighbors.");
     57                                Node newNode = new Node(Integer.toString(labelCounter));
    5758                                if(foundMatch) {
    58                                         match.set(g.getIndex(u), g.getIndex(matchedNode));
    59                                         match.set(g.getIndex(matchedNode), g.getIndex(u));
    60                                         map.set(g.getIndex(u), labelCounter);
    61                                         map.set(g.getIndex(matchedNode), labelCounter);
    62                                         if(debug) debugStream.println("Contracting node " + u + " with " + matchedNode + ". Node id: " + getMappedNode(g, map, u));
     59                                        match.put(u, matchedNode);
     60                                        match.put(matchedNode, u);
     61                                        map.put(u, newNode);
     62                                        map.put(matchedNode, newNode);
     63                                        if(debug) debugStream.println("Contracting node " + u + " with " + matchedNode + ". Node id: " + getMappedNode(map, u));
    6364                                } else {
    64                                         map.set(g.getIndex(u), labelCounter);
    65                                         if(debug) debugStream.println("Node " + u + " with " + " new node id: " + getMappedNode(g, map, u));
     65                                        match.put(u, u);
     66                                        map.put(u, newNode);
     67                                        if(debug) debugStream.println("Node " + u + " with " + " new node id: " + getMappedNode(map, u));
    6668                                }
    6769                                labelCounter++;
    … …  
    7072        }
    7173       
    72         private static int getMatchedNode(Graph g, List<Integer> match, int u) {
    73                 return g.getLabel(match.get(g.getIndex(u)));
    74         }
    75        
    76         private static int getMappedNode(Graph g, List<Integer> map, int u) {
    77                 return map.get(g.getIndex(u));
     74        private static Node getMatchedNode(Map<Node,Node> match, Node u) {
     75                return match.get(u);
     76        }
     77       
     78        private static Node getMappedNode(Map<Node,Node> map, Node u) {
     79                return map.get(u);
    7880        }
    7981       
    … …  
    8183         * Return a new contracted graph.
    8284         */
    83         private static Graph contract(Graph g, List<Integer> match, List<Integer> map) {
    84                 Graph output = new Graph();
    85                 Iterator<Integer> iterator = g.iterator();
     85        private static UndirectedGraph contract(UndirectedGraph g, Map<Node,Node> match, Map<Node,Node> map) {
     86                UndirectedGraph output = new UndirectedGraph();
     87                Iterator<Node> iterator = g.getVertices().iterator();
     88                int i = 0;
    8689                while(iterator.hasNext()) {
    87                         int u = iterator.next();
    88                         output.addNode(getMappedNode(g,map,u));
    89                         Iterator<Integer> it = g.getNeighbors(u).iterator();
    90                         Set<Integer> neighbors = new HashSet<Integer>();
    91                         while(it.hasNext()) {
    92                                 int v = it.next();
    93                                 neighbors.add(getMappedNode(g,map,v));
    94                         }
    95                         it = g.getNeighbors(getMatchedNode(g,match,u)).iterator();
    96                         while(it.hasNext()) {
    97                                 int v = it.next();
    98                                 neighbors.add(getMappedNode(g,map,v));
    99                         }
    100                         neighbors.remove(getMappedNode(g,map,u));
     90                        Node u = iterator.next();
     91                        output.addVertex(getMappedNode(map,u));
     92                       
     93                        Set<Node> neighbors = new HashSet<Node>();
     94                        Iterator<Node> it = g.getNeighbors(u).iterator();
     95                        while(it.hasNext())
     96                                neighbors.add(getMappedNode(map, it.next()));
     97                        it = g.getNeighbors(getMatchedNode(match, u)).iterator();
     98                        while(it.hasNext())
     99                                neighbors.add(getMappedNode(map, it.next()));
     100                       
     101//                      Set<Node> neighbors = new HashSet<Node>();
     102//                      while(it.hasNext()) {
     103//                              Node v = it.next();
     104//                              neighbors.add(getMappedNode(map,v));
     105//                      }
     106//                      it = g.getNeighbors(getMappedNode(match,u)).iterator();
     107//                      while(it.hasNext()) {
     108//                              Node v = it.next();
     109//                              neighbors.add(getMappedNode(map,v));
     110//                      }
     111                        neighbors.remove(getMappedNode(map,u));
    101112                        it = neighbors.iterator();
    102113                        while(it.hasNext()) {
    103                                 int v = it.next();
    104                                 output.addNode(v);
    105                                 output.addEdgeUndirected(getMappedNode(g,map,u), v, 0);
    106                         }
    107                 }       
     114                                Node v = it.next();
     115                                output.addVertex(v);
     116                                output.addEdge(new Edge(Integer.toString(i),0,0),getMappedNode(map,u), v);
     117                                i++;
     118                        }
     119                }
     120               
    108121                //calcolo dei pesi del nuovo grafo: per ogni arco (u,v) && u < v.
    109                 //w(map(u),map(v)) += w(u,v).
    110                 for(int i=0; i < g.size(); i++) {
    111                         int u = g.getLabel(i);
    112                         Iterator<Integer> it = g.getNeighbors(u).iterator();
    113                         while(it.hasNext()) {
    114                                 int v = it.next();
    115                                 if(getMappedNode(g,map,u) != getMappedNode(g,map,v) && output.isEdge(getMappedNode(g,map,u), getMappedNode(g,map,v)) && u < v) {
    116                                         output.setWeight(getMappedNode(g,map,u), getMappedNode(g,map,v), output.getWeight(getMappedNode(g,map,u), getMappedNode(g,map,v)) + g.getWeight(u, v));
    117                                 }
    118                         }
    119                 }
    120                 for(int i=0; i < g.size(); i++) {
    121                         int u = g.getLabel(i);
    122                         if(isMatched(g,match,u)) {
    123                                 int v = getMatchedNode(g,match,u);
    124                                 if(u < v) {
    125                                         output.getNode(getMappedNode(g,map,u)).vwgt = g.getNode(u).vwgt + g.getNode(v).vwgt;
    126                                         output.getNode(getMappedNode(g,map,u)).cewgt = g.getNode(u).cewgt + g.getNode(v).cewgt +
    127                                         g.getWeight(u, v);
    128                                         output.getNode(getMappedNode(g,map,u)).adjwgt = g.getNode(u).adjwgt + g.getNode(v).adjwgt - 2 *
    129                                         g.getWeight(u, v);
     122                //w(map(u),map(v)) += w(u,v).
     123               
     124                Iterator<Edge> edgeIterator = g.getEdges().iterator();
     125                while(edgeIterator.hasNext()) {
     126                        Edge oldEdge = edgeIterator.next();
     127                        Pair<Node> srcDst = g.getEndpoints(oldEdge);
     128                        Node src = srcDst.getFirst();
     129                        Node dst = srcDst.getFirst();
     130                        Node srcMapped = getMappedNode(map, src);
     131                        Node dstMapped = getMappedNode(map, dst);
     132                        if(!srcMapped.equals(dstMapped) && output.containsEdge(srcMapped, dstMapped)) {
     133                                Edge newEdge = output.findEdge(srcMapped, dstMapped);
     134                                newEdge.setWeight(newEdge.getWeight() + oldEdge.getWeight());
     135                        }
     136                }
     137               
     138               
     139//              for(int i=0; i < g.size(); i++) {
     140//                      int u = g.getLabel(i);
     141//                      Iterator<Integer> it = g.getNeighbors(u).iterator();
     142//                      while(it.hasNext()) {
     143//                              int v = it.next();
     144//                              if(getMappedNode(g,map,u) != getMappedNode(g,map,v) && output.isEdge(getMappedNode(g,map,u), getMappedNode(g,map,v)) && u < v) {
     145//                                      output.setWeight(getMappedNode(g,map,u), getMappedNode(g,map,v), output.getWeight(getMappedNode(g,map,u), getMappedNode(g,map,v)) + g.getWeight(u, v));
     146//                              }
     147//                      }
     148//              }
     149               
     150               
     151                iterator = g.getVertices().iterator();
     152                Set<Node> nodesComplete = new HashSet<Node>();
     153                while(iterator.hasNext()) {
     154                        Node u = iterator.next();
     155                        if(isMatched(match,u)) {
     156                                Node v = getMatchedNode(match,u);
     157                                if(!nodesComplete.contains(u)) {
     158                                        getMappedNode(map,u).setVwgt(u.getVwgt() + v.getVwgt());
     159                                        getMappedNode(map,u).setCewgt(u.getCewgt() + v.getCewgt() + g.findEdge(u, v).getWeight());
     160                                        getMappedNode(map,u).setAdjwgt(u.getAdjwgt() + v.getAdjwgt() - 2 * g.findEdge(u, v).getWeight());
     161                                        nodesComplete.add(u);
     162                                        nodesComplete.add(v);
    130163                                }
    131164                        } else {
    132                                 output.getNode(getMappedNode(g,map,u)).vwgt = g.getNode(u).vwgt;
    133                                 output.getNode(getMappedNode(g,map,u)).cewgt = g.getNode(u).cewgt;
    134                                 output.getNode(getMappedNode(g,map,u)).adjwgt = g.getNode(u).adjwgt;
     165                                getMappedNode(map,u).setVwgt(u.getVwgt());
     166                                getMappedNode(map,u).setCewgt(u.getCewgt());
     167                                getMappedNode(map,u).setAdjwgt(u.getAdjwgt());
    135168                        }
    136169                }
    … …  
    141174         * Performs the first stage of the METIS algorithm, using RM.
    142175         */
    143         public static CoarserGraphElement coarseOneStep(Graph g) {
    144                 Graph projected = g;
    145                 Graph contracted = null;
    146                 List<Integer> match = new ArrayList<Integer>();
    147                 List<Integer> map = new ArrayList<Integer>();
     176        public static CoarserGraphElement coarseOneStep(UndirectedGraph g) {
     177                UndirectedGraph projected = g;
     178                UndirectedGraph contracted = null;
     179                Map<Node,Node> match = new HashMap<Node,Node>();
     180                Map<Node,Node> map = new HashMap<Node,Node>();
    148181                RMMatch(g,match,map);
    149182                contracted = contract(g,match,map);
    … …  
    151184        }
    152185       
    153         public static Stack<CoarserGraphElement> coarse(Graph g) {
     186        public static Stack<CoarserGraphElement> coarse(UndirectedGraph g) {
    154187                Stack<CoarserGraphElement> stack = new Stack<CoarserGraphElement>();
    155188                CoarserGraphElement e;
    156                 Graph curr = g;
     189                UndirectedGraph curr = g;
    157190            do {
    158191                if(debug)
    … …  
    163196                if(debug)
    164197                        debugStream.println("-----------------------------------------------------");
    165             } while(e.getProjected().size() > e.getContracted().size() && e.getContracted().size() > finerSize);
     198            } while(e.getProjected().getVertexCount() > e.getContracted().getVertexCount() && e.getContracted().getVertexCount() > finerSize);
    166199            return stack;
    167200        }

  • src/main/java/weka/clusterers/forMetisMQI/CoarserGraphElement.java

    r7 r9  
    11package weka.clusterers.forMetisMQI;
    22
    3 import java.util.List;
     3import java.util.Map;
    44
    55public class CoarserGraphElement {
    66       
    7         private Graph contracted;
    8         private Graph projected;
    9         private List<Integer> match;
    10         private List<Integer> map;
     7        private UndirectedGraph contracted;
     8        private UndirectedGraph projected;
     9        private Map<Node,Node> match;
     10        private Map<Node,Node> map;
    1111       
    12         public CoarserGraphElement(Graph contracted, Graph projected, List<Integer> match, List<Integer> map) {
     12        public CoarserGraphElement(UndirectedGraph contracted, UndirectedGraph projected, Map<Node,Node> match, Map<Node,Node> map) {
    1313                this.contracted = contracted;
    1414                this.projected = projected;
    … …  
    1717        }
    1818       
    19         public List<Integer> getMatch() {
     19        public Map<Node,Node> getMatch() {
    2020                return match;
    2121        }
    2222       
    23         public List<Integer> getMap() {
     23        public Map<Node,Node> getMap() {
    2424                return map;
    2525        }
    2626       
    27         public Graph getContracted() {
     27        public UndirectedGraph getContracted() {
    2828                return contracted;
    2929        }
    3030       
    31         public Graph getProjected() {
     31        public UndirectedGraph getProjected() {
    3232                return projected;
    3333        }

  • src/main/java/weka/clusterers/forMetisMQI/Edge.java

    r8 r9  
    5151        }
    5252
     53        public void setWeight(int weight) {
     54                this.weight = weight;
     55        }
     56
     57        public void setCapacity(int capacity) {
     58                this.capacity = capacity;
     59        }
     60       
     61        @Override
     62        public Edge clone(){
     63                Edge e = new Edge(id, weight, capacity);
     64                return e;
     65        }
     66
    5367}

  • src/main/java/weka/clusterers/forMetisMQI/GraphAlgorithms.java

    r8 r9  
    55public class GraphAlgorithms {
    66       
    7         public KLPartition KL(Graph g) {
     7        public KLPartition KL(UndirectedGraph g) {
    88                KLPartition partition = new KLPartition(g);
    99                KLPartition result = partition;
    1010                int bestEdgeCut = Integer.MAX_VALUE;
    11                 int u = partition.getCandidate();
    12                 while(u != -1) {
     11                Node u = partition.getCandidate();
     12                while(u != null) {
    1313                        partition.swap(u);
    1414                        if(partition.edgeCut() <=  bestEdgeCut) {
    1515                                bestEdgeCut = partition.edgeCut();
    16                                 result = partition.clone();
     16                                result = partition.copy();
    1717                        }
    1818                        u = partition.getCandidate();
    … …  
    2121        }
    2222       
    23         public void METIS(Graph g) {
     23        public void METIS(UndirectedGraph g) {
    2424                KLPartition partition = null;
    2525                Coarse.setFinerSize(10);

  • src/main/java/weka/clusterers/forMetisMQI/KLPartition.java

    r8 r9  
    11package weka.clusterers.forMetisMQI;
    22
    3 import java.util.ArrayList;
     3import java.util.HashSet;
    44import java.util.Iterator;
    5 import java.util.List;
     5import java.util.Set;
    66
    77
    … …  
    1212        private Subgraph b = null;
    1313       
    14         private List<Integer> marked = null;
     14        private Set<Node> marked = null;
    1515
    1616        private KLPartition() {
    … …  
    1818       
    1919        public KLPartition(Subgraph s) {
    20                 Graph g  = s.getGraph();
     20                UndirectedGraph g  = s.getGraph();
    2121                a = s;
    2222                b = new Subgraph(g);
    23                 Iterator<Integer> graphIterator =  g.iterator();
     23                Iterator<Node> graphIterator =  g.getVertices().iterator();
    2424                while(graphIterator.hasNext()) {
    25                         int u = graphIterator.next();
     25                        Node u = graphIterator.next();
    2626                        if(!s.contains(u))
    27                                 b.addNode(u);
     27                                b.addVertex(u);
    2828                }
    29                 marked = new ArrayList<Integer>();
     29                marked = new HashSet<Node>();
    3030        }
    3131       
    32         public KLPartition(Graph g){
     32        public KLPartition(UndirectedGraph g){
    3333                a = new Subgraph(g);
    3434                b = new Subgraph(g);
    35                 Iterator<Integer> graph = g.vtxsPermutation().iterator();
     35                Iterator<Node> graph = g.vtxsPermutation().iterator();
    3636                int i = 0;
    3737                while(graph.hasNext()) {
    38                         int u = graph.next();
     38                        Node u = graph.next();
    3939                        if((i%2)==0)
    40                                 a.addNode(u);
     40                                a.addVertex(u);
    4141                        else
    42                                 b.addNode(u);
     42                                b.addVertex(u);
    4343                        i++;
    4444                }
    45                 marked = new ArrayList<Integer>();
     45                marked = new HashSet<Node>();
    4646        }
    4747       
    4848        /**
    49          * Returns the node marked as candidate for swapping or -1 if there aren't node available
     49         * Returns the node marked as candidate for swapping or <code>null</code> if there aren't node available
    5050         * for swapping.
    5151         * @return
    5252         */
    53         public int getCandidate() {
    54                 int u;
    55                 if(a.size() > b.size()) {
     53        public Node getCandidate() {
     54                Node u;
     55                if(a.getVertexCount() > b.getVertexCount()) {
    5656                        u = a.getCandidate(marked);
    57                         if(u == -1)
     57                        if(u == null)
    5858                                u = b.getCandidate(marked);
    5959                } else {
    6060                        u = b.getCandidate(marked);
    61                         if(u == -1)
     61                        if(u == null)
    6262                                u = a.getCandidate(marked);
    6363                }
    64                 if(u != -1) {
     64                if(u != null) {
    6565                        marked.add(u);
    6666                }
    … …  
    6868        }
    6969       
    70         public void swap(int u) {
     70        public void swap(Node u) {
    7171                Subgraph from = fromSubgraph(u);
    7272                Subgraph to = toSubgraph(u);
    73                 from.remove(u);
    74                 to.addNode(u);
     73                from.removeVertex(u);
     74                to.addVertex(u);
    7575        }
    7676       
    77         private Subgraph fromSubgraph(int u) {
     77        private Subgraph fromSubgraph(Node u) {
    7878                Subgraph ret = null;
    7979                if(a.contains(u))
    … …  
    8484        }
    8585       
    86         private Subgraph toSubgraph(int u) {
     86        private Subgraph toSubgraph(Node u) {
    8787                Subgraph ret = null;
    8888                if(!a.contains(u))
    … …  
    106106        }
    107107       
    108         @Override
    109         public KLPartition clone(){
     108        public KLPartition copy(){
    110109                KLPartition clone = new KLPartition();
    111110                clone.a = (Subgraph) a.clone();
    112111                clone.b = (Subgraph) b.clone();
    113                 clone.marked = new ArrayList<Integer>();
    114                 for(int i = 0; i < marked.size(); i++) {
    115                         clone.marked.add(marked.get(i));
    116                 }
     112                clone.marked = new HashSet<Node>();
    117113                return clone;
    118114        }

  • src/main/java/weka/clusterers/forMetisMQI/MQI.java

    r8 r9  
    66import javax.swing.JFrame;
    77
    8 import edu.uci.ics.jung.algorithms.layout.CircleLayout;
     8import edu.uci.ics.jung.algorithms.layout.KKLayout;
    99import edu.uci.ics.jung.algorithms.layout.Layout;
    1010import edu.uci.ics.jung.graph.DirectedSparseGraph;
    … …  
    1616       
    1717        public static void viewGraph(Graph<Node, Edge> g){
    18                 Layout<Node, Edge> layout = new CircleLayout<Node, Edge>(g);
     18                Layout<Node, Edge> layout = new KKLayout<Node, Edge>(g);
    1919                layout.setSize(new Dimension(300,300)); // sets the initial size of the space
    2020                // The BasicVisualizationServer<V,E> is parameterized by the edge types
    … …  
    3333                Subgraph A = null;
    3434                Subgraph B = null;
    35                 if(partition.getSubgraph().size() > partition.getComplement().size()) {
     35                if(partition.getSubgraph().getVertexCount() > partition.getComplement().getVertexCount()) {
    3636                        A = partition.getSubgraph();
    3737                        B = partition.getComplement();
    … …  
    4141                        B = partition.getSubgraph();
    4242                }
    43                 int a = A.size();
     43                int a = A.getVertexCount();
    4444                int c = partition.edgeCut();
    4545               
    4646               
    4747                Graph<Node,Edge> g = new DirectedSparseGraph<Node, Edge>();
    48                 Iterator<Integer> nodes =  A.iterator();
     48                Iterator<Node> nodes =  A.iterator();
    4949                while(nodes.hasNext()) {
    50                         int u = nodes.next();
    51                         g.addVertex(new Node(Integer.toString(u)));
     50                        Node u = nodes.next();
     51                        g.addVertex(u);
    5252                }
    5353               
    … …  
    5555                int id = 0;
    5656                while(nodes.hasNext()) {
    57                         int u = nodes.next();
    58                         Iterator<Integer> neighbors = A.getNeighbours(u).iterator();
     57                        Node u = nodes.next();
     58                        Iterator<Node> neighbors = A.getNeighbors(u).iterator();
    5959                        while(neighbors.hasNext()) {
    60                                 int v = neighbors.next();
    61                                 g.addEdge(new Edge(Integer.toString(id),A.getWeight(u, v),a),new Node(Integer.toString(u)),new Node(Integer.toString(v)));
     60                                Node v = neighbors.next();
     61                                g.addEdge(new Edge(Integer.toString(id),A.getWeight(u, v),a),u,v);
    6262                                id++;
    6363                        }
    … …  
    7272                nodes =  B.iterator();
    7373                while(nodes.hasNext()) {
    74                         int u = nodes.next();
    75                         Iterator<Integer> neighbors = B.getGraph().getNeighbors(u).iterator();
     74                        Node u = nodes.next();
     75                        Iterator<Node> neighbors = B.getGraph().getNeighbors(u).iterator();
    7676                        while(neighbors.hasNext()) {
    77                                 int v = neighbors.next();
     77                                Node v = neighbors.next();
    7878                                if(A.contains(v)) {
    79                                         g.addEdge(new Edge(Integer.toString(id),1,a),source,new Node(Integer.toString(v)));
     79                                        g.addEdge(new Edge(Integer.toString(id),1,a),source,v);
    8080                                        id++;
    8181                                }
    … …  
    8585                nodes =  A.iterator();
    8686                while(nodes.hasNext()) {
    87                         int u = nodes.next();
    88                         g.addEdge(new Edge(Integer.toString(id),1,c),new Node(Integer.toString(u)),sink);
     87                        Node u = nodes.next();
     88                        g.addEdge(new Edge(Integer.toString(id),1,c),u,sink);
    8989                        id++;
    9090                }

  • src/main/java/weka/clusterers/forMetisMQI/Node.java

    r8 r9  
    11package weka.clusterers.forMetisMQI;
    22
     3
    34public class Node {
    4        
     5
    56        private String id;
    6        
     7
     8        /** The weight of the node */
     9        private int vwgt;
     10        /** The size of the adjacency list of the node */
     11        private int nedges;
     12        /**
     13         * The index into the adjacency list that is the beginning of the adjacency
     14         * list of v
     15         */
     16        private int iedges;
     17        /** The weight of the edges that have been contracted to create the node */
     18        private int cewgt;
     19        /** The sum of the weight of the edges adjacent to v */
     20        private int adjwgt;
     21
    722        public Node(String id) {
    823                this.id = id;
     24                this.vwgt = 1;
     25                this.cewgt = 0;
     26                this.iedges = 0;
     27                this.nedges = 0;
     28                this.adjwgt = 0;
    929        }
    10        
     30
    1131        @Override
    1232        public boolean equals(Object o) {
    13                 return (o instanceof Node) && (((Node)o).getId().equals(id));
     33                return (o instanceof Node) && (((Node) o).getId().equals(id));
    1434        }
    15        
     35
    1636        @Override
    1737        public int hashCode() {
    … …  
    2444                return id;
    2545        }
    26        
     46
    2747        @Override
    2848        public String toString() {
    … …  
    3050        }
    3151
     52        public int getVwgt() {
     53                return vwgt;
     54        }
     55
     56        public void setVwgt(int vwgt) {
     57                this.vwgt = vwgt;
     58        }
     59
     60        public int getNedges() {
     61                return nedges;
     62        }
     63
     64        public void setNedges(int nedges) {
     65                this.nedges = nedges;
     66        }
     67
     68        public int getIedges() {
     69                return iedges;
     70        }
     71
     72        public void setIedges(int iedges) {
     73                this.iedges = iedges;
     74        }
     75
     76        public int getCewgt() {
     77                return cewgt;
     78        }
     79
     80        public void setCewgt(int cewgt) {
     81                this.cewgt = cewgt;
     82        }
     83
     84        public int getAdjwgt() {
     85                return adjwgt;
     86        }
     87
     88        public void setAdjwgt(int adjwgt) {
     89                this.adjwgt = adjwgt;
     90        }
     91       
     92        @Override
     93        public Node clone() {
     94                Node n = new Node(id);
     95                n.adjwgt = adjwgt;
     96                n.cewgt = cewgt;
     97                n.iedges = iedges;
     98                n.nedges = nedges;
     99                n.vwgt = vwgt;
     100                return n;
     101        }
     102
    32103}

  • src/main/java/weka/clusterers/forMetisMQI/Subgraph.java

    r8 r9  
    22
    33import java.util.ArrayList;
    4 import java.util.BitSet;
    54import java.util.HashMap;
     5import java.util.HashSet;
    66import java.util.Iterator;
    77import java.util.List;
     8import java.util.Set;
    89import java.util.SortedSet;
    910import java.util.TreeSet;
    … …  
    1213public class Subgraph {
    1314       
    14         private Graph g = null;
    15         private BitSet nodes = null;
    16         private List<Integer> listOfNodes = null;
    17         private HashMap<Integer,Integer> ID = null;
    18         private HashMap<Integer,Integer> ED = null;
    19         private HashMap<Integer,List<Integer>> bucketGain = null;
     15        private UndirectedGraph g = null;
     16       
     17        private Set<Node> nodes = null;
     18       
     19//      private BitSet nodes = null;
     20//      private List<Integer> listOfNodes = null;
     21        private HashMap<Node,Integer> ID = null;
     22        private HashMap<Node,Integer> ED = null;
     23        private HashMap<Integer,List<Node>> bucketGain = null;
    2024        private SortedSet<Integer> gainSet = null;
    2125        private boolean recomputeGain = true;
    2226       
    23         public Subgraph(Graph g){
     27        public Subgraph(UndirectedGraph g){
    2428                this.g = g;
    25                 nodes = new BitSet(g.size());
    26                 listOfNodes = new ArrayList<Integer>();
    27                 ID = new HashMap<Integer,Integer>();
    28                 ED = new HashMap<Integer,Integer>();
    29                 bucketGain = new HashMap<Integer, List<Integer>>();
     29                nodes = new HashSet<Node>();
     30                ID = new HashMap<Node,Integer>();
     31                ED = new HashMap<Node,Integer>();
     32                bucketGain = new HashMap<Integer, List<Node>>();
    3033                gainSet = new TreeSet<Integer>();
    3134        }
    3235       
    33         public Graph getGraph() {
     36        public UndirectedGraph getGraph() {
    3437                return g;
    3538        }
    3639       
    37         public void addNode(int u) {
    38                 nodes.set(g.getIndex(u));
    39                 listOfNodes.add(u);
     40        public void addVertex(Node u) {
     41                nodes.add(u);
    4042                ID.put(u, 0);
    4143                ED.put(u, 0);
    … …  
    4446       
    4547        private void computeDegree() {
    46                 for(int i = 0; i < size(); i++) {
    47                         int u = listOfNodes.get(i);
    48                         Iterator<Integer> it = g.getNeighbors(u).iterator();
     48                Iterator<Node> subgraphIterator = nodes.iterator();
     49                while(subgraphIterator.hasNext()) {
     50                        Node u = subgraphIterator.next();
     51                        Iterator<Node> nborsIterator = g.getNeighbors(u).iterator();
    4952                        int newID = 0;
    5053                        int newED = 0;
    51                         while(it.hasNext()) {
    52                                 int v = it.next();
     54                        while(nborsIterator.hasNext()) {
     55                                Node v = nborsIterator.next();
    5356                                if(contains(v))
    54                                         newID = newID + g.getWeight(u, v);
     57                                        newID = newID + g.findEdge(u, v).getWeight();
    5558                                else
    56                                         newED = newED + g.getWeight(u, v);
     59                                        newED = newED + g.findEdge(u, v).getWeight();
    5760                                ID.put(u, newID);
    5861                                ED.put(u, newED);
    … …  
    6770                ED.clear();
    6871                computeDegree();
    69                 for(int i = 0; i < size(); i++) {
    70                         int u = listOfNodes.get(i);
     72                Iterator<Node> subgraphIterator = nodes.iterator();
     73                while(subgraphIterator.hasNext()) {
     74                        Node u = subgraphIterator.next();
    7175                        int gainU = ED.get(u) - ID.get(u);
    7276                        if(!bucketGain.containsKey(gainU)) {
    73                                 bucketGain.put(gainU, new ArrayList<Integer>());
     77                                bucketGain.put(gainU, new ArrayList<Node>());
    7478                        }
    7579                        bucketGain.get(gainU).add(u);
    … …  
    7983        }
    8084       
    81         public int getCandidate() {
    82                 return getCandidate(new ArrayList<Integer>());
     85        public Node getCandidate() {
     86                return getCandidate(new HashSet<Node>());
    8387        }
    8488       
    … …  
    8690         *
    8791         * @param marked
    88          * @return the candidate node for swap or -1 if there aren't available nodes.
     92         * @return the candidate node for swap or <code>null</code> if there aren't available nodes.
    8993         */
    90         public int getCandidate(List<Integer> marked) {
    91                 if(recomputeGain)
    92                         computeGain();
    93                 int candidate = -1;
     94        public Node getCandidate(Set<Node> marked) {
     95                if(recomputeGain)
     96                        computeGain();
     97                Node candidate = null;
    9498                Iterator<Integer> iterator = ((TreeSet<Integer>)gainSet).descendingIterator();
    95                 while(iterator.hasNext() && (candidate == -1)) {
     99                while(iterator.hasNext() && (candidate == null)) {
    96100                        int gain = iterator.next();
    97                         Iterator<Integer> nodes = bucketGain.get(gain).iterator();
    98                         while(nodes.hasNext() && (candidate == -1)) {
    99                                 int u = nodes.next();
     101                        Iterator<Node> nodes = bucketGain.get(gain).iterator();
     102                        while(nodes.hasNext() && (candidate == null)) {
     103                                Node u = nodes.next();
    100104                                if(!marked.contains(u))
    101105                                        candidate = u;
    … …  
    105109        }
    106110       
    107         public int gain(int u){
     111        public int gain(Node u){
    108112                if(recomputeGain)
    109113                        computeGain();
    … …  
    111115        }
    112116       
    113         public void remove(int u) {
     117        public void removeVertex(Node u) {
    114118                if(recomputeGain)
    115119                        computeGain();
    116120                int gainU = gain(u);
    117                 nodes.set(g.getIndex(u), false);
    118                 listOfNodes.remove(listOfNodes.indexOf(u));
     121                nodes.remove(u);
    119122                ID.remove(u);
    120123                ED.remove(u);
    121                 List<Integer> l = bucketGain.get(gainU);
     124                List<Node> l = bucketGain.get(gainU);
    122125                l.remove(l.indexOf(u));
    123126                if(l.size() == 0) {
    … …  
    128131        }
    129132       
    130         public int size() {
    131                 return listOfNodes.size();
    132         }
    133        
    134         public int getWeight(int u, int v) {
     133        public int getVertexCount() {
     134                return nodes.size();
     135        }
     136       
     137        public Edge findEdge(Node v1, Node v2) {
     138                Edge e = null;
     139                if(contains(v1) && contains(v2))
     140                        e = g.findEdge(v1, v2);
     141                return e;
     142        }
     143       
     144        public int getWeight(Node u, Node v) {
    135145                int ret = -1;
    136                 if(isEdge(u,v))
    137                         ret = g.getWeight(u, v);
     146                if(containsEdge(u,v))
     147                        ret = g.findEdge(u, v).getWeight();
    138148                return ret;
    139149        }
    140150       
    141         public Iterator<Integer> iterator() {
    142                 return listOfNodes.iterator();
    143         }
    144        
    145         public boolean isEdge(int u, int v) {
    146                 return nodes.get(g.getIndex(u)) && nodes.get(g.getIndex(v)) && g.isEdge(u, v);
    147         }
    148        
    149         public boolean contains(int u) {
    150                 return nodes.get(g.getIndex(u));
    151         }
    152        
    153         public List<Integer> getNeighbours(int u) {
    154                 List<Integer> neighbors = new ArrayList<Integer>();
    155                 Iterator<Integer> iterator = g.getNeighbors(u).iterator();
     151        public Iterator<Node> iterator() {
     152                return nodes.iterator();
     153        }
     154       
     155        public boolean containsEdge(Node u, Node v) {
     156                return contains(u) && contains(v) && g.containsEdge(u, v);
     157        }
     158       
     159        public boolean contains(Node u) {
     160                return nodes.contains(u);
     161        }
     162       
     163        public List<Node> getNeighbors(Node u) {
     164                List<Node> neighbors = new ArrayList<Node>();
     165                Iterator<Node> iterator = g.getNeighbors(u).iterator();
    156166                while(iterator.hasNext()) {
    157                         int v = iterator.next();
    158                         if(contains(v) && isEdge(u, v))
     167                        Node v = iterator.next();
     168                        if(contains(v) && containsEdge(u, v))
    159169                                neighbors.add(v);
    160170                }
    … …  
    175185        public String toString() {
    176186                String out = "[";
    177                 Iterator<Integer> it = listOfNodes.iterator();
     187                Iterator<Node> it = nodes.iterator();
    178188                while(it.hasNext()) {
    179                         int u = it.next();
     189                        Node u = it.next();
    180190                        out = out + u + ",";
    181191                }
    … …  
    184194        }
    185195       
    186         public List<Integer> getBoundary() {
    187                 if(recomputeGain)
    188                         computeGain();
    189                 Iterator<Entry<Integer,Integer>> EDIterator = ED.entrySet().iterator();
    190                 List<Integer> boundary = new ArrayList<Integer>();
     196        public List<Node> getBoundary() {
     197                if(recomputeGain)
     198                        computeGain();
     199                Iterator<Entry<Node,Integer>> EDIterator = ED.entrySet().iterator();
     200                List<Node> boundary = new ArrayList<Node>();
    191201                while(EDIterator.hasNext()) {
    192                         Entry<Integer,Integer> entry = EDIterator.next();
     202                        Entry<Node,Integer> entry = EDIterator.next();
    193203                        if(entry.getValue() > 0)
    194204                                boundary.add(entry.getKey());
    … …  
    206216                clone.g = g.clone();
    207217               
    208                 clone.nodes = (BitSet)nodes.clone();
    209                
    210                 clone.listOfNodes = new ArrayList<Integer>();
    211                 for(int i = 0; i < listOfNodes.size(); i++) {
    212                         clone.listOfNodes.add(listOfNodes.get(i));
    213                 }
    214                
    215                 clone.ID = new HashMap<Integer, Integer>();
    216                 Iterator<Entry<Integer,Integer>> i = ID.entrySet().iterator();
    217                 while(i.hasNext()) {
    218                         Entry<Integer,Integer> entry = i.next();
    219                         clone.ID.put(entry.getKey(), entry.getValue());
    220                 }
    221                
    222                 clone.ED = new HashMap<Integer, Integer>();
    223                 i = ED.entrySet().iterator();
    224                 while(i.hasNext()) {
    225                         Entry<Integer,Integer> entry = i.next();
    226                         clone.ED.put(entry.getKey(), entry.getValue());
    227                 }
    228                
    229                 clone.bucketGain = new HashMap<Integer, List<Integer>>();
    230                 Iterator<Entry<Integer,List<Integer>>>it = bucketGain.entrySet().iterator();
    231                 while(it.hasNext()) {
    232                         Entry<Integer,List<Integer>> entry = it.next();
    233                         List<Integer> bucketClone = new ArrayList<Integer>();
    234                         List<Integer> bucket = entry.getValue();
    235                         for(int j = 0; j < bucket.size(); j++) {
    236                                 bucketClone.add(bucket.get(j));
    237                         }
    238                         clone.bucketGain.put(entry.getKey(), bucketClone);
    239                 }
    240                
     218                clone.nodes = new HashSet<Node>();
     219                Iterator<Node> graphIterator =clone.g.getVertices().iterator();
     220                while(graphIterator.hasNext()) {
     221                        Node u = graphIterator.next();
     222                        if(contains(u))
     223                                clone.nodes.add(u);
     224                }
     225               
     226                clone.bucketGain = new HashMap<Integer, List<Node>>();
    241227                clone.gainSet = new TreeSet<Integer>();
    242                 Iterator<Integer> gainIt = gainSet.iterator();
    243                 while(gainIt.hasNext()) {
    244                         gainSet.add(gainIt.next());
    245                 }
    246                
    247                 clone.recomputeGain = recomputeGain;
     228                clone.ID = new HashMap<Node, Integer>();
     229                clone.ED = new HashMap<Node, Integer>();
     230               
     231                clone.computeGain();
    248232               
    249233                return clone;

  • src/main/java/weka/clusterers/forMetisMQI/Uncoarse.java

    r7 r9  
    66public class Uncoarse {
    77       
    8         private boolean projectedBelongs(int u, KLPartition partition, CoarserGraphElement cge) {
     8        private boolean projectedBelongs(Node u, KLPartition partition, CoarserGraphElement cge) {
    99                Subgraph s = partition.getSubgraph();
    10                 int index = cge.getProjected().getIndex(u);
    11                 int mappedNode = cge.getMap().get(index);
     10                Node mappedNode = cge.getMap().get(u);
    1211                return s.contains(mappedNode);
    1312        }
    … …  
    2019         */
    2120        public KLPartition uncoarseOneStep(KLPartition partition, CoarserGraphElement cge) {
    22                 Graph projected = cge.getProjected();
     21                UndirectedGraph projected = cge.getProjected();
    2322                Subgraph part = new Subgraph(projected);
    24                 Iterator<Integer> projectedIterator = projected.iterator();
     23                Iterator<Node> projectedIterator = projected.getVertices().iterator();
    2524                while(projectedIterator.hasNext()) {
    26                         int u = projectedIterator.next();
     25                        Node u = projectedIterator.next();
    2726                        if(projectedBelongs(u,partition,cge))
    28                                 part.addNode(u);
     27                                part.addVertex(u);
    2928                }
    3029                return new KLPartition(part);
Note: See TracChangeset for help on using the changeset viewer.