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

Corretti alcuni bachi inseriti con la migrazione a Jung.

Location:
src/main/java/weka/clusterers/forMetisMQI
Files:
7 edited

Legend:

Unmodified
Added
Removed

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

    r9 r10  
    1313public class Coarse {
    1414       
    15         private static boolean debug = true;
     15        private static boolean debug = false;
    1616        private static PrintStream debugStream = System.err;
    1717        private static int finerSize = 5;
    … …  
    9898                        while(it.hasNext())
    9999                                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 //                      }
    111100                        neighbors.remove(getMappedNode(map,u));
    112101                        it = neighbors.iterator();
    … …  
    127116                        Pair<Node> srcDst = g.getEndpoints(oldEdge);
    128117                        Node src = srcDst.getFirst();
    129                         Node dst = srcDst.getFirst();
     118                        Node dst = srcDst.getSecond();
    130119                        Node srcMapped = getMappedNode(map, src);
    131120                        Node dstMapped = getMappedNode(map, dst);
    … …  
    135124                        }
    136125                }
    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                
    151126                iterator = g.getVertices().iterator();
    152127                Set<Node> nodesComplete = new HashSet<Node>();
    … …  
    158133                                        getMappedNode(map,u).setVwgt(u.getVwgt() + v.getVwgt());
    159134                                        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());
    161135                                        nodesComplete.add(u);
    162136                                        nodesComplete.add(v);
    … …  
    165139                                getMappedNode(map,u).setVwgt(u.getVwgt());
    166140                                getMappedNode(map,u).setCewgt(u.getCewgt());
    167                                 getMappedNode(map,u).setAdjwgt(u.getAdjwgt());
    168141                        }
    169142                }
    … …  
    174147         * Performs the first stage of the METIS algorithm, using RM.
    175148         */
    176         public static CoarserGraphElement coarseOneStep(UndirectedGraph g) {
     149        private static CoarserGraphElement coarseOneStep(UndirectedGraph g) {
    177150                UndirectedGraph projected = g;
    178151                UndirectedGraph contracted = null;
    … …  
    183156                return new CoarserGraphElement(contracted, projected, match, map);
    184157        }
     158
    185159       
     160        /**
     161         * Performs at least one contraction of the given the graph, and goes on until the graph
     162         * is under the desidered size (see setFinerSize()).
     163         * @param g
     164         * @return the stack of contracted graphs
     165         */
    186166        public static Stack<CoarserGraphElement> coarse(UndirectedGraph g) {
    187167                Stack<CoarserGraphElement> stack = new Stack<CoarserGraphElement>();
    188                 CoarserGraphElement e;
     168                CoarserGraphElement e = null;
    189169                UndirectedGraph curr = g;
     170                int i = 0;
     171               
    190172            do {
    191173                if(debug)
    192                         debugStream.println("-----------------------------------------------------");
     174                        debugStream.println("--------CONTRACTION-nr" + i +"------------------------------");
    193175                e = coarseOneStep(curr);
    194176                stack.push(e);
    195177                curr = e.getContracted();
    196                 if(debug)
    197                         debugStream.println("-----------------------------------------------------");
     178                if(debug) {
     179                        debugStream.println("-----------EXPANDED----------------------------------");
     180                        debugStream.println(e.getProjected().toString());
     181                        debugStream.println("-----------CONTRACTED--------------------------------");
     182                        debugStream.println(e.getContracted().toString());
     183                }
     184                i++;
    198185            } while(e.getProjected().getVertexCount() > e.getContracted().getVertexCount() && e.getContracted().getVertexCount() > finerSize);
    199186            return stack;

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

    r9 r10  
    4848        @Override
    4949        public String toString() {
    50                 return "E" + id;
     50                return "E" + id + " w:" + weight;
    5151        }
    5252

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

    r9 r10  
    2323        public void METIS(UndirectedGraph g) {
    2424                KLPartition partition = null;
    25                 Coarse.setFinerSize(10);
     25                Coarse.setFinerSize(8);
    2626                Stack<CoarserGraphElement> stack = Coarse.coarse(g);
    2727               

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

    r9 r10  
    9595        public int edgeCut() {
    9696                int acc = a.getExternalDegree() + b.getExternalDegree();
    97                 return (int)Math.round(0.5 * acc);
     97                return acc;
    9898        }
    9999       

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

    r9 r10  
    2323                vv.setPreferredSize(new Dimension(350,350)); //Sets the viewing area size
    2424                vv.getRenderContext().setVertexLabelTransformer(new ToStringLabeller<Node>());
     25                vv.getRenderContext().setEdgeLabelTransformer(new ToStringLabeller<Edge>());
     26
    2527                JFrame frame = new JFrame("Simple Graph View");
    2628                frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    … …  
    9092                }
    9193               
    92                 viewGraph(g);
     94//              viewGraph(g);
    9395                System.out.println(g.toString());
    9496               

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

    r9 r10  
    88        /** The weight of the node */
    99        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;
    1710        /** The weight of the edges that have been contracted to create the node */
    1811        private int cewgt;
    19         /** The sum of the weight of the edges adjacent to v */
    20         private int adjwgt;
    21 
    2212        public Node(String id) {
    2313                this.id = id;
    2414                this.vwgt = 1;
    2515                this.cewgt = 0;
    26                 this.iedges = 0;
    27                 this.nedges = 0;
    28                 this.adjwgt = 0;
    2916        }
    3017
    … …  
    4734        @Override
    4835        public String toString() {
    49                 return "N" + id;
     36                return "N" + id; //+ " Cewgt: " + cewgt;
    5037        }
    5138
    … …  
    5845        }
    5946
    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 
    7647        public int getCewgt() {
    7748                return cewgt;
    … …  
    8253        }
    8354
    84         public int getAdjwgt() {
    85                 return adjwgt;
    86         }
    87 
    88         public void setAdjwgt(int adjwgt) {
    89                 this.adjwgt = adjwgt;
    90         }
    91        
    9255        @Override
    9356        public Node clone() {
    9457                Node n = new Node(id);
    95                 n.adjwgt = adjwgt;
    9658                n.cewgt = cewgt;
    97                 n.iedges = iedges;
    98                 n.nedges = nedges;
    9959                n.vwgt = vwgt;
    10060                return n;

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

    r9 r10  
    1010import weka.core.Instances;
    1111import edu.uci.ics.jung.graph.UndirectedSparseGraph;
     12import edu.uci.ics.jung.graph.util.Pair;
    1213
    1314public class UndirectedGraph extends UndirectedSparseGraph<Node, Edge> {
    … …  
    9495                        g.addEdge(e.clone(), getEndpoints(e));
    9596                }
    96                
    97                
    9897                return g;
     98        }
     99       
     100        public int getAdjcncyWeight(Node v1){
     101                Iterator<Node> nbsIterator = getNeighbors(v1).iterator();
     102                int adjcncyWgt = 0;
     103                while(nbsIterator.hasNext()) {
     104                        Node v2 = nbsIterator.next();
     105                        Edge edge = findEdge(v1, v2);
     106                        adjcncyWgt += edge.getWeight();
     107                }
     108                return adjcncyWgt;
     109        }
     110       
     111        public String toString() {
     112                StringBuffer sb = new StringBuffer("Vertices:");
     113        for(Node v : getVertices()) {
     114                sb.append(v+ " Adjw: "+ getAdjcncyWeight(v) + ",");
     115        }
     116        sb.setLength(sb.length()-1);
     117        sb.append("\nEdges:");
     118        for(Edge e : getEdges()) {
     119                Pair<Node> ep = getEndpoints(e);
     120                sb.append(e+"["+ep.getFirst()+","+ep.getSecond()+"] ");
     121        }
     122        return sb.toString();
    99123        }
    100124
Note: See TracChangeset for help on using the changeset viewer.