Changeset 10 for src/main/java
- Timestamp:
- Sep 14, 2010, 5:27:28 PM (14 years ago)
- Location:
- src/main/java/weka/clusterers/forMetisMQI
- Files:
-
- 7 edited
Legend:
- Unmodified
- Added
- Removed
-
src/main/java/weka/clusterers/forMetisMQI/Coarse.java
r9 r10 13 13 public class Coarse { 14 14 15 private static boolean debug = true;15 private static boolean debug = false; 16 16 private static PrintStream debugStream = System.err; 17 17 private static int finerSize = 5; … … 98 98 while(it.hasNext()) 99 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 100 neighbors.remove(getMappedNode(map,u)); 112 101 it = neighbors.iterator(); … … 127 116 Pair<Node> srcDst = g.getEndpoints(oldEdge); 128 117 Node src = srcDst.getFirst(); 129 Node dst = srcDst.get First();118 Node dst = srcDst.getSecond(); 130 119 Node srcMapped = getMappedNode(map, src); 131 120 Node dstMapped = getMappedNode(map, dst); … … 135 124 } 136 125 } 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 126 iterator = g.getVertices().iterator(); 152 127 Set<Node> nodesComplete = new HashSet<Node>(); … … 158 133 getMappedNode(map,u).setVwgt(u.getVwgt() + v.getVwgt()); 159 134 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 135 nodesComplete.add(u); 162 136 nodesComplete.add(v); … … 165 139 getMappedNode(map,u).setVwgt(u.getVwgt()); 166 140 getMappedNode(map,u).setCewgt(u.getCewgt()); 167 getMappedNode(map,u).setAdjwgt(u.getAdjwgt());168 141 } 169 142 } … … 174 147 * Performs the first stage of the METIS algorithm, using RM. 175 148 */ 176 p ublicstatic CoarserGraphElement coarseOneStep(UndirectedGraph g) {149 private static CoarserGraphElement coarseOneStep(UndirectedGraph g) { 177 150 UndirectedGraph projected = g; 178 151 UndirectedGraph contracted = null; … … 183 156 return new CoarserGraphElement(contracted, projected, match, map); 184 157 } 158 185 159 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 */ 186 166 public static Stack<CoarserGraphElement> coarse(UndirectedGraph g) { 187 167 Stack<CoarserGraphElement> stack = new Stack<CoarserGraphElement>(); 188 CoarserGraphElement e ;168 CoarserGraphElement e = null; 189 169 UndirectedGraph curr = g; 170 int i = 0; 171 190 172 do { 191 173 if(debug) 192 debugStream.println("-------- ---------------------------------------------");174 debugStream.println("--------CONTRACTION-nr" + i +"------------------------------"); 193 175 e = coarseOneStep(curr); 194 176 stack.push(e); 195 177 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++; 198 185 } while(e.getProjected().getVertexCount() > e.getContracted().getVertexCount() && e.getContracted().getVertexCount() > finerSize); 199 186 return stack; -
src/main/java/weka/clusterers/forMetisMQI/Edge.java
r9 r10 48 48 @Override 49 49 public String toString() { 50 return "E" + id ;50 return "E" + id + " w:" + weight; 51 51 } 52 52 -
src/main/java/weka/clusterers/forMetisMQI/GraphAlgorithms.java
r9 r10 23 23 public void METIS(UndirectedGraph g) { 24 24 KLPartition partition = null; 25 Coarse.setFinerSize( 10);25 Coarse.setFinerSize(8); 26 26 Stack<CoarserGraphElement> stack = Coarse.coarse(g); 27 27 -
src/main/java/weka/clusterers/forMetisMQI/KLPartition.java
r9 r10 95 95 public int edgeCut() { 96 96 int acc = a.getExternalDegree() + b.getExternalDegree(); 97 return (int)Math.round(0.5 * acc);97 return acc; 98 98 } 99 99 -
src/main/java/weka/clusterers/forMetisMQI/MQI.java
r9 r10 23 23 vv.setPreferredSize(new Dimension(350,350)); //Sets the viewing area size 24 24 vv.getRenderContext().setVertexLabelTransformer(new ToStringLabeller<Node>()); 25 vv.getRenderContext().setEdgeLabelTransformer(new ToStringLabeller<Edge>()); 26 25 27 JFrame frame = new JFrame("Simple Graph View"); 26 28 frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); … … 90 92 } 91 93 92 viewGraph(g);94 // viewGraph(g); 93 95 System.out.println(g.toString()); 94 96 -
src/main/java/weka/clusterers/forMetisMQI/Node.java
r9 r10 8 8 /** The weight of the node */ 9 9 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 adjacency14 * list of v15 */16 private int iedges;17 10 /** The weight of the edges that have been contracted to create the node */ 18 11 private int cewgt; 19 /** The sum of the weight of the edges adjacent to v */20 private int adjwgt;21 22 12 public Node(String id) { 23 13 this.id = id; 24 14 this.vwgt = 1; 25 15 this.cewgt = 0; 26 this.iedges = 0;27 this.nedges = 0;28 this.adjwgt = 0;29 16 } 30 17 … … 47 34 @Override 48 35 public String toString() { 49 return "N" + id; 36 return "N" + id; //+ " Cewgt: " + cewgt; 50 37 } 51 38 … … 58 45 } 59 46 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 76 47 public int getCewgt() { 77 48 return cewgt; … … 82 53 } 83 54 84 public int getAdjwgt() {85 return adjwgt;86 }87 88 public void setAdjwgt(int adjwgt) {89 this.adjwgt = adjwgt;90 }91 92 55 @Override 93 56 public Node clone() { 94 57 Node n = new Node(id); 95 n.adjwgt = adjwgt;96 58 n.cewgt = cewgt; 97 n.iedges = iedges;98 n.nedges = nedges;99 59 n.vwgt = vwgt; 100 60 return n; -
src/main/java/weka/clusterers/forMetisMQI/UndirectedGraph.java
r9 r10 10 10 import weka.core.Instances; 11 11 import edu.uci.ics.jung.graph.UndirectedSparseGraph; 12 import edu.uci.ics.jung.graph.util.Pair; 12 13 13 14 public class UndirectedGraph extends UndirectedSparseGraph<Node, Edge> { … … 94 95 g.addEdge(e.clone(), getEndpoints(e)); 95 96 } 96 97 98 97 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(); 99 123 } 100 124
Note: See TracChangeset
for help on using the changeset viewer.