Index: src/main/java/weka/clusterers/SimpleClusterer.java =================================================================== --- src/main/java/weka/clusterers/SimpleClusterer.java (revision 8) +++ src/main/java/weka/clusterers/SimpleClusterer.java (revision 9) @@ -2,6 +2,6 @@ -import weka.clusterers.forMetisMQI.Graph; import weka.clusterers.forMetisMQI.GraphAlgorithms; +import weka.clusterers.forMetisMQI.UndirectedGraph; import weka.core.Capabilities; import weka.core.Instance; @@ -22,5 +22,6 @@ getCapabilities().testWithFail(data); - Graph g = new Graph(data); + UndirectedGraph g = new UndirectedGraph(); + g.loadFromInstance(data); GraphAlgorithms ga = new GraphAlgorithms(); ga.METIS(g); Index: src/main/java/weka/clusterers/forMetisMQI/Coarse.java =================================================================== --- src/main/java/weka/clusterers/forMetisMQI/Coarse.java (revision 8) +++ src/main/java/weka/clusterers/forMetisMQI/Coarse.java (revision 9) @@ -2,10 +2,12 @@ import java.io.PrintStream; -import java.util.ArrayList; +import java.util.HashMap; import java.util.HashSet; import java.util.Iterator; -import java.util.List; +import java.util.Map; import java.util.Set; import java.util.Stack; + +import edu.uci.ics.jung.graph.util.Pair; public class Coarse { @@ -23,27 +25,25 @@ * @return true if the vertex v is matched, false o.w. */ - private static boolean isMatched(Graph g, List match, int v) { - return match.get(g.getIndex(v)) != g.getIndex(v); - } - - private static void RMMatch(Graph g, List match, List map) { + private static boolean isMatched(Map match, Node v) { + if(match.containsKey(v)) + return !match.get(v).equals(v); + else + return false; + } + + private static void RMMatch(UndirectedGraph g, Map match, Map map) { int labelCounter = 0; - for (int i = 0; i < g.size(); i++) { - match.add(i); - map.add(i); - } - g.adjncyPermutation(); - Iterator nodeIterator = g.vtxsPermutation().iterator(); + Iterator nodeIterator = g.vtxsPermutation().iterator(); while (nodeIterator.hasNext()) { - int u = nodeIterator.next(); + Node u = nodeIterator.next(); if (debug) - debugStream.println("Visiting node " + u + " Matched = " + isMatched(g,match,u)); - if (!isMatched(g,match,u)) { + debugStream.println("Visiting node " + u + " Matched = " + isMatched(match,u)); + if (!isMatched(match,u)) { boolean foundMatch = false; - int matchedNode = -1; - Iterator iterator = g.getNeighbors(u).iterator(); + Node matchedNode = null; + Iterator iterator = g.getNeighborsPermutation(u).iterator(); while(iterator.hasNext() && !foundMatch){ - int v = iterator.next(); - if (!isMatched(g,match,v)) { + Node v = iterator.next(); + if (!isMatched(match,v)) { matchedNode = v; foundMatch = true; @@ -55,13 +55,15 @@ if (debug && !foundMatch) debugStream.println("There aren't unmatched neighbors."); + Node newNode = new Node(Integer.toString(labelCounter)); if(foundMatch) { - match.set(g.getIndex(u), g.getIndex(matchedNode)); - match.set(g.getIndex(matchedNode), g.getIndex(u)); - map.set(g.getIndex(u), labelCounter); - map.set(g.getIndex(matchedNode), labelCounter); - if(debug) debugStream.println("Contracting node " + u + " with " + matchedNode + ". Node id: " + getMappedNode(g, map, u)); + match.put(u, matchedNode); + match.put(matchedNode, u); + map.put(u, newNode); + map.put(matchedNode, newNode); + if(debug) debugStream.println("Contracting node " + u + " with " + matchedNode + ". Node id: " + getMappedNode(map, u)); } else { - map.set(g.getIndex(u), labelCounter); - if(debug) debugStream.println("Node " + u + " with " + " new node id: " + getMappedNode(g, map, u)); + match.put(u, u); + map.put(u, newNode); + if(debug) debugStream.println("Node " + u + " with " + " new node id: " + getMappedNode(map, u)); } labelCounter++; @@ -70,10 +72,10 @@ } - private static int getMatchedNode(Graph g, List match, int u) { - return g.getLabel(match.get(g.getIndex(u))); - } - - private static int getMappedNode(Graph g, List map, int u) { - return map.get(g.getIndex(u)); + private static Node getMatchedNode(Map match, Node u) { + return match.get(u); + } + + private static Node getMappedNode(Map map, Node u) { + return map.get(u); } @@ -81,56 +83,87 @@ * Return a new contracted graph. */ - private static Graph contract(Graph g, List match, List map) { - Graph output = new Graph(); - Iterator iterator = g.iterator(); + private static UndirectedGraph contract(UndirectedGraph g, Map match, Map map) { + UndirectedGraph output = new UndirectedGraph(); + Iterator iterator = g.getVertices().iterator(); + int i = 0; while(iterator.hasNext()) { - int u = iterator.next(); - output.addNode(getMappedNode(g,map,u)); - Iterator it = g.getNeighbors(u).iterator(); - Set neighbors = new HashSet(); - while(it.hasNext()) { - int v = it.next(); - neighbors.add(getMappedNode(g,map,v)); - } - it = g.getNeighbors(getMatchedNode(g,match,u)).iterator(); - while(it.hasNext()) { - int v = it.next(); - neighbors.add(getMappedNode(g,map,v)); - } - neighbors.remove(getMappedNode(g,map,u)); + Node u = iterator.next(); + output.addVertex(getMappedNode(map,u)); + + Set neighbors = new HashSet(); + Iterator it = g.getNeighbors(u).iterator(); + while(it.hasNext()) + neighbors.add(getMappedNode(map, it.next())); + it = g.getNeighbors(getMatchedNode(match, u)).iterator(); + 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(); while(it.hasNext()) { - int v = it.next(); - output.addNode(v); - output.addEdgeUndirected(getMappedNode(g,map,u), v, 0); - } - } + Node v = it.next(); + output.addVertex(v); + output.addEdge(new Edge(Integer.toString(i),0,0),getMappedNode(map,u), v); + i++; + } + } + //calcolo dei pesi del nuovo grafo: per ogni arco (u,v) && u < v. - //w(map(u),map(v)) += w(u,v). - 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)); - } - } - } - for(int i=0; i < g.size(); i++) { - int u = g.getLabel(i); - if(isMatched(g,match,u)) { - int v = getMatchedNode(g,match,u); - if(u < v) { - output.getNode(getMappedNode(g,map,u)).vwgt = g.getNode(u).vwgt + g.getNode(v).vwgt; - output.getNode(getMappedNode(g,map,u)).cewgt = g.getNode(u).cewgt + g.getNode(v).cewgt + - g.getWeight(u, v); - output.getNode(getMappedNode(g,map,u)).adjwgt = g.getNode(u).adjwgt + g.getNode(v).adjwgt - 2 * - g.getWeight(u, v); + //w(map(u),map(v)) += w(u,v). + + Iterator edgeIterator = g.getEdges().iterator(); + while(edgeIterator.hasNext()) { + Edge oldEdge = edgeIterator.next(); + Pair srcDst = g.getEndpoints(oldEdge); + Node src = srcDst.getFirst(); + Node dst = srcDst.getFirst(); + Node srcMapped = getMappedNode(map, src); + Node dstMapped = getMappedNode(map, dst); + if(!srcMapped.equals(dstMapped) && output.containsEdge(srcMapped, dstMapped)) { + Edge newEdge = output.findEdge(srcMapped, dstMapped); + newEdge.setWeight(newEdge.getWeight() + oldEdge.getWeight()); + } + } + + +// 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(); + while(iterator.hasNext()) { + Node u = iterator.next(); + if(isMatched(match,u)) { + Node v = getMatchedNode(match,u); + if(!nodesComplete.contains(u)) { + 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); } } else { - output.getNode(getMappedNode(g,map,u)).vwgt = g.getNode(u).vwgt; - output.getNode(getMappedNode(g,map,u)).cewgt = g.getNode(u).cewgt; - output.getNode(getMappedNode(g,map,u)).adjwgt = g.getNode(u).adjwgt; + getMappedNode(map,u).setVwgt(u.getVwgt()); + getMappedNode(map,u).setCewgt(u.getCewgt()); + getMappedNode(map,u).setAdjwgt(u.getAdjwgt()); } } @@ -141,9 +174,9 @@ * Performs the first stage of the METIS algorithm, using RM. */ - public static CoarserGraphElement coarseOneStep(Graph g) { - Graph projected = g; - Graph contracted = null; - List match = new ArrayList(); - List map = new ArrayList(); + public static CoarserGraphElement coarseOneStep(UndirectedGraph g) { + UndirectedGraph projected = g; + UndirectedGraph contracted = null; + Map match = new HashMap(); + Map map = new HashMap(); RMMatch(g,match,map); contracted = contract(g,match,map); @@ -151,8 +184,8 @@ } - public static Stack coarse(Graph g) { + public static Stack coarse(UndirectedGraph g) { Stack stack = new Stack(); CoarserGraphElement e; - Graph curr = g; + UndirectedGraph curr = g; do { if(debug) @@ -163,5 +196,5 @@ if(debug) debugStream.println("-----------------------------------------------------"); - } while(e.getProjected().size() > e.getContracted().size() && e.getContracted().size() > finerSize); + } while(e.getProjected().getVertexCount() > e.getContracted().getVertexCount() && e.getContracted().getVertexCount() > finerSize); return stack; } Index: src/main/java/weka/clusterers/forMetisMQI/CoarserGraphElement.java =================================================================== --- src/main/java/weka/clusterers/forMetisMQI/CoarserGraphElement.java (revision 8) +++ src/main/java/weka/clusterers/forMetisMQI/CoarserGraphElement.java (revision 9) @@ -1,14 +1,14 @@ package weka.clusterers.forMetisMQI; -import java.util.List; +import java.util.Map; public class CoarserGraphElement { - private Graph contracted; - private Graph projected; - private List match; - private List map; + private UndirectedGraph contracted; + private UndirectedGraph projected; + private Map match; + private Map map; - public CoarserGraphElement(Graph contracted, Graph projected, List match, List map) { + public CoarserGraphElement(UndirectedGraph contracted, UndirectedGraph projected, Map match, Map map) { this.contracted = contracted; this.projected = projected; @@ -17,17 +17,17 @@ } - public List getMatch() { + public Map getMatch() { return match; } - public List getMap() { + public Map getMap() { return map; } - public Graph getContracted() { + public UndirectedGraph getContracted() { return contracted; } - public Graph getProjected() { + public UndirectedGraph getProjected() { return projected; } Index: src/main/java/weka/clusterers/forMetisMQI/Edge.java =================================================================== --- src/main/java/weka/clusterers/forMetisMQI/Edge.java (revision 8) +++ src/main/java/weka/clusterers/forMetisMQI/Edge.java (revision 9) @@ -51,3 +51,17 @@ } + public void setWeight(int weight) { + this.weight = weight; + } + + public void setCapacity(int capacity) { + this.capacity = capacity; + } + + @Override + public Edge clone(){ + Edge e = new Edge(id, weight, capacity); + return e; + } + } Index: src/main/java/weka/clusterers/forMetisMQI/Graph.java =================================================================== --- src/main/java/weka/clusterers/forMetisMQI/Graph.java (revision 8) +++ (revision ) @@ -1,358 +1,0 @@ -package weka.clusterers.forMetisMQI; - -import java.io.PrintStream; -import java.util.ArrayList; -import java.util.HashMap; -import java.util.Iterator; -import java.util.List; -import java.util.Map.Entry; - -import weka.core.Attribute; -import weka.core.Instance; -import weka.core.Instances; - -public class Graph { - - protected static class NodeInfo { - /** The weight of the node */ - protected int vwgt; - /** The size of the adjacency list of the node */ - protected int nedges; - /** - * The index into the adjacency list that is the beginning of the - * adjacency list of v - */ - protected int iedges; - /** The weight of the edges that have been contracted to create the node */ - protected int cewgt; - /** The sum of the weight of the edges adjacent to v */ - protected int adjwgt; - - public NodeInfo() { - this.vwgt = 1; - this.cewgt = 0; - this.iedges = 0; - this.nedges = 0; - this.adjwgt = 0; - - } - - @Override - public String toString() { - return "Vwgt: " + vwgt + " Cewgt: " + cewgt + " Iedges: " + iedges - + " Nedges: " + nedges + " Adjwgt: " + adjwgt; - } - - @Override - public NodeInfo clone() { - NodeInfo ni = new NodeInfo(); - ni.adjwgt = adjwgt; - ni.cewgt = cewgt; - ni.iedges = iedges; - ni.nedges = nedges; - ni.vwgt = vwgt; - return ni; - } - } - - /** - * Additional node info for all vertices.. - */ - private List vtxs; - /** - * Adjacency vector. - */ - private List adjncy; - /** - * Weights vector - */ - private List weights; - - private HashMap label; - private HashMap index; - - /** - * Build a new graph given a set of instances. - * - * @param data - */ - public Graph(Instances data) { - vtxs = new ArrayList(); - adjncy = new ArrayList(); - weights = new ArrayList(); - label = new HashMap(); - index = new HashMap(); - Iterator dataIterator = data.iterator(); - Attribute from = data.attribute("from"); - Attribute to = data.attribute("to"); - if (from == null || to == null) - throw new RuntimeException( - "Unsupported data: check the list of attributes (from and to are needed)."); - while (dataIterator.hasNext()) { - Instance edge = dataIterator.next(); - int node1 = (int) Math.round(edge.value(from)); - int node2 = (int) Math.round(edge.value(to)); - addNode(node1); addNode(node2); - addEdgeUndirected(node1, node2, 1); - } - } - - public Graph() { - vtxs = new ArrayList(); - adjncy = new ArrayList(); - weights = new ArrayList(); - label = new HashMap(); - index = new HashMap(); - } - - /** - * Returns an iterator over the nodes of the graph. - * @return - */ - public Iterator iterator() { - return label.keySet().iterator(); - } - - /** - * Returns the label associated with a given index. - * @param index - * @return - */ - public int getLabel(int index) { - return this.index.get(index); - } - - /** - * Returns the index associated with a given label. - * @param index - * @return - */ - public int getIndex(int label) { - return this.label.get(label); - } - - private void updateAssociation(int index, int label) { - this.index.put(index,label); - this.label.put(label,index); - } - - /** - * Returns the weight of the edge (u,v). - * @param u - * @param v - * @return - */ - public int getWeight(int u, int v) { - int i = getIndex(u); - int istart = vtxs.get(i).iedges; - int iend = vtxs.get(i).iedges + vtxs.get(i).nedges; - int weight = -1; boolean found = false; - for(int k = istart; k < iend && !found; k++) { - if(adjncy.get(k) == v) { - weight = weights.get(k); - found = true; - } - } - return weight; - } - - public void setWeight(int u, int v, int weight) { - int i = getIndex(u); - int j = getIndex(v); - int istart = vtxs.get(i).iedges; - int iend = istart + vtxs.get(i).nedges; - for(int k = istart; k < iend; k++){ - if(adjncy.get(k) == v) { - weights.set(k, weight); - } - } - int jstart = vtxs.get(j).iedges; - int jend = jstart + vtxs.get(j).nedges; - for(int k = jstart; k < jend; k++){ - if(adjncy.get(k) == u) - weights.set(k, weight); - } - } - - public NodeInfo getNode(int u) { - int i = getIndex(u); - return vtxs.get(i); - } - - public int nedge() { - return adjncy.size(); - } - - public boolean isNode(int u) { - return label.containsKey(u); - } - - public void addNode(int u) { - if(!isNode(u)) { - int index = size(); - updateAssociation(index, u); - NodeInfo node = new NodeInfo(); - node.iedges = nedge(); - node.nedges = 0; - node.vwgt = 1; - node.adjwgt = 0; - node.cewgt = 0; - vtxs.add(index, node); - } - } - - public int size() { - return vtxs.size(); - } - - public List getNeighbors(int u) { - int i = getIndex(u); - List neighbors = new ArrayList(); - int istart = vtxs.get(i).iedges; - int iend = vtxs.get(i).iedges + vtxs.get(i).nedges; - for(int k = istart; k < iend; k++) { - neighbors.add(adjncy.get(k)); - } - return neighbors; - } - - /** - * Return true if u is neighbor of v. - * @param u - * @param v - * @return - */ - public boolean isNeighbor(int u, int v){ - return getNeighbors(u).contains(v); - } - - public void addEdgeUndirected(int i, int j, int w) { - addEdgeDirectedl(i, j, w); - addEdgeDirectedl(j, i, w); - } - - /** - * Add an edge from i to j of weight w if previously it doesn't exists, otherwise - * simply update the weight of the edge. - * @param i - * @param j - * @param w - */ - public void addEdgeDirectedl(int u, int v, int w) { - int i = getIndex(u); - if(!isNeighbor(u,v)) { - int istart = getNode(u).iedges; - adjncy.add(istart,v); - for(int k = i + 1; k < size(); k++) { - vtxs.get(k).iedges++; - } - vtxs.get(i).nedges++; - vtxs.get(i).adjwgt += w; - weights.add(istart, w); - } else - setWeight(u, v, w); - } - - public boolean isEdge(int u, int v) { - int i = getIndex(u); - int istart = vtxs.get(i).iedges; - int iend = vtxs.get(i).iedges + vtxs.get(i).nedges; - boolean found = false; - for(int k = istart; k < iend && !found; k++) { - found = (adjncy.get(k) == v); - } - return found; - } - - /** - * Print the graph structure. - */ - public void printGraph(PrintStream io) { - for(int i = 0; i < vtxs.size(); i++) { - int u = getLabel(i); - io.print("Node: " + u + " Neighbors: "); - Iterator neighbors = getNeighbors(u).iterator(); - while(neighbors.hasNext()) { - int v = neighbors.next(); - io.print(v + " [w: " + getWeight(u, v) + "] "); - } - io.println(getNode(u).toString()); - } - } - - /** - * Return a list containing a random permutation of the vertices. - * - * @return a random permutation of vertices - */ - public List vtxsPermutation() { - Random r = Random.instance(); - List perm = new ArrayList(); - for (int i = 0; i < vtxs.size(); i++) { - perm.add(getLabel(i)); - } - for (int i = 0; i < perm.size(); i++) { - int k = r.nextInt(perm.size()); - int swap = perm.get(k); - perm.set(k, perm.get(i)); - perm.set(i, swap); - } - return perm; - } - - /** - * Randomize the adjacency list. - */ - public void adjncyPermutation() { - Random r = Random.instance(); - for (int i = 0; i < vtxs.size(); i++) { - NodeInfo n = vtxs.get(i); - for (int j = n.iedges; j < n.nedges + n.iedges; j++) { - int k = r.nextInt(n.nedges) + n.iedges; - int swap = adjncy.get(k); - adjncy.set(k, adjncy.get(j)); - adjncy.set(j, swap); - swap = weights.get(k); - weights.set(k, weights.get(j)); - weights.set(j, swap); - } - } - } - - - @Override - public Graph clone() { - Graph g = new Graph(); - g.adjncy = new ArrayList(); - for(int i = 0; i < adjncy.size(); i++) { - g.adjncy.add(adjncy.get(i)); - } - - g.weights = new ArrayList(); - for(int i = 0; i < weights.size(); i++) { - g.weights.add(weights.get(i)); - } - - g.vtxs = new ArrayList(); - for(int i = 0; i < vtxs.size(); i++) { - g.vtxs.add(vtxs.get(i).clone()); - } - - g.index = new HashMap(); - Iterator> i = index.entrySet().iterator(); - while(i.hasNext()) { - Entry entry = i.next(); - g.index.put(entry.getKey(), entry.getValue()); - } - - g.label = new HashMap(); - i = label.entrySet().iterator(); - while(i.hasNext()) { - Entry entry = i.next(); - g.label.put(entry.getKey(), entry.getValue()); - } - - - return g; - } -} Index: src/main/java/weka/clusterers/forMetisMQI/GraphAlgorithms.java =================================================================== --- src/main/java/weka/clusterers/forMetisMQI/GraphAlgorithms.java (revision 8) +++ src/main/java/weka/clusterers/forMetisMQI/GraphAlgorithms.java (revision 9) @@ -5,14 +5,14 @@ public class GraphAlgorithms { - public KLPartition KL(Graph g) { + public KLPartition KL(UndirectedGraph g) { KLPartition partition = new KLPartition(g); KLPartition result = partition; int bestEdgeCut = Integer.MAX_VALUE; - int u = partition.getCandidate(); - while(u != -1) { + Node u = partition.getCandidate(); + while(u != null) { partition.swap(u); if(partition.edgeCut() <= bestEdgeCut) { bestEdgeCut = partition.edgeCut(); - result = partition.clone(); + result = partition.copy(); } u = partition.getCandidate(); @@ -21,5 +21,5 @@ } - public void METIS(Graph g) { + public void METIS(UndirectedGraph g) { KLPartition partition = null; Coarse.setFinerSize(10); Index: src/main/java/weka/clusterers/forMetisMQI/KLPartition.java =================================================================== --- src/main/java/weka/clusterers/forMetisMQI/KLPartition.java (revision 8) +++ src/main/java/weka/clusterers/forMetisMQI/KLPartition.java (revision 9) @@ -1,7 +1,7 @@ package weka.clusterers.forMetisMQI; -import java.util.ArrayList; +import java.util.HashSet; import java.util.Iterator; -import java.util.List; +import java.util.Set; @@ -12,5 +12,5 @@ private Subgraph b = null; - private List marked = null; + private Set marked = null; private KLPartition() { @@ -18,49 +18,49 @@ public KLPartition(Subgraph s) { - Graph g = s.getGraph(); + UndirectedGraph g = s.getGraph(); a = s; b = new Subgraph(g); - Iterator graphIterator = g.iterator(); + Iterator graphIterator = g.getVertices().iterator(); while(graphIterator.hasNext()) { - int u = graphIterator.next(); + Node u = graphIterator.next(); if(!s.contains(u)) - b.addNode(u); + b.addVertex(u); } - marked = new ArrayList(); + marked = new HashSet(); } - public KLPartition(Graph g){ + public KLPartition(UndirectedGraph g){ a = new Subgraph(g); b = new Subgraph(g); - Iterator graph = g.vtxsPermutation().iterator(); + Iterator graph = g.vtxsPermutation().iterator(); int i = 0; while(graph.hasNext()) { - int u = graph.next(); + Node u = graph.next(); if((i%2)==0) - a.addNode(u); + a.addVertex(u); else - b.addNode(u); + b.addVertex(u); i++; } - marked = new ArrayList(); + marked = new HashSet(); } /** - * Returns the node marked as candidate for swapping or -1 if there aren't node available + * Returns the node marked as candidate for swapping or null if there aren't node available * for swapping. * @return */ - public int getCandidate() { - int u; - if(a.size() > b.size()) { + public Node getCandidate() { + Node u; + if(a.getVertexCount() > b.getVertexCount()) { u = a.getCandidate(marked); - if(u == -1) + if(u == null) u = b.getCandidate(marked); } else { u = b.getCandidate(marked); - if(u == -1) + if(u == null) u = a.getCandidate(marked); } - if(u != -1) { + if(u != null) { marked.add(u); } @@ -68,12 +68,12 @@ } - public void swap(int u) { + public void swap(Node u) { Subgraph from = fromSubgraph(u); Subgraph to = toSubgraph(u); - from.remove(u); - to.addNode(u); + from.removeVertex(u); + to.addVertex(u); } - private Subgraph fromSubgraph(int u) { + private Subgraph fromSubgraph(Node u) { Subgraph ret = null; if(a.contains(u)) @@ -84,5 +84,5 @@ } - private Subgraph toSubgraph(int u) { + private Subgraph toSubgraph(Node u) { Subgraph ret = null; if(!a.contains(u)) @@ -106,13 +106,9 @@ } - @Override - public KLPartition clone(){ + public KLPartition copy(){ KLPartition clone = new KLPartition(); clone.a = (Subgraph) a.clone(); clone.b = (Subgraph) b.clone(); - clone.marked = new ArrayList(); - for(int i = 0; i < marked.size(); i++) { - clone.marked.add(marked.get(i)); - } + clone.marked = new HashSet(); return clone; } Index: src/main/java/weka/clusterers/forMetisMQI/MQI.java =================================================================== --- src/main/java/weka/clusterers/forMetisMQI/MQI.java (revision 8) +++ src/main/java/weka/clusterers/forMetisMQI/MQI.java (revision 9) @@ -6,5 +6,5 @@ import javax.swing.JFrame; -import edu.uci.ics.jung.algorithms.layout.CircleLayout; +import edu.uci.ics.jung.algorithms.layout.KKLayout; import edu.uci.ics.jung.algorithms.layout.Layout; import edu.uci.ics.jung.graph.DirectedSparseGraph; @@ -16,5 +16,5 @@ public static void viewGraph(Graph g){ - Layout layout = new CircleLayout(g); + Layout layout = new KKLayout(g); layout.setSize(new Dimension(300,300)); // sets the initial size of the space // The BasicVisualizationServer is parameterized by the edge types @@ -33,5 +33,5 @@ Subgraph A = null; Subgraph B = null; - if(partition.getSubgraph().size() > partition.getComplement().size()) { + if(partition.getSubgraph().getVertexCount() > partition.getComplement().getVertexCount()) { A = partition.getSubgraph(); B = partition.getComplement(); @@ -41,13 +41,13 @@ B = partition.getSubgraph(); } - int a = A.size(); + int a = A.getVertexCount(); int c = partition.edgeCut(); Graph g = new DirectedSparseGraph(); - Iterator nodes = A.iterator(); + Iterator nodes = A.iterator(); while(nodes.hasNext()) { - int u = nodes.next(); - g.addVertex(new Node(Integer.toString(u))); + Node u = nodes.next(); + g.addVertex(u); } @@ -55,9 +55,9 @@ int id = 0; while(nodes.hasNext()) { - int u = nodes.next(); - Iterator neighbors = A.getNeighbours(u).iterator(); + Node u = nodes.next(); + Iterator neighbors = A.getNeighbors(u).iterator(); while(neighbors.hasNext()) { - int v = neighbors.next(); - g.addEdge(new Edge(Integer.toString(id),A.getWeight(u, v),a),new Node(Integer.toString(u)),new Node(Integer.toString(v))); + Node v = neighbors.next(); + g.addEdge(new Edge(Integer.toString(id),A.getWeight(u, v),a),u,v); id++; } @@ -72,10 +72,10 @@ nodes = B.iterator(); while(nodes.hasNext()) { - int u = nodes.next(); - Iterator neighbors = B.getGraph().getNeighbors(u).iterator(); + Node u = nodes.next(); + Iterator neighbors = B.getGraph().getNeighbors(u).iterator(); while(neighbors.hasNext()) { - int v = neighbors.next(); + Node v = neighbors.next(); if(A.contains(v)) { - g.addEdge(new Edge(Integer.toString(id),1,a),source,new Node(Integer.toString(v))); + g.addEdge(new Edge(Integer.toString(id),1,a),source,v); id++; } @@ -85,6 +85,6 @@ nodes = A.iterator(); while(nodes.hasNext()) { - int u = nodes.next(); - g.addEdge(new Edge(Integer.toString(id),1,c),new Node(Integer.toString(u)),sink); + Node u = nodes.next(); + g.addEdge(new Edge(Integer.toString(id),1,c),u,sink); id++; } Index: src/main/java/weka/clusterers/forMetisMQI/Node.java =================================================================== --- src/main/java/weka/clusterers/forMetisMQI/Node.java (revision 8) +++ src/main/java/weka/clusterers/forMetisMQI/Node.java (revision 9) @@ -1,17 +1,37 @@ package weka.clusterers.forMetisMQI; + public class Node { - + private String id; - + + /** 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; } - + @Override public boolean equals(Object o) { - return (o instanceof Node) && (((Node)o).getId().equals(id)); + return (o instanceof Node) && (((Node) o).getId().equals(id)); } - + @Override public int hashCode() { @@ -24,5 +44,5 @@ return id; } - + @Override public String toString() { @@ -30,3 +50,54 @@ } + public int getVwgt() { + return vwgt; + } + + public void setVwgt(int vwgt) { + this.vwgt = vwgt; + } + + 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; + } + + public void setCewgt(int cewgt) { + this.cewgt = cewgt; + } + + 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/Subgraph.java =================================================================== --- src/main/java/weka/clusterers/forMetisMQI/Subgraph.java (revision 8) +++ src/main/java/weka/clusterers/forMetisMQI/Subgraph.java (revision 9) @@ -2,8 +2,9 @@ import java.util.ArrayList; -import java.util.BitSet; import java.util.HashMap; +import java.util.HashSet; import java.util.Iterator; import java.util.List; +import java.util.Set; import java.util.SortedSet; import java.util.TreeSet; @@ -12,30 +13,31 @@ public class Subgraph { - private Graph g = null; - private BitSet nodes = null; - private List listOfNodes = null; - private HashMap ID = null; - private HashMap ED = null; - private HashMap> bucketGain = null; + private UndirectedGraph g = null; + + private Set nodes = null; + +// private BitSet nodes = null; +// private List listOfNodes = null; + private HashMap ID = null; + private HashMap ED = null; + private HashMap> bucketGain = null; private SortedSet gainSet = null; private boolean recomputeGain = true; - public Subgraph(Graph g){ + public Subgraph(UndirectedGraph g){ this.g = g; - nodes = new BitSet(g.size()); - listOfNodes = new ArrayList(); - ID = new HashMap(); - ED = new HashMap(); - bucketGain = new HashMap>(); + nodes = new HashSet(); + ID = new HashMap(); + ED = new HashMap(); + bucketGain = new HashMap>(); gainSet = new TreeSet(); } - public Graph getGraph() { + public UndirectedGraph getGraph() { return g; } - public void addNode(int u) { - nodes.set(g.getIndex(u)); - listOfNodes.add(u); + public void addVertex(Node u) { + nodes.add(u); ID.put(u, 0); ED.put(u, 0); @@ -44,15 +46,16 @@ private void computeDegree() { - for(int i = 0; i < size(); i++) { - int u = listOfNodes.get(i); - Iterator it = g.getNeighbors(u).iterator(); + Iterator subgraphIterator = nodes.iterator(); + while(subgraphIterator.hasNext()) { + Node u = subgraphIterator.next(); + Iterator nborsIterator = g.getNeighbors(u).iterator(); int newID = 0; int newED = 0; - while(it.hasNext()) { - int v = it.next(); + while(nborsIterator.hasNext()) { + Node v = nborsIterator.next(); if(contains(v)) - newID = newID + g.getWeight(u, v); + newID = newID + g.findEdge(u, v).getWeight(); else - newED = newED + g.getWeight(u, v); + newED = newED + g.findEdge(u, v).getWeight(); ID.put(u, newID); ED.put(u, newED); @@ -67,9 +70,10 @@ ED.clear(); computeDegree(); - for(int i = 0; i < size(); i++) { - int u = listOfNodes.get(i); + Iterator subgraphIterator = nodes.iterator(); + while(subgraphIterator.hasNext()) { + Node u = subgraphIterator.next(); int gainU = ED.get(u) - ID.get(u); if(!bucketGain.containsKey(gainU)) { - bucketGain.put(gainU, new ArrayList()); + bucketGain.put(gainU, new ArrayList()); } bucketGain.get(gainU).add(u); @@ -79,6 +83,6 @@ } - public int getCandidate() { - return getCandidate(new ArrayList()); + public Node getCandidate() { + return getCandidate(new HashSet()); } @@ -86,16 +90,16 @@ * * @param marked - * @return the candidate node for swap or -1 if there aren't available nodes. + * @return the candidate node for swap or null if there aren't available nodes. */ - public int getCandidate(List marked) { - if(recomputeGain) - computeGain(); - int candidate = -1; + public Node getCandidate(Set marked) { + if(recomputeGain) + computeGain(); + Node candidate = null; Iterator iterator = ((TreeSet)gainSet).descendingIterator(); - while(iterator.hasNext() && (candidate == -1)) { + while(iterator.hasNext() && (candidate == null)) { int gain = iterator.next(); - Iterator nodes = bucketGain.get(gain).iterator(); - while(nodes.hasNext() && (candidate == -1)) { - int u = nodes.next(); + Iterator nodes = bucketGain.get(gain).iterator(); + while(nodes.hasNext() && (candidate == null)) { + Node u = nodes.next(); if(!marked.contains(u)) candidate = u; @@ -105,5 +109,5 @@ } - public int gain(int u){ + public int gain(Node u){ if(recomputeGain) computeGain(); @@ -111,13 +115,12 @@ } - public void remove(int u) { + public void removeVertex(Node u) { if(recomputeGain) computeGain(); int gainU = gain(u); - nodes.set(g.getIndex(u), false); - listOfNodes.remove(listOfNodes.indexOf(u)); + nodes.remove(u); ID.remove(u); ED.remove(u); - List l = bucketGain.get(gainU); + List l = bucketGain.get(gainU); l.remove(l.indexOf(u)); if(l.size() == 0) { @@ -128,33 +131,40 @@ } - public int size() { - return listOfNodes.size(); - } - - public int getWeight(int u, int v) { + public int getVertexCount() { + return nodes.size(); + } + + public Edge findEdge(Node v1, Node v2) { + Edge e = null; + if(contains(v1) && contains(v2)) + e = g.findEdge(v1, v2); + return e; + } + + public int getWeight(Node u, Node v) { int ret = -1; - if(isEdge(u,v)) - ret = g.getWeight(u, v); + if(containsEdge(u,v)) + ret = g.findEdge(u, v).getWeight(); return ret; } - public Iterator iterator() { - return listOfNodes.iterator(); - } - - public boolean isEdge(int u, int v) { - return nodes.get(g.getIndex(u)) && nodes.get(g.getIndex(v)) && g.isEdge(u, v); - } - - public boolean contains(int u) { - return nodes.get(g.getIndex(u)); - } - - public List getNeighbours(int u) { - List neighbors = new ArrayList(); - Iterator iterator = g.getNeighbors(u).iterator(); + public Iterator iterator() { + return nodes.iterator(); + } + + public boolean containsEdge(Node u, Node v) { + return contains(u) && contains(v) && g.containsEdge(u, v); + } + + public boolean contains(Node u) { + return nodes.contains(u); + } + + public List getNeighbors(Node u) { + List neighbors = new ArrayList(); + Iterator iterator = g.getNeighbors(u).iterator(); while(iterator.hasNext()) { - int v = iterator.next(); - if(contains(v) && isEdge(u, v)) + Node v = iterator.next(); + if(contains(v) && containsEdge(u, v)) neighbors.add(v); } @@ -175,7 +185,7 @@ public String toString() { String out = "["; - Iterator it = listOfNodes.iterator(); + Iterator it = nodes.iterator(); while(it.hasNext()) { - int u = it.next(); + Node u = it.next(); out = out + u + ","; } @@ -184,11 +194,11 @@ } - public List getBoundary() { - if(recomputeGain) - computeGain(); - Iterator> EDIterator = ED.entrySet().iterator(); - List boundary = new ArrayList(); + public List getBoundary() { + if(recomputeGain) + computeGain(); + Iterator> EDIterator = ED.entrySet().iterator(); + List boundary = new ArrayList(); while(EDIterator.hasNext()) { - Entry entry = EDIterator.next(); + Entry entry = EDIterator.next(); if(entry.getValue() > 0) boundary.add(entry.getKey()); @@ -206,44 +216,18 @@ clone.g = g.clone(); - clone.nodes = (BitSet)nodes.clone(); - - clone.listOfNodes = new ArrayList(); - for(int i = 0; i < listOfNodes.size(); i++) { - clone.listOfNodes.add(listOfNodes.get(i)); - } - - clone.ID = new HashMap(); - Iterator> i = ID.entrySet().iterator(); - while(i.hasNext()) { - Entry entry = i.next(); - clone.ID.put(entry.getKey(), entry.getValue()); - } - - clone.ED = new HashMap(); - i = ED.entrySet().iterator(); - while(i.hasNext()) { - Entry entry = i.next(); - clone.ED.put(entry.getKey(), entry.getValue()); - } - - clone.bucketGain = new HashMap>(); - Iterator>>it = bucketGain.entrySet().iterator(); - while(it.hasNext()) { - Entry> entry = it.next(); - List bucketClone = new ArrayList(); - List bucket = entry.getValue(); - for(int j = 0; j < bucket.size(); j++) { - bucketClone.add(bucket.get(j)); - } - clone.bucketGain.put(entry.getKey(), bucketClone); - } - + clone.nodes = new HashSet(); + Iterator graphIterator =clone.g.getVertices().iterator(); + while(graphIterator.hasNext()) { + Node u = graphIterator.next(); + if(contains(u)) + clone.nodes.add(u); + } + + clone.bucketGain = new HashMap>(); clone.gainSet = new TreeSet(); - Iterator gainIt = gainSet.iterator(); - while(gainIt.hasNext()) { - gainSet.add(gainIt.next()); - } - - clone.recomputeGain = recomputeGain; + clone.ID = new HashMap(); + clone.ED = new HashMap(); + + clone.computeGain(); return clone; Index: src/main/java/weka/clusterers/forMetisMQI/Uncoarse.java =================================================================== --- src/main/java/weka/clusterers/forMetisMQI/Uncoarse.java (revision 8) +++ src/main/java/weka/clusterers/forMetisMQI/Uncoarse.java (revision 9) @@ -6,8 +6,7 @@ public class Uncoarse { - private boolean projectedBelongs(int u, KLPartition partition, CoarserGraphElement cge) { + private boolean projectedBelongs(Node u, KLPartition partition, CoarserGraphElement cge) { Subgraph s = partition.getSubgraph(); - int index = cge.getProjected().getIndex(u); - int mappedNode = cge.getMap().get(index); + Node mappedNode = cge.getMap().get(u); return s.contains(mappedNode); } @@ -20,11 +19,11 @@ */ public KLPartition uncoarseOneStep(KLPartition partition, CoarserGraphElement cge) { - Graph projected = cge.getProjected(); + UndirectedGraph projected = cge.getProjected(); Subgraph part = new Subgraph(projected); - Iterator projectedIterator = projected.iterator(); + Iterator projectedIterator = projected.getVertices().iterator(); while(projectedIterator.hasNext()) { - int u = projectedIterator.next(); + Node u = projectedIterator.next(); if(projectedBelongs(u,partition,cge)) - part.addNode(u); + part.addVertex(u); } return new KLPartition(part); 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 9) @@ -0,0 +1,101 @@ +package weka.clusterers.forMetisMQI; + +import java.util.ArrayList; +import java.util.Collection; +import java.util.Iterator; +import java.util.List; + +import weka.core.Attribute; +import weka.core.Instance; +import weka.core.Instances; +import edu.uci.ics.jung.graph.UndirectedSparseGraph; + +public class UndirectedGraph extends UndirectedSparseGraph { + + private static final long serialVersionUID = 1L; + + public List vtxsPermutation() { + Random r = Random.instance(); + List perm = new ArrayList(); + Iterator vtxsIterator = getVertices().iterator(); + while(vtxsIterator.hasNext()) { + Node node = vtxsIterator.next(); + perm.add(node); + } + for (int i = 0; i < perm.size(); i++) { + int k = r.nextInt(perm.size()); + Node swap = perm.get(k); + perm.set(k, perm.get(i)); + perm.set(i, swap); + } + return perm; + } + + public boolean containsEdge(Node v1, Node v2) { + return (findEdge(v1, v2) != null); + } + + public Node findVertex(Node v1) { + Iterator graphIterator = getVertices().iterator(); + while(graphIterator.hasNext()) { + Node v2 = graphIterator.next(); + if(v1.equals(v2)) return v2; + } + return null; + } + + public Collection getNeighborsPermutation(Node n) { + Random r = Random.instance(); + ArrayList perm = new ArrayList(); + Iterator vtxsIterator = getNeighbors(n).iterator(); + while(vtxsIterator.hasNext()) { + Node node = vtxsIterator.next(); + perm.add(node); + } + for (int i = 0; i < perm.size(); i++) { + int k = r.nextInt(perm.size()); + Node swap = perm.get(k); + perm.set(k, perm.get(i)); + perm.set(i, swap); + } + return perm; + } + + public void loadFromInstance(Instances data) { + Iterator dataIterator = data.iterator(); + Attribute from = data.attribute("from"); + Attribute to = data.attribute("to"); + if (from == null || to == null) + throw new RuntimeException( + "Unsupported data: check the list of attributes (from and to are needed)."); + int edgeId = 0; + while (dataIterator.hasNext()) { + Instance edge = dataIterator.next(); + Node node1 = new Node(Integer.toString(((int) Math.round(edge.value(from))))); + Node node2 = new Node(Integer.toString(((int) Math.round(edge.value(to))))); + addVertex(node1); + addVertex(node2); + addEdge(new Edge(Integer.toString(edgeId),1,1),node1,node2); + edgeId++; + } + } + + @Override + public UndirectedGraph clone() { + UndirectedGraph g = new UndirectedGraph(); + Iterator nodesIterator = getVertices().iterator(); + while(nodesIterator.hasNext()) { + g.addVertex(nodesIterator.next().clone()); + } + + Iterator edgesIterator = getEdges().iterator(); + while(edgesIterator.hasNext()) { + Edge e = edgesIterator.next(); + g.addEdge(e.clone(), getEndpoints(e)); + } + + + return g; + } + +}