Index: src/main/java/weka/clusterers/SimpleClusterer.java =================================================================== --- src/main/java/weka/clusterers/SimpleClusterer.java (revision 10) +++ src/main/java/weka/clusterers/SimpleClusterer.java (revision 11) @@ -3,5 +3,5 @@ import weka.clusterers.forMetisMQI.GraphAlgorithms; -import weka.clusterers.forMetisMQI.UndirectedGraph; +import weka.clusterers.forMetisMQI.graph.UndirectedGraph; import weka.core.Capabilities; import weka.core.Instance; Index: src/main/java/weka/clusterers/forMetisMQI/Coarse.java =================================================================== --- src/main/java/weka/clusterers/forMetisMQI/Coarse.java (revision 10) +++ (revision ) @@ -1,192 +1,0 @@ -package weka.clusterers.forMetisMQI; - -import java.io.PrintStream; -import java.util.HashMap; -import java.util.HashSet; -import java.util.Iterator; -import java.util.Map; -import java.util.Set; -import java.util.Stack; - -import edu.uci.ics.jung.graph.util.Pair; - -public class Coarse { - - private static boolean debug = false; - private static PrintStream debugStream = System.err; - private static int finerSize = 5; - - /** - * Return true if the vertex v is matched - * - * @param g graph - * @param v - * the index of the vertex - * @return true if the vertex v is matched, false o.w. - */ - 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; - Iterator nodeIterator = g.vtxsPermutation().iterator(); - while (nodeIterator.hasNext()) { - Node u = nodeIterator.next(); - if (debug) - debugStream.println("Visiting node " + u + " Matched = " + isMatched(match,u)); - if (!isMatched(match,u)) { - boolean foundMatch = false; - Node matchedNode = null; - Iterator iterator = g.getNeighborsPermutation(u).iterator(); - while(iterator.hasNext() && !foundMatch){ - Node v = iterator.next(); - if (!isMatched(match,v)) { - matchedNode = v; - foundMatch = true; - if (debug) - debugStream.println("Found a match with node " - + matchedNode); - } - } - if (debug && !foundMatch) - debugStream.println("There aren't unmatched neighbors."); - Node newNode = new Node(Integer.toString(labelCounter)); - if(foundMatch) { - 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 { - match.put(u, u); - map.put(u, newNode); - if(debug) debugStream.println("Node " + u + " with " + " new node id: " + getMappedNode(map, u)); - } - labelCounter++; - } - } - } - - private static Node getMatchedNode(Map match, Node u) { - return match.get(u); - } - - private static Node getMappedNode(Map map, Node u) { - return map.get(u); - } - - /** - * Return a new contracted graph. - */ - 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()) { - 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())); - neighbors.remove(getMappedNode(map,u)); - it = neighbors.iterator(); - while(it.hasNext()) { - 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). - - Iterator edgeIterator = g.getEdges().iterator(); - while(edgeIterator.hasNext()) { - Edge oldEdge = edgeIterator.next(); - Pair srcDst = g.getEndpoints(oldEdge); - Node src = srcDst.getFirst(); - Node dst = srcDst.getSecond(); - 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()); - } - } - 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()); - nodesComplete.add(u); - nodesComplete.add(v); - } - } else { - getMappedNode(map,u).setVwgt(u.getVwgt()); - getMappedNode(map,u).setCewgt(u.getCewgt()); - } - } - return output; - } - - /** - * Performs the first stage of the METIS algorithm, using RM. - */ - private 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); - 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 = null; - UndirectedGraph curr = g; - int i = 0; - - do { - if(debug) - debugStream.println("--------CONTRACTION-nr" + i +"------------------------------"); - e = coarseOneStep(curr); - stack.push(e); - curr = e.getContracted(); - 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; - } - - public static void setFinerSize(int i) { - finerSize = i; - } -} Index: src/main/java/weka/clusterers/forMetisMQI/CoarserGraphElement.java =================================================================== --- src/main/java/weka/clusterers/forMetisMQI/CoarserGraphElement.java (revision 10) +++ (revision ) @@ -1,35 +1,0 @@ -package weka.clusterers.forMetisMQI; - -import java.util.Map; - -public class CoarserGraphElement { - - private UndirectedGraph contracted; - private UndirectedGraph projected; - private Map match; - private Map map; - - public CoarserGraphElement(UndirectedGraph contracted, UndirectedGraph projected, Map match, Map map) { - this.contracted = contracted; - this.projected = projected; - this.match = match; - this.map = map; - } - - public Map getMatch() { - return match; - } - - public Map getMap() { - return map; - } - - public UndirectedGraph getContracted() { - return contracted; - } - - public UndirectedGraph getProjected() { - return projected; - } - -} Index: src/main/java/weka/clusterers/forMetisMQI/Edge.java =================================================================== --- src/main/java/weka/clusterers/forMetisMQI/Edge.java (revision 10) +++ (revision ) @@ -1,67 +1,0 @@ -package weka.clusterers.forMetisMQI; - -public class Edge { - - private String id; - - private int weight; - - private int capacity; - - public Edge(String id, int weight, int capacity) { - this.id = id; - this.weight = weight; - this.capacity = capacity; - } - - @Override - public int hashCode() { - int hash = 1; - hash = hash * 31 + id.hashCode(); - return hash; - } - - @Override - public boolean equals(Object o) { - boolean result = (o instanceof Edge); - if(result) { - Edge e = (Edge) o; - result = result && (e.getId().equals(id)); - result = result && (e.getWeight() == weight); - result = result && (e.getCapacity() == capacity); - } - return result; - } - - public String getId() { - return id; - } - - public int getWeight() { - return weight; - } - - public int getCapacity() { - return capacity; - } - - @Override - public String toString() { - return "E" + id + " w:" + weight; - } - - 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/GraphAlgorithms.java =================================================================== --- src/main/java/weka/clusterers/forMetisMQI/GraphAlgorithms.java (revision 10) +++ src/main/java/weka/clusterers/forMetisMQI/GraphAlgorithms.java (revision 11) @@ -3,9 +3,15 @@ import java.util.Stack; +import weka.clusterers.forMetisMQI.coarse.Coarse; +import weka.clusterers.forMetisMQI.coarse.CoarserGraphElement; +import weka.clusterers.forMetisMQI.graph.Bisection; +import weka.clusterers.forMetisMQI.graph.Node; +import weka.clusterers.forMetisMQI.graph.UndirectedGraph; + public class GraphAlgorithms { - public KLPartition KL(UndirectedGraph g) { - KLPartition partition = new KLPartition(g); - KLPartition result = partition; + public Bisection KL(UndirectedGraph g) { + Bisection partition = new Bisection(g); + Bisection result = partition; int bestEdgeCut = Integer.MAX_VALUE; Node u = partition.getCandidate(); @@ -22,8 +28,8 @@ public void METIS(UndirectedGraph g) { - KLPartition partition = null; + MQI.viewGraph(g); + Bisection partition = null; Coarse.setFinerSize(8); Stack stack = Coarse.coarse(g); - if(stack.size() > 0) { partition = KL(stack.peek().getContracted()); @@ -32,6 +38,6 @@ System.out.println(partition.toString()); } - - MQI.start(partition); + System.out.println("AAAAAA"); + System.out.println(MQI.mqi(partition).toString()); } Index: src/main/java/weka/clusterers/forMetisMQI/KLPartition.java =================================================================== --- src/main/java/weka/clusterers/forMetisMQI/KLPartition.java (revision 10) +++ (revision ) @@ -1,123 +1,0 @@ -package weka.clusterers.forMetisMQI; - -import java.util.HashSet; -import java.util.Iterator; -import java.util.Set; - - -public class KLPartition { - - private Subgraph a = null; - - private Subgraph b = null; - - private Set marked = null; - - private KLPartition() { - } - - public KLPartition(Subgraph s) { - UndirectedGraph g = s.getGraph(); - a = s; - b = new Subgraph(g); - Iterator graphIterator = g.getVertices().iterator(); - while(graphIterator.hasNext()) { - Node u = graphIterator.next(); - if(!s.contains(u)) - b.addVertex(u); - } - marked = new HashSet(); - } - - public KLPartition(UndirectedGraph g){ - a = new Subgraph(g); - b = new Subgraph(g); - Iterator graph = g.vtxsPermutation().iterator(); - int i = 0; - while(graph.hasNext()) { - Node u = graph.next(); - if((i%2)==0) - a.addVertex(u); - else - b.addVertex(u); - i++; - } - marked = new HashSet(); - } - - /** - * Returns the node marked as candidate for swapping or null if there aren't node available - * for swapping. - * @return - */ - public Node getCandidate() { - Node u; - if(a.getVertexCount() > b.getVertexCount()) { - u = a.getCandidate(marked); - if(u == null) - u = b.getCandidate(marked); - } else { - u = b.getCandidate(marked); - if(u == null) - u = a.getCandidate(marked); - } - if(u != null) { - marked.add(u); - } - return u; - } - - public void swap(Node u) { - Subgraph from = fromSubgraph(u); - Subgraph to = toSubgraph(u); - from.removeVertex(u); - to.addVertex(u); - } - - private Subgraph fromSubgraph(Node u) { - Subgraph ret = null; - if(a.contains(u)) - ret = a; - if(b.contains(u)) - ret = b; - return ret; - } - - private Subgraph toSubgraph(Node u) { - Subgraph ret = null; - if(!a.contains(u)) - ret = a; - if(!b.contains(u)) - ret = b; - return ret; - } - - public int edgeCut() { - int acc = a.getExternalDegree() + b.getExternalDegree(); - return acc; - } - - public Subgraph getSubgraph() { - return a; - } - - public Subgraph getComplement() { - return b; - } - - public KLPartition copy(){ - KLPartition clone = new KLPartition(); - clone.a = (Subgraph) a.clone(); - clone.b = (Subgraph) b.clone(); - clone.marked = new HashSet(); - return clone; - } - - @Override - public String toString(){ - String out = a.toString(); - out = out + "\n"; - out = out + b.toString(); - return out; - } -} Index: src/main/java/weka/clusterers/forMetisMQI/MQI.java =================================================================== --- src/main/java/weka/clusterers/forMetisMQI/MQI.java (revision 10) +++ src/main/java/weka/clusterers/forMetisMQI/MQI.java (revision 11) @@ -2,10 +2,23 @@ import java.awt.Dimension; +import java.util.HashMap; import java.util.Iterator; +import java.util.Map; +import java.util.Set; import javax.swing.JFrame; +import org.apache.commons.collections15.Factory; +import org.apache.commons.collections15.Transformer; + +import weka.clusterers.forMetisMQI.graph.Bisection; +import weka.clusterers.forMetisMQI.graph.Edge; +import weka.clusterers.forMetisMQI.graph.Node; +import weka.clusterers.forMetisMQI.graph.Subgraph; +import weka.clusterers.forMetisMQI.graph.UndirectedGraph; +import edu.uci.ics.jung.algorithms.flows.EdmondsKarpMaxFlow; import edu.uci.ics.jung.algorithms.layout.KKLayout; import edu.uci.ics.jung.algorithms.layout.Layout; +import edu.uci.ics.jung.graph.DirectedGraph; import edu.uci.ics.jung.graph.DirectedSparseGraph; import edu.uci.ics.jung.graph.Graph; @@ -15,11 +28,13 @@ public class MQI { + static int i = -1; + public static void viewGraph(Graph g){ Layout layout = new KKLayout(g); - layout.setSize(new Dimension(300,300)); // sets the initial size of the space + layout.setSize(new Dimension(800,600)); // sets the initial size of the space // The BasicVisualizationServer is parameterized by the edge types BasicVisualizationServer vv = new BasicVisualizationServer(layout); - vv.setPreferredSize(new Dimension(350,350)); //Sets the viewing area size + vv.setPreferredSize(new Dimension(800,600)); //Sets the viewing area size vv.getRenderContext().setVertexLabelTransformer(new ToStringLabeller()); vv.getRenderContext().setEdgeLabelTransformer(new ToStringLabeller()); @@ -31,6 +46,22 @@ frame.setVisible(true); } + + /** + * Given a bisection, returns the cardinality of the larger subgraph. + * @param b + * @return + */ + static private int getMaxCardinality(Bisection b) { + Subgraph A = null; + if(b.getSubgraph().getVertexCount() > b.getComplement().getVertexCount()) { + A = b.getSubgraph(); + } + else { + A = b.getComplement(); + } + return A.getVertexCount(); + } - static public void start(KLPartition partition) { + static private DirectedGraph prepareDirectedGraph(Bisection partition, Node source, Node sink) { Subgraph A = null; Subgraph B = null; @@ -44,8 +75,8 @@ } int a = A.getVertexCount(); - int c = partition.edgeCut(); + int c = partition.edgeCut() / 2; - Graph g = new DirectedSparseGraph(); + DirectedGraph g = new DirectedSparseGraph(); Iterator nodes = A.iterator(); while(nodes.hasNext()) { @@ -66,6 +97,4 @@ } - Node source = new Node("S"); - Node sink = new Node("T"); g.addVertex(source); g.addVertex(sink); @@ -91,8 +120,56 @@ id++; } - -// viewGraph(g); - System.out.println(g.toString()); - + return g; + } + + static public Bisection mqi(Bisection partition) { + boolean finished = false; + Bisection bisection = partition; + int maxFlowThreshold = Integer.MAX_VALUE; + while (!finished) { + UndirectedGraph startingGraph = partition.getGraph(); + Node source = new Node("S"); + Node sink = new Node("T"); + DirectedGraph g = prepareDirectedGraph(bisection, source, sink); + Transformer capTransformer = new Transformer() { + public Double transform(Edge e) { + return (double) e.getCapacity(); + } + }; + Map edgeFlowMap = new HashMap(); + // This Factory produces new edges for use by the algorithm + i=-1; + Factory edgeFactory = new Factory() { + public Edge create() { + i++; + return new Edge(Integer.toString(i), 1, 1); + } + }; + EdmondsKarpMaxFlow alg = new EdmondsKarpMaxFlow( + g, source, sink, capTransformer, edgeFlowMap, edgeFactory); + + maxFlowThreshold = getMaxCardinality(bisection) * bisection.edgeCut() / 2; + alg.evaluate(); + if(alg.getMaxFlow() < maxFlowThreshold) { + Set sinkPartition = alg.getNodesInSinkPartition(); + Set sourcePartition = alg.getNodesInSourcePartition(); + bisection = prepareBisection(startingGraph, sourcePartition, sinkPartition); + } else + finished = true; + } + return bisection; + } + + private static Bisection prepareBisection(UndirectedGraph g, Set sourcePartition, Set sinkPartition) { + Bisection b = null; + Subgraph sourceSubgraph = new Subgraph(g, sourcePartition); + Subgraph sinkSubgraph = new Subgraph(g, sinkPartition); + Subgraph subgraph = null; + if(sourceSubgraph.getVertexCount() > sinkSubgraph.getVertexCount()) + subgraph =sourceSubgraph; + else + subgraph = sinkSubgraph; + b = new Bisection(subgraph); + return b; } Index: src/main/java/weka/clusterers/forMetisMQI/Node.java =================================================================== --- src/main/java/weka/clusterers/forMetisMQI/Node.java (revision 10) +++ (revision ) @@ -1,63 +1,0 @@ -package weka.clusterers.forMetisMQI; - - -public class Node { - - private String id; - - /** The weight of the node */ - private int vwgt; - /** The weight of the edges that have been contracted to create the node */ - private int cewgt; - public Node(String id) { - this.id = id; - this.vwgt = 1; - this.cewgt = 0; - } - - @Override - public boolean equals(Object o) { - return (o instanceof Node) && (((Node) o).getId().equals(id)); - } - - @Override - public int hashCode() { - int hash = 1; - hash = hash * 31 + id.hashCode(); - return hash; - } - - public String getId() { - return id; - } - - @Override - public String toString() { - return "N" + id; //+ " Cewgt: " + cewgt; - } - - public int getVwgt() { - return vwgt; - } - - public void setVwgt(int vwgt) { - this.vwgt = vwgt; - } - - public int getCewgt() { - return cewgt; - } - - public void setCewgt(int cewgt) { - this.cewgt = cewgt; - } - - @Override - public Node clone() { - Node n = new Node(id); - n.cewgt = cewgt; - n.vwgt = vwgt; - return n; - } - -} Index: src/main/java/weka/clusterers/forMetisMQI/Subgraph.java =================================================================== --- src/main/java/weka/clusterers/forMetisMQI/Subgraph.java (revision 10) +++ (revision ) @@ -1,235 +1,0 @@ -package weka.clusterers.forMetisMQI; - -import java.util.ArrayList; -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; -import java.util.Map.Entry; - -public class Subgraph { - - 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(UndirectedGraph g){ - this.g = g; - nodes = new HashSet(); - ID = new HashMap(); - ED = new HashMap(); - bucketGain = new HashMap>(); - gainSet = new TreeSet(); - } - - public UndirectedGraph getGraph() { - return g; - } - - public void addVertex(Node u) { - nodes.add(u); - ID.put(u, 0); - ED.put(u, 0); - recomputeGain = true; - } - - private void computeDegree() { - Iterator subgraphIterator = nodes.iterator(); - while(subgraphIterator.hasNext()) { - Node u = subgraphIterator.next(); - Iterator nborsIterator = g.getNeighbors(u).iterator(); - int newID = 0; - int newED = 0; - while(nborsIterator.hasNext()) { - Node v = nborsIterator.next(); - if(contains(v)) - newID = newID + g.findEdge(u, v).getWeight(); - else - newED = newED + g.findEdge(u, v).getWeight(); - ID.put(u, newID); - ED.put(u, newED); - } - } - } - - private void computeGain() { - bucketGain.clear(); - gainSet.clear(); - ID.clear(); - ED.clear(); - computeDegree(); - 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.get(gainU).add(u); - gainSet.add(gainU); - } - recomputeGain = false; - } - - public Node getCandidate() { - return getCandidate(new HashSet()); - } - - /** - * - * @param marked - * @return the candidate node for swap or null if there aren't available nodes. - */ - public Node getCandidate(Set marked) { - if(recomputeGain) - computeGain(); - Node candidate = null; - Iterator iterator = ((TreeSet)gainSet).descendingIterator(); - while(iterator.hasNext() && (candidate == null)) { - int gain = iterator.next(); - Iterator nodes = bucketGain.get(gain).iterator(); - while(nodes.hasNext() && (candidate == null)) { - Node u = nodes.next(); - if(!marked.contains(u)) - candidate = u; - } - } - return candidate; - } - - public int gain(Node u){ - if(recomputeGain) - computeGain(); - return ED.get(u) - ID.get(u); - } - - public void removeVertex(Node u) { - if(recomputeGain) - computeGain(); - int gainU = gain(u); - nodes.remove(u); - ID.remove(u); - ED.remove(u); - List l = bucketGain.get(gainU); - l.remove(l.indexOf(u)); - if(l.size() == 0) { - bucketGain.remove(gainU); - gainSet.remove(gainU); - } - recomputeGain = true; - } - - 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(containsEdge(u,v)) - ret = g.findEdge(u, v).getWeight(); - return ret; - } - - 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()) { - Node v = iterator.next(); - if(contains(v) && containsEdge(u, v)) - neighbors.add(v); - } - return neighbors; - } - - public int getExternalDegree() { - if(recomputeGain) - computeGain(); - int acc = 0; - Iterator it = ED.values().iterator(); - while(it.hasNext()) - acc = acc + it.next(); - return acc; - } - - @Override - public String toString() { - String out = "["; - Iterator it = nodes.iterator(); - while(it.hasNext()) { - Node u = it.next(); - out = out + u + ","; - } - out = out + "]"; - return out; - } - - public List getBoundary() { - if(recomputeGain) - computeGain(); - Iterator> EDIterator = ED.entrySet().iterator(); - List boundary = new ArrayList(); - while(EDIterator.hasNext()) { - Entry entry = EDIterator.next(); - if(entry.getValue() > 0) - boundary.add(entry.getKey()); - } - return boundary; - } - - private Subgraph() { - - } - - @Override - public Subgraph clone() { - Subgraph clone = new Subgraph(); - clone.g = g.clone(); - - 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(); - 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 10) +++ src/main/java/weka/clusterers/forMetisMQI/Uncoarse.java (revision 11) @@ -4,7 +4,13 @@ import java.util.Stack; +import weka.clusterers.forMetisMQI.coarse.CoarserGraphElement; +import weka.clusterers.forMetisMQI.graph.Bisection; +import weka.clusterers.forMetisMQI.graph.Node; +import weka.clusterers.forMetisMQI.graph.Subgraph; +import weka.clusterers.forMetisMQI.graph.UndirectedGraph; + public class Uncoarse { - private boolean projectedBelongs(Node u, KLPartition partition, CoarserGraphElement cge) { + private boolean projectedBelongs(Node u, Bisection partition, CoarserGraphElement cge) { Subgraph s = partition.getSubgraph(); Node mappedNode = cge.getMap().get(u); @@ -18,5 +24,5 @@ * @param cge */ - public KLPartition uncoarseOneStep(KLPartition partition, CoarserGraphElement cge) { + public Bisection uncoarseOneStep(Bisection partition, CoarserGraphElement cge) { UndirectedGraph projected = cge.getProjected(); Subgraph part = new Subgraph(projected); @@ -27,8 +33,8 @@ part.addVertex(u); } - return new KLPartition(part); + return new Bisection(part); } - public KLPartition uncoarse(Stack stack, KLPartition partition) { + public Bisection uncoarse(Stack stack, Bisection partition) { while(stack.size() > 0) { CoarserGraphElement element = stack.pop(); Index: src/main/java/weka/clusterers/forMetisMQI/UndirectedGraph.java =================================================================== --- src/main/java/weka/clusterers/forMetisMQI/UndirectedGraph.java (revision 10) +++ (revision ) @@ -1,125 +1,0 @@ -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; -import edu.uci.ics.jung.graph.util.Pair; - -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; - } - - 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(); - } - -} Index: src/main/java/weka/clusterers/forMetisMQI/coarse/Coarse.java =================================================================== --- src/main/java/weka/clusterers/forMetisMQI/coarse/Coarse.java (revision 11) +++ src/main/java/weka/clusterers/forMetisMQI/coarse/Coarse.java (revision 11) @@ -0,0 +1,196 @@ +package weka.clusterers.forMetisMQI.coarse; + +import java.io.PrintStream; +import java.util.HashMap; +import java.util.HashSet; +import java.util.Iterator; +import java.util.Map; +import java.util.Set; +import java.util.Stack; + +import weka.clusterers.forMetisMQI.graph.Edge; +import weka.clusterers.forMetisMQI.graph.Node; +import weka.clusterers.forMetisMQI.graph.UndirectedGraph; + +import edu.uci.ics.jung.graph.util.Pair; + +public class Coarse { + + private static boolean debug = false; + private static PrintStream debugStream = System.err; + private static int finerSize = 5; + + /** + * Return true if the vertex v is matched + * + * @param g graph + * @param v + * the index of the vertex + * @return true if the vertex v is matched, false o.w. + */ + 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; + Iterator nodeIterator = g.vtxsPermutation().iterator(); + while (nodeIterator.hasNext()) { + Node u = nodeIterator.next(); + if (debug) + debugStream.println("Visiting node " + u + " Matched = " + isMatched(match,u)); + if (!isMatched(match,u)) { + boolean foundMatch = false; + Node matchedNode = null; + Iterator iterator = g.getNeighborsPermutation(u).iterator(); + while(iterator.hasNext() && !foundMatch){ + Node v = iterator.next(); + if (!isMatched(match,v)) { + matchedNode = v; + foundMatch = true; + if (debug) + debugStream.println("Found a match with node " + + matchedNode); + } + } + if (debug && !foundMatch) + debugStream.println("There aren't unmatched neighbors."); + Node newNode = new Node(Integer.toString(labelCounter)); + if(foundMatch) { + 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 { + match.put(u, u); + map.put(u, newNode); + if(debug) debugStream.println("Node " + u + " with " + " new node id: " + getMappedNode(map, u)); + } + labelCounter++; + } + } + } + + private static Node getMatchedNode(Map match, Node u) { + return match.get(u); + } + + private static Node getMappedNode(Map map, Node u) { + return map.get(u); + } + + /** + * Return a new contracted graph. + */ + 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()) { + 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())); + neighbors.remove(getMappedNode(map,u)); + it = neighbors.iterator(); + while(it.hasNext()) { + 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). + + Iterator edgeIterator = g.getEdges().iterator(); + while(edgeIterator.hasNext()) { + Edge oldEdge = edgeIterator.next(); + Pair srcDst = g.getEndpoints(oldEdge); + Node src = srcDst.getFirst(); + Node dst = srcDst.getSecond(); + 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()); + } + } + 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()); + nodesComplete.add(u); + nodesComplete.add(v); + } + } else { + getMappedNode(map,u).setVwgt(u.getVwgt()); + getMappedNode(map,u).setCewgt(u.getCewgt()); + } + } + return output; + } + + /** + * Performs the first stage of the METIS algorithm, using RM. + */ + private 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); + 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 = null; + UndirectedGraph curr = g; + int i = 0; + + do { + if(debug) + debugStream.println("--------CONTRACTION-nr" + i +"------------------------------"); + e = coarseOneStep(curr); + stack.push(e); + curr = e.getContracted(); + 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; + } + + public static void setFinerSize(int i) { + finerSize = i; + } +} Index: src/main/java/weka/clusterers/forMetisMQI/coarse/CoarserGraphElement.java =================================================================== --- src/main/java/weka/clusterers/forMetisMQI/coarse/CoarserGraphElement.java (revision 11) +++ src/main/java/weka/clusterers/forMetisMQI/coarse/CoarserGraphElement.java (revision 11) @@ -0,0 +1,38 @@ +package weka.clusterers.forMetisMQI.coarse; + +import java.util.Map; + +import weka.clusterers.forMetisMQI.graph.Node; +import weka.clusterers.forMetisMQI.graph.UndirectedGraph; + +public class CoarserGraphElement { + + private UndirectedGraph contracted; + private UndirectedGraph projected; + private Map match; + private Map map; + + public CoarserGraphElement(UndirectedGraph contracted, UndirectedGraph projected, Map match, Map map) { + this.contracted = contracted; + this.projected = projected; + this.match = match; + this.map = map; + } + + public Map getMatch() { + return match; + } + + public Map getMap() { + return map; + } + + public UndirectedGraph getContracted() { + return contracted; + } + + public UndirectedGraph getProjected() { + return projected; + } + +} Index: src/main/java/weka/clusterers/forMetisMQI/graph/Bisection.java =================================================================== --- src/main/java/weka/clusterers/forMetisMQI/graph/Bisection.java (revision 11) +++ src/main/java/weka/clusterers/forMetisMQI/graph/Bisection.java (revision 11) @@ -0,0 +1,139 @@ +package weka.clusterers.forMetisMQI.graph; + +import java.util.HashSet; +import java.util.Iterator; +import java.util.Set; + + + +public class Bisection { + + private Subgraph a = null; + + private Subgraph b = null; + + private Set marked = null; + + private UndirectedGraph g = null; + + private Bisection() { + } + + /** + * Initialize the bisection with a given subgraph. + * @param s + */ + public Bisection(Subgraph s) { + g = s.getGraph(); + a = s; + b = new Subgraph(g); + Iterator graphIterator = g.getVertices().iterator(); + while(graphIterator.hasNext()) { + Node u = graphIterator.next(); + if(!s.contains(u)) + b.addVertex(u); + } + marked = new HashSet(); + } + + /** + * Creates a bisection choosing randomly the nodes for each subgraph. + * @param g + */ + public Bisection(UndirectedGraph g){ + this.g = g; + a = new Subgraph(g); + b = new Subgraph(g); + Iterator graph = g.vtxsPermutation().iterator(); + int i = 0; + while(graph.hasNext()) { + Node u = graph.next(); + if((i%2)==0) + a.addVertex(u); + else + b.addVertex(u); + i++; + } + marked = new HashSet(); + } + + public UndirectedGraph getGraph() { + return g; + } + + /** + * Returns the node marked as candidate for swapping or null if there aren't node available + * for swapping. + * @return + */ + public Node getCandidate() { + Node u; + if(a.getVertexCount() > b.getVertexCount()) { + u = a.getCandidate(marked); + if(u == null) + u = b.getCandidate(marked); + } else { + u = b.getCandidate(marked); + if(u == null) + u = a.getCandidate(marked); + } + if(u != null) { + marked.add(u); + } + return u; + } + + public void swap(Node u) { + Subgraph from = fromSubgraph(u); + Subgraph to = toSubgraph(u); + from.removeVertex(u); + to.addVertex(u); + } + + private Subgraph fromSubgraph(Node u) { + Subgraph ret = null; + if(a.contains(u)) + ret = a; + if(b.contains(u)) + ret = b; + return ret; + } + + private Subgraph toSubgraph(Node u) { + Subgraph ret = null; + if(!a.contains(u)) + ret = a; + if(!b.contains(u)) + ret = b; + return ret; + } + + public int edgeCut() { + int acc = a.getExternalDegree() + b.getExternalDegree(); + return acc; + } + + public Subgraph getSubgraph() { + return a; + } + + public Subgraph getComplement() { + return b; + } + + public Bisection copy(){ + Bisection clone = new Bisection(); + clone.a = (Subgraph) a.clone(); + clone.b = (Subgraph) b.clone(); + clone.marked = new HashSet(); + return clone; + } + + @Override + public String toString(){ + String out = a.toString(); + out = out + "\n"; + out = out + b.toString(); + return out; + } +} Index: src/main/java/weka/clusterers/forMetisMQI/graph/Edge.java =================================================================== --- src/main/java/weka/clusterers/forMetisMQI/graph/Edge.java (revision 11) +++ src/main/java/weka/clusterers/forMetisMQI/graph/Edge.java (revision 11) @@ -0,0 +1,67 @@ +package weka.clusterers.forMetisMQI.graph; + +public class Edge { + + private String id; + + private int weight; + + private int capacity; + + public Edge(String id, int weight, int capacity) { + this.id = id; + this.weight = weight; + this.capacity = capacity; + } + + @Override + public int hashCode() { + int hash = 1; + hash = hash * 31 + id.hashCode(); + return hash; + } + + @Override + public boolean equals(Object o) { + boolean result = (o instanceof Edge); + if(result) { + Edge e = (Edge) o; + result = result && (e.getId().equals(id)); + result = result && (e.getWeight() == weight); + result = result && (e.getCapacity() == capacity); + } + return result; + } + + public String getId() { + return id; + } + + public int getWeight() { + return weight; + } + + public int getCapacity() { + return capacity; + } + + @Override + public String toString() { + return Integer.toString(capacity); + } + + 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/Node.java =================================================================== --- src/main/java/weka/clusterers/forMetisMQI/graph/Node.java (revision 11) +++ src/main/java/weka/clusterers/forMetisMQI/graph/Node.java (revision 11) @@ -0,0 +1,63 @@ +package weka.clusterers.forMetisMQI.graph; + + +public class Node { + + private String id; + + /** The weight of the node */ + private int vwgt; + /** The weight of the edges that have been contracted to create the node */ + private int cewgt; + public Node(String id) { + this.id = id; + this.vwgt = 1; + this.cewgt = 0; + } + + @Override + public boolean equals(Object o) { + return (o instanceof Node) && (((Node) o).getId().equals(id)); + } + + @Override + public int hashCode() { + int hash = 1; + hash = hash * 31 + id.hashCode(); + return hash; + } + + public String getId() { + return id; + } + + @Override + public String toString() { + return "N" + id; //+ " Cewgt: " + cewgt; + } + + public int getVwgt() { + return vwgt; + } + + public void setVwgt(int vwgt) { + this.vwgt = vwgt; + } + + public int getCewgt() { + return cewgt; + } + + public void setCewgt(int cewgt) { + this.cewgt = cewgt; + } + + @Override + public Node clone() { + Node n = new Node(id); + n.cewgt = cewgt; + n.vwgt = vwgt; + return n; + } + +} Index: src/main/java/weka/clusterers/forMetisMQI/graph/Subgraph.java =================================================================== --- src/main/java/weka/clusterers/forMetisMQI/graph/Subgraph.java (revision 11) +++ src/main/java/weka/clusterers/forMetisMQI/graph/Subgraph.java (revision 11) @@ -0,0 +1,259 @@ +package weka.clusterers.forMetisMQI.graph; + +import java.util.ArrayList; +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; +import java.util.Map.Entry; + +import edu.uci.ics.jung.algorithms.filters.FilterUtils; + + +public class Subgraph { + + private UndirectedGraph g = null; + + private Set nodes = null; + + private HashMap ID = null; + private HashMap ED = null; + private HashMap> bucketGain = null; + private SortedSet gainSet = null; + private boolean recomputeGain = true; + + public Subgraph(UndirectedGraph g){ + this.g = g; + nodes = new HashSet(); + ID = new HashMap(); + ED = new HashMap(); + bucketGain = new HashMap>(); + gainSet = new TreeSet(); + } + + public Subgraph(UndirectedGraph g, Set nodes) { + this.g = g; + this.nodes = new HashSet(); + this.ID = new HashMap(); + this.ED = new HashMap(); + this.bucketGain = new HashMap>(); + this.gainSet = new TreeSet(); + Iterator nodesIterator = nodes.iterator(); + while(nodesIterator.hasNext()) { + addVertex(nodesIterator.next()); + } + } + + public UndirectedGraph getGraph() { + return g; + } + + /** + * Adds to the subgraph the node u iff u belongs to the graph. + * @param u + */ + public void addVertex(Node u) { + if(g.containsVertex(u)) { + nodes.add(u); + ID.put(u, 0); + ED.put(u, 0); + recomputeGain = true; + } + } + + private void computeDegree() { + Iterator subgraphIterator = nodes.iterator(); + while(subgraphIterator.hasNext()) { + Node u = subgraphIterator.next(); + Iterator nborsIterator = g.getNeighbors(u).iterator(); + int newID = 0; + int newED = 0; + while(nborsIterator.hasNext()) { + Node v = nborsIterator.next(); + if(contains(v)) + newID = newID + g.findEdge(u, v).getWeight(); + else + newED = newED + g.findEdge(u, v).getWeight(); + ID.put(u, newID); + ED.put(u, newED); + } + } + } + + private void computeGain() { + bucketGain.clear(); + gainSet.clear(); + ID.clear(); + ED.clear(); + computeDegree(); + 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.get(gainU).add(u); + gainSet.add(gainU); + } + recomputeGain = false; + } + + public Node getCandidate() { + return getCandidate(new HashSet()); + } + + /** + * + * @param marked + * @return the candidate node for swap or null if there aren't available nodes. + */ + public Node getCandidate(Set marked) { + if(recomputeGain) + computeGain(); + Node candidate = null; + Iterator iterator = ((TreeSet)gainSet).descendingIterator(); + while(iterator.hasNext() && (candidate == null)) { + int gain = iterator.next(); + Iterator nodes = bucketGain.get(gain).iterator(); + while(nodes.hasNext() && (candidate == null)) { + Node u = nodes.next(); + if(!marked.contains(u)) + candidate = u; + } + } + return candidate; + } + + public int gain(Node u){ + if(recomputeGain) + computeGain(); + return ED.get(u) - ID.get(u); + } + + public void removeVertex(Node u) { + if(recomputeGain) + computeGain(); + int gainU = gain(u); + nodes.remove(u); + ID.remove(u); + ED.remove(u); + List l = bucketGain.get(gainU); + l.remove(l.indexOf(u)); + if(l.size() == 0) { + bucketGain.remove(gainU); + gainSet.remove(gainU); + } + recomputeGain = true; + } + + 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(containsEdge(u,v)) + ret = g.findEdge(u, v).getWeight(); + return ret; + } + + 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()) { + Node v = iterator.next(); + if(contains(v) && containsEdge(u, v)) + neighbors.add(v); + } + return neighbors; + } + + public int getExternalDegree() { + if(recomputeGain) + computeGain(); + int acc = 0; + Iterator it = ED.values().iterator(); + while(it.hasNext()) + acc = acc + it.next(); + return acc; + } + + @Override + public String toString() { + String out = "["; + Iterator it = nodes.iterator(); + while(it.hasNext()) { + Node u = it.next(); + out = out + u + ","; + } + out = out + "]"; + return out; + } + + public List getBoundary() { + if(recomputeGain) + computeGain(); + Iterator> EDIterator = ED.entrySet().iterator(); + List boundary = new ArrayList(); + while(EDIterator.hasNext()) { + Entry entry = EDIterator.next(); + if(entry.getValue() > 0) + boundary.add(entry.getKey()); + } + return boundary; + } + + private Subgraph() { + + } + + @Override + public Subgraph clone() { + Subgraph clone = new Subgraph(); + clone.g = g.clone(); + + 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(); + clone.ID = new HashMap(); + clone.ED = new HashMap(); + + clone.computeGain(); + + return clone; + } + + public UndirectedGraph createInducedSubgraph() { + return FilterUtils.createInducedSubgraph(nodes,g); + } +} Index: src/main/java/weka/clusterers/forMetisMQI/graph/UndirectedGraph.java =================================================================== --- src/main/java/weka/clusterers/forMetisMQI/graph/UndirectedGraph.java (revision 11) +++ src/main/java/weka/clusterers/forMetisMQI/graph/UndirectedGraph.java (revision 11) @@ -0,0 +1,125 @@ +package weka.clusterers.forMetisMQI.graph; + +import java.util.ArrayList; +import java.util.Collection; +import java.util.Iterator; +import java.util.List; + +import weka.clusterers.forMetisMQI.Random; +import weka.core.Attribute; +import weka.core.Instance; +import weka.core.Instances; +import edu.uci.ics.jung.graph.UndirectedSparseGraph; +import edu.uci.ics.jung.graph.util.Pair; + +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; + } + + 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(); + } + +}