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.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • 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.