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

Migrato il resto del codice verso Jung.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • 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;
Note: See TracChangeset for help on using the changeset viewer.