Index: src/main/java/weka/clusterers/forMetisMQI/Coarse.java =================================================================== --- src/main/java/weka/clusterers/forMetisMQI/Coarse.java (revision 9) +++ src/main/java/weka/clusterers/forMetisMQI/Coarse.java (revision 10) @@ -13,5 +13,5 @@ public class Coarse { - private static boolean debug = true; + private static boolean debug = false; private static PrintStream debugStream = System.err; private static int finerSize = 5; @@ -98,15 +98,4 @@ while(it.hasNext()) neighbors.add(getMappedNode(map, it.next())); - -// Set neighbors = new HashSet(); -// while(it.hasNext()) { -// Node v = it.next(); -// neighbors.add(getMappedNode(map,v)); -// } -// it = g.getNeighbors(getMappedNode(match,u)).iterator(); -// while(it.hasNext()) { -// Node v = it.next(); -// neighbors.add(getMappedNode(map,v)); -// } neighbors.remove(getMappedNode(map,u)); it = neighbors.iterator(); @@ -127,5 +116,5 @@ Pair srcDst = g.getEndpoints(oldEdge); Node src = srcDst.getFirst(); - Node dst = srcDst.getFirst(); + Node dst = srcDst.getSecond(); Node srcMapped = getMappedNode(map, src); Node dstMapped = getMappedNode(map, dst); @@ -135,18 +124,4 @@ } } - - -// for(int i=0; i < g.size(); i++) { -// int u = g.getLabel(i); -// Iterator it = g.getNeighbors(u).iterator(); -// while(it.hasNext()) { -// int v = it.next(); -// if(getMappedNode(g,map,u) != getMappedNode(g,map,v) && output.isEdge(getMappedNode(g,map,u), getMappedNode(g,map,v)) && u < v) { -// output.setWeight(getMappedNode(g,map,u), getMappedNode(g,map,v), output.getWeight(getMappedNode(g,map,u), getMappedNode(g,map,v)) + g.getWeight(u, v)); -// } -// } -// } - - iterator = g.getVertices().iterator(); Set nodesComplete = new HashSet(); @@ -158,5 +133,4 @@ getMappedNode(map,u).setVwgt(u.getVwgt() + v.getVwgt()); getMappedNode(map,u).setCewgt(u.getCewgt() + v.getCewgt() + g.findEdge(u, v).getWeight()); - getMappedNode(map,u).setAdjwgt(u.getAdjwgt() + v.getAdjwgt() - 2 * g.findEdge(u, v).getWeight()); nodesComplete.add(u); nodesComplete.add(v); @@ -165,5 +139,4 @@ getMappedNode(map,u).setVwgt(u.getVwgt()); getMappedNode(map,u).setCewgt(u.getCewgt()); - getMappedNode(map,u).setAdjwgt(u.getAdjwgt()); } } @@ -174,5 +147,5 @@ * Performs the first stage of the METIS algorithm, using RM. */ - public static CoarserGraphElement coarseOneStep(UndirectedGraph g) { + private static CoarserGraphElement coarseOneStep(UndirectedGraph g) { UndirectedGraph projected = g; UndirectedGraph contracted = null; @@ -183,17 +156,31 @@ return new CoarserGraphElement(contracted, projected, match, map); } + + /** + * Performs at least one contraction of the given the graph, and goes on until the graph + * is under the desidered size (see setFinerSize()). + * @param g + * @return the stack of contracted graphs + */ public static Stack coarse(UndirectedGraph g) { Stack stack = new Stack(); - CoarserGraphElement e; + CoarserGraphElement e = null; UndirectedGraph curr = g; + int i = 0; + do { if(debug) - debugStream.println("-----------------------------------------------------"); + debugStream.println("--------CONTRACTION-nr" + i +"------------------------------"); e = coarseOneStep(curr); stack.push(e); curr = e.getContracted(); - if(debug) - debugStream.println("-----------------------------------------------------"); + if(debug) { + debugStream.println("-----------EXPANDED----------------------------------"); + debugStream.println(e.getProjected().toString()); + debugStream.println("-----------CONTRACTED--------------------------------"); + debugStream.println(e.getContracted().toString()); + } + i++; } while(e.getProjected().getVertexCount() > e.getContracted().getVertexCount() && e.getContracted().getVertexCount() > finerSize); return stack; Index: src/main/java/weka/clusterers/forMetisMQI/Edge.java =================================================================== --- src/main/java/weka/clusterers/forMetisMQI/Edge.java (revision 9) +++ src/main/java/weka/clusterers/forMetisMQI/Edge.java (revision 10) @@ -48,5 +48,5 @@ @Override public String toString() { - return "E" + id; + return "E" + id + " w:" + weight; } Index: src/main/java/weka/clusterers/forMetisMQI/GraphAlgorithms.java =================================================================== --- src/main/java/weka/clusterers/forMetisMQI/GraphAlgorithms.java (revision 9) +++ src/main/java/weka/clusterers/forMetisMQI/GraphAlgorithms.java (revision 10) @@ -23,5 +23,5 @@ public void METIS(UndirectedGraph g) { KLPartition partition = null; - Coarse.setFinerSize(10); + Coarse.setFinerSize(8); Stack stack = Coarse.coarse(g); Index: src/main/java/weka/clusterers/forMetisMQI/KLPartition.java =================================================================== --- src/main/java/weka/clusterers/forMetisMQI/KLPartition.java (revision 9) +++ src/main/java/weka/clusterers/forMetisMQI/KLPartition.java (revision 10) @@ -95,5 +95,5 @@ public int edgeCut() { int acc = a.getExternalDegree() + b.getExternalDegree(); - return (int)Math.round(0.5 * acc); + return acc; } Index: src/main/java/weka/clusterers/forMetisMQI/MQI.java =================================================================== --- src/main/java/weka/clusterers/forMetisMQI/MQI.java (revision 9) +++ src/main/java/weka/clusterers/forMetisMQI/MQI.java (revision 10) @@ -23,4 +23,6 @@ vv.setPreferredSize(new Dimension(350,350)); //Sets the viewing area size vv.getRenderContext().setVertexLabelTransformer(new ToStringLabeller()); + vv.getRenderContext().setEdgeLabelTransformer(new ToStringLabeller()); + JFrame frame = new JFrame("Simple Graph View"); frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); @@ -90,5 +92,5 @@ } - viewGraph(g); +// viewGraph(g); System.out.println(g.toString()); Index: src/main/java/weka/clusterers/forMetisMQI/Node.java =================================================================== --- src/main/java/weka/clusterers/forMetisMQI/Node.java (revision 9) +++ src/main/java/weka/clusterers/forMetisMQI/Node.java (revision 10) @@ -8,23 +8,10 @@ /** The weight of the node */ private int vwgt; - /** The size of the adjacency list of the node */ - private int nedges; - /** - * The index into the adjacency list that is the beginning of the adjacency - * list of v - */ - private int iedges; /** The weight of the edges that have been contracted to create the node */ private int cewgt; - /** The sum of the weight of the edges adjacent to v */ - private int adjwgt; - public Node(String id) { this.id = id; this.vwgt = 1; this.cewgt = 0; - this.iedges = 0; - this.nedges = 0; - this.adjwgt = 0; } @@ -47,5 +34,5 @@ @Override public String toString() { - return "N" + id; + return "N" + id; //+ " Cewgt: " + cewgt; } @@ -58,20 +45,4 @@ } - public int getNedges() { - return nedges; - } - - public void setNedges(int nedges) { - this.nedges = nedges; - } - - public int getIedges() { - return iedges; - } - - public void setIedges(int iedges) { - this.iedges = iedges; - } - public int getCewgt() { return cewgt; @@ -82,19 +53,8 @@ } - public int getAdjwgt() { - return adjwgt; - } - - public void setAdjwgt(int adjwgt) { - this.adjwgt = adjwgt; - } - @Override public Node clone() { Node n = new Node(id); - n.adjwgt = adjwgt; n.cewgt = cewgt; - n.iedges = iedges; - n.nedges = nedges; n.vwgt = vwgt; return n; Index: src/main/java/weka/clusterers/forMetisMQI/UndirectedGraph.java =================================================================== --- src/main/java/weka/clusterers/forMetisMQI/UndirectedGraph.java (revision 9) +++ src/main/java/weka/clusterers/forMetisMQI/UndirectedGraph.java (revision 10) @@ -10,4 +10,5 @@ import weka.core.Instances; import edu.uci.ics.jung.graph.UndirectedSparseGraph; +import edu.uci.ics.jung.graph.util.Pair; public class UndirectedGraph extends UndirectedSparseGraph { @@ -94,7 +95,30 @@ g.addEdge(e.clone(), getEndpoints(e)); } - - return g; + } + + public int getAdjcncyWeight(Node v1){ + Iterator nbsIterator = getNeighbors(v1).iterator(); + int adjcncyWgt = 0; + while(nbsIterator.hasNext()) { + Node v2 = nbsIterator.next(); + Edge edge = findEdge(v1, v2); + adjcncyWgt += edge.getWeight(); + } + return adjcncyWgt; + } + + public String toString() { + StringBuffer sb = new StringBuffer("Vertices:"); + for(Node v : getVertices()) { + sb.append(v+ " Adjw: "+ getAdjcncyWeight(v) + ","); + } + sb.setLength(sb.length()-1); + sb.append("\nEdges:"); + for(Edge e : getEdges()) { + Pair ep = getEndpoints(e); + sb.append(e+"["+ep.getFirst()+","+ep.getSecond()+"] "); + } + return sb.toString(); }