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