Ignore:
Timestamp:
Sep 10, 2010, 10:51:27 AM (14 years ago)
Author:
gnappo
Message:

Implementazione di Metis: aggiunta fase di uncoarsing e algoritmo di bisezione. Un po' di refactoring.

Location:
src/main/java/weka/clusterers/forMetisMQI
Files:
4 added
3 edited

Legend:

Unmodified
Added
Removed

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

    r6 r7  
    55public class CoarserGraphElement {
    66       
    7         private Graph g;
     7        private Graph contracted;
     8        private Graph projected;
    89        private List<Integer> match;
    910        private List<Integer> map;
    1011       
    11         public CoarserGraphElement(Graph g, List<Integer> match, List<Integer> map) {
    12                 this.g = g;
     12        public CoarserGraphElement(Graph contracted, Graph projected, List<Integer> match, List<Integer> map) {
     13                this.contracted = contracted;
     14                this.projected = projected;
    1315                this.match = match;
    1416                this.map = map;
    … …  
    2325        }
    2426       
    25         public Graph getGraph() {
    26                 return g;
     27        public Graph getContracted() {
     28                return contracted;
     29        }
     30       
     31        public Graph getProjected() {
     32                return projected;
    2733        }
    2834

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

    r6 r7  
    66import java.util.Iterator;
    77import java.util.List;
     8import java.util.Map.Entry;
    89
    910import weka.core.Attribute;
    … …  
    4142                        return "Vwgt: " + vwgt + " Cewgt: " + cewgt + " Iedges: " + iedges
    4243                                        + " Nedges: " + nedges + " Adjwgt: " + adjwgt;
     44                }
     45               
     46                @Override
     47                public NodeInfo clone() {
     48                        NodeInfo ni = new NodeInfo();
     49                        ni.adjwgt = adjwgt;
     50                        ni.cewgt = cewgt;
     51                        ni.iedges = iedges;
     52                        ni.nedges = nedges;
     53                        ni.vwgt = vwgt;
     54                        return ni;
    4355                }
    4456        }
    … …  
    107119         * @return
    108120         */
    109         private int getLabel(int index) {
     121        public int getLabel(int index) {
    110122                return this.index.get(index);
    111123        }
    … …  
    116128         * @return
    117129         */
    118         private int getIndex(int label) {
     130        public int getIndex(int label) {
    119131                return this.label.get(label);
    120132        }
    … …  
    307319                }
    308320        }
     321       
     322       
     323        @Override
     324        public Graph clone() {
     325                Graph g = new Graph();
     326                g.adjncy = new ArrayList<Integer>();
     327                for(int i = 0; i < adjncy.size(); i++) {
     328                        g.adjncy.add(adjncy.get(i));
     329                }
     330               
     331                g.weights = new ArrayList<Integer>();
     332                for(int i = 0; i < weights.size(); i++) {
     333                        g.weights.add(weights.get(i));
     334                }
     335               
     336                g.vtxs = new ArrayList<NodeInfo>();
     337                for(int i = 0; i < vtxs.size(); i++) {
     338                        g.vtxs.add(vtxs.get(i).clone());
     339                }
     340               
     341                g.index = new HashMap<Integer, Integer>();
     342                Iterator<Entry<Integer,Integer>> i = index.entrySet().iterator();
     343                while(i.hasNext()) {
     344                        Entry<Integer,Integer> entry = i.next();
     345                        g.index.put(entry.getKey(), entry.getValue());
     346                }
     347               
     348                g.label = new HashMap<Integer, Integer>();
     349                i = label.entrySet().iterator();
     350                while(i.hasNext()) {
     351                        Entry<Integer,Integer> entry = i.next();
     352                        g.label.put(entry.getKey(), entry.getValue());
     353                }
     354               
     355               
     356                return g;
     357        }
    309358}

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

    r6 r7  
    11package weka.clusterers.forMetisMQI;
    22
    3 import java.io.PrintStream;
    4 import java.util.ArrayList;
    5 import java.util.HashSet;
    6 import java.util.Iterator;
    7 import java.util.List;
    8 import java.util.Set;
     3import java.util.Stack;
    94
    105public class GraphAlgorithms {
    116       
    12         boolean debug = true;
    13         PrintStream debugStream = System.err;
    14        
    15         /**
    16          * Return true if the vertex v is matched
    17          *
    18          * @param v
    19          *            the index of the vertex
    20          * @return true if the vertex v is matched, false o.w.
    21          */
    22         private boolean isMatched(List<Integer> match, int v) {
    23                 return match.get(v) != v;
    24         }
    25 
    26         private void RMMatch(Graph g, List<Integer> match, List<Integer> map) {
    27                 int labelCounter = 0;
    28                 for (int i = 0; i < g.size(); i++) {
    29                         match.add(i);
    30                         map.add(i);
     7        public KLPartition KL(Graph g) {
     8                KLPartition partition = new KLPartition(g);
     9                KLPartition result = partition;
     10                int bestEdgeCut = Integer.MAX_VALUE;
     11                int u = partition.getCandidate();
     12                while(u != -1) {
     13                        partition.swap(u);
     14                        if(partition.edgeCut() <=  bestEdgeCut) {
     15                                bestEdgeCut = partition.edgeCut();
     16                                result = partition.clone();
     17                        }
     18                        u = partition.getCandidate();
    3119                }
    32                 g.adjncyPermutation();
    33                 Iterator<Integer> nodeIterator = g.vtxsPermutation().iterator();
    34                 while (nodeIterator.hasNext()) {
    35                         int u = nodeIterator.next();
    36                         if (debug)
    37                                 debugStream.println("Visiting node " + u + " Matched = " + isMatched(match,u));
    38                         if (!isMatched(match,u)) {
    39                                 boolean foundMatch = false;
    40                                 int matchedNode = -1;
    41                                 Iterator<Integer> iterator = g.getNeighbors(u).iterator();
    42                                 while(iterator.hasNext() && !foundMatch){
    43                                         int v = iterator.next();
    44                                         if (!isMatched(match,v)) {
    45                                                 matchedNode = v;
    46                                                 foundMatch = true;
    47                                                 if (debug)
    48                                                         debugStream.println("Found a match with node "
    49                                                                         + matchedNode);
    50                                         }
    51                                 }
    52                                 if (debug && !foundMatch)
    53                                         debugStream.println("There aren't unmatched neighbors.");
    54                                 if(foundMatch) {
    55                                         match.set(u, matchedNode);
    56                                         match.set(matchedNode, u);
    57                                         map.set(u, labelCounter);
    58                                         map.set(matchedNode, labelCounter);
    59                                         if(debug) debugStream.println("Contracting node " + u + " with " + matchedNode + ". Node id: " + map.get(u));
    60                                 } else
    61                                         map.set(u, labelCounter);
    62                                 labelCounter++;
    63                         }
    64                 }
     20                return result;
    6521        }
    6622       
    67         /**
    68          * Return a new contracted graph.
    69          */
    70         private Graph contract(Graph g, List<Integer> match, List<Integer> map) {
    71                 Graph output = new Graph();
    72                 Iterator<Integer> iterator = g.iterator();
    73                 while(iterator.hasNext()) {
    74                         int u = iterator.next();
    75                         output.addNode(map.get(u));
    76                         Iterator<Integer> it = g.getNeighbors(u).iterator();
    77                         Set<Integer> neighbors = new HashSet<Integer>();
    78                         while(it.hasNext()) {
    79                                 int v = it.next();
    80                                 neighbors.add(map.get(v));
    81                         }
    82                         it = g.getNeighbors(match.get(u)).iterator();
    83                         while(it.hasNext()) {
    84                                 int v = it.next();
    85                                 neighbors.add(map.get(v));
    86                         }
    87                         neighbors.remove(map.get(u));
    88                         it = neighbors.iterator();
    89                         while(it.hasNext()) {
    90                                 int v = it.next();
    91                                 output.addNode(v);
    92                                 output.addEdgeUndirected(map.get(u), v, 0);
    93                         }
    94                 }       
    95                 //calcolo dei pesi del nuovo grafo: per ogni arco (u,v) && u < v.
    96                 //w(map(u),map(v)) += w(u,v).
    97                 for(int u=0; u < g.size(); u++) {
    98                         Iterator<Integer> it = g.getNeighbors(u).iterator();
    99                         while(it.hasNext()) {
    100                                 int v = it.next();
    101                                 if(map.get(u) != map.get(v) && output.isEdge(map.get(u), map.get(v)) && u < v) {
    102                                         output.setWeight(map.get(u), map.get(v), output.getWeight(map.get(u), map.get(v)) + g.getWeight(u, v));
    103                                 }
    104                         }
     23        public void METIS(Graph g) {
     24                KLPartition partition = null;
     25                Stack<CoarserGraphElement> stack = Coarse.coarse(g);
     26               
     27                if(stack.size() > 0) {
     28                        partition = KL(stack.peek().getContracted());
     29                        System.out.println(partition.toString());
     30                        partition = new Uncoarse().uncoarse(stack, partition);
     31                        System.out.println(partition.toString());
    10532                }
    106                 for(int u = 0; u < g.size(); u++) {
    107                         if(isMatched(match,u)) {
    108                                 int v = match.get(u);
    109                                 if(u < v) {
    110                                         output.getNode(map.get(u)).vwgt = g.getNode(u).vwgt + g.getNode(v).vwgt;
    111                                         output.getNode(map.get(u)).cewgt = g.getNode(u).cewgt + g.getNode(v).cewgt +
    112                                         g.getWeight(u, v);
    113                                         output.getNode(map.get(u)).adjwgt = g.getNode(u).adjwgt + g.getNode(v).adjwgt - 2 *
    114                                         g.getWeight(u, v);
    115                                 }
    116                         } else {
    117                                 output.getNode(map.get(u)).vwgt = g.getNode(u).vwgt;
    118                                 output.getNode(map.get(u)).cewgt = g.getNode(u).cewgt;
    119                                 output.getNode(map.get(u)).adjwgt = g.getNode(u).adjwgt;
    120                         }
    121                 }
    122                 return output;
    123         }
    124 
    125         /**
    126          * Performs the first stage of the METIS algorithm, using RM.
    127          */
    128         private CoarserGraphElement coarseOneStep(Graph g) {
    129                 List<Integer> match = new ArrayList<Integer>();
    130                 List<Integer> map = new ArrayList<Integer>();
    131                 RMMatch(g,match,map);
    132                 g = contract(g,match,map);
    133                 return new CoarserGraphElement(g, match, map);
    134         }
    135        
    136         public void coarse(Graph g) {
    137                 int n = 1;
    138                 Graph prev = g;
    139                 CoarserGraphElement e;
    140                 g.printGraph(System.out);
    141             do {
    142                 e = coarseOneStep(g);
    143                 prev = g;
    144                 g = e.getGraph();
    145                 g.printGraph(System.out);
    146             } while(prev.size() > g.size() && g.size() > n);
     33               
    14734        }
    14835
Note: See TracChangeset for help on using the changeset viewer.