Index: /src/main/java/weka/clusterers/forMetisMQI/GraphAlgorithms.java =================================================================== --- /src/main/java/weka/clusterers/forMetisMQI/GraphAlgorithms.java (revision 14) +++ /src/main/java/weka/clusterers/forMetisMQI/GraphAlgorithms.java (revision 15) @@ -57,8 +57,10 @@ static public Set> metisMqi(UndirectedGraph g, int numberOfCluster, int sizeFinerGraph) { Set> clusters = new HashSet>(); + Util.viewGraph(g); for (int i = 0; i < numberOfCluster; i++) { Bisection partition = metis(g,sizeFinerGraph); Set cluster = MQI.mqi(partition); clusters.add(cluster); + System.out.println("CLUSTER "+ i + ": " + cluster); } return clusters; Index: /src/main/java/weka/clusterers/forMetisMQI/MQI.java =================================================================== --- /src/main/java/weka/clusterers/forMetisMQI/MQI.java (revision 14) +++ /src/main/java/weka/clusterers/forMetisMQI/MQI.java (revision 15) @@ -1,7 +1,4 @@ package weka.clusterers.forMetisMQI; -import java.awt.Color; -import java.awt.Dimension; -import java.awt.Paint; import java.util.Collection; import java.util.HashMap; @@ -12,6 +9,4 @@ import java.util.Stack; -import javax.swing.JFrame; - import org.apache.commons.collections15.Factory; import org.apache.commons.collections15.Transformer; @@ -22,17 +17,58 @@ import weka.clusterers.forMetisMQI.graph.Subgraph; import weka.clusterers.forMetisMQI.graph.UndirectedGraph; +import weka.clusterers.forMetisMQI.util.Util; import edu.uci.ics.jung.algorithms.flows.EdmondsKarpMaxFlow; -import edu.uci.ics.jung.algorithms.layout.FRLayout; -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; -import edu.uci.ics.jung.visualization.BasicVisualizationServer; -import edu.uci.ics.jung.visualization.decorators.ToStringLabeller; public class MQI { static int i = -1; + + static private Set reversedLookup(Node sink, DirectedGraph g, Map edgeFlowMap) { + Set result = new HashSet(); + Collection inEdges = g.getInEdges(sink); + Iterator inEdgesIterator = inEdges.iterator(); + while (inEdgesIterator.hasNext()) { + Edge edge = inEdgesIterator.next(); + Node src = g.getSource(edge); + Edge reverseEdge = g.findEdge(src, sink); + if ((reverseEdge != null) + && ((Integer) edgeFlowMap.get(reverseEdge) < reverseEdge + .getCapacity())) { + result.add(src); + } + } + return result; + } + + static private Set DFSReversed(Node sink, DirectedGraph g, Map edgeFlowMap) { + Stack stack = new Stack(); + stack.push(sink); + Set result = new HashSet(); + Set discardedNodes = new HashSet(); + result.add(sink); + while (!stack.empty()) { + boolean founded = false; + Node currentNode = stack.pop(); + discardedNodes.add(currentNode); + Collection inEdges = g.getInEdges(currentNode); + Iterator inEdgesIterator = inEdges.iterator(); + while (inEdgesIterator.hasNext()) { + Edge edge = inEdgesIterator.next(); + Node src = g.getSource(edge); + Edge reverseEdge = g.findEdge(src, currentNode); + if ((reverseEdge != null) && !discardedNodes.contains(src) + && ((Integer) edgeFlowMap.get(reverseEdge) < reverseEdge + .getCapacity()) && !founded) { + founded=true; + stack.push(src); + result.add(src); + } + discardedNodes.add(src); + } + } + return result; + } static private Set BFSReversed(Node sink, DirectedGraph g, Map edgeFlowMap) { @@ -132,5 +168,5 @@ boolean finished = false; Bisection bisection = partition; - Set cluster = new HashSet(partition.getSubgraph().createInducedSubgraph().getVertices()); + Set cluster = new HashSet(partition.getSmallerNotEmptySubgraph().createInducedSubgraph().getVertices()); int maxFlowThreshold = Integer.MAX_VALUE; while (!finished) { @@ -138,4 +174,5 @@ Node sink = new Node("T"); DirectedGraph directedGraph = prepareDirectedGraph(bisection, source, sink); +// Util.viewGraph(directedGraph); Transformer capTransformer = new Transformer() { public Double transform(Edge e) { @@ -144,10 +181,10 @@ }; Map edgeFlowMap = new HashMap(); + i=-1; // 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); + return new Edge("f" + Integer.toString(i), 1, 1); } }; @@ -155,16 +192,17 @@ directedGraph, source, sink, capTransformer, edgeFlowMap, edgeFactory); - maxFlowThreshold = bisection.getSmallerSubgraph().getVertexCount() * bisection.edgeCut() / 2; + maxFlowThreshold = bisection.getSmallerNotEmptySubgraph().getVertexCount() * bisection.edgeCut() / 2; alg.evaluate(); + Util.viewFlowGraph(directedGraph, edgeFlowMap); System.out.println("MAX FLOW: " + alg.getMaxFlow() + " THRESHOLD: " + maxFlowThreshold); if(alg.getMaxFlow() < maxFlowThreshold) { - Set sinkPartition = alg.getNodesInSinkPartition(); - System.out.println(sinkPartition); - Set sourcePartition = alg.getNodesInSourcePartition(); - System.out.println(sourcePartition); - bisection = prepareBisection(bisection.getSmallerSubgraph().createInducedSubgraph(), sourcePartition, sinkPartition); -// bisection = new Bisection(new Subgraph(bisection.getSmallerSubgraph().createInducedSubgraph(), BFSReversed(sink, directedGraph, edgeFlowMap))); +// bisection = prepareBisection(bisection.getSmallerNotEmptySubgraph().createInducedSubgraph(), sourcePartition, sinkPartition); + cluster = BFSReversed(sink, directedGraph, edgeFlowMap); +// System.out.println("DFSReversed: " + DFSReversed(sink, directedGraph, edgeFlowMap)); +// bisection = new Bisection(new Subgraph(bisection.getSmallerNotEmptySubgraph().createInducedSubgraph(), DFSReversed(sink, directedGraph, edgeFlowMap))); +// cluster = reversedLookup(sink, directedGraph, edgeFlowMap); + cluster.remove(sink); + bisection = new Bisection(new Subgraph(bisection.getSmallerNotEmptySubgraph().createInducedSubgraph(), cluster)); System.out.println("NEW BISECTION: " + bisection.toString()); - cluster = sinkPartition; } else finished = true; Index: /src/main/java/weka/clusterers/forMetisMQI/graph/Bisection.java =================================================================== --- /src/main/java/weka/clusterers/forMetisMQI/graph/Bisection.java (revision 14) +++ /src/main/java/weka/clusterers/forMetisMQI/graph/Bisection.java (revision 15) @@ -139,8 +139,12 @@ /** - * Returns the smaller subgraph of this bisection. + * Returns the smaller not empty subgraph of this bisection, null otherwise. * @return */ - public Subgraph getSmallerSubgraph() { + public Subgraph getSmallerNotEmptySubgraph() { + if(a.getVertexCount() > 0 && b.getVertexCount() == 0) + return a; + if(b.getVertexCount() > 0 && a.getVertexCount() == 0) + return b; if(a.getVertexCount() < b.getVertexCount()) return a; Index: /src/main/java/weka/clusterers/forMetisMQI/graph/Edge.java =================================================================== --- /src/main/java/weka/clusterers/forMetisMQI/graph/Edge.java (revision 14) +++ /src/main/java/weka/clusterers/forMetisMQI/graph/Edge.java (revision 15) @@ -28,6 +28,4 @@ Edge e = (Edge) o; result = result && (e.getId().equals(id)); - result = result && (e.getWeight() == weight); - result = result && (e.getCapacity() == capacity); } return result; Index: /src/main/java/weka/clusterers/forMetisMQI/graph/Subgraph.java =================================================================== --- /src/main/java/weka/clusterers/forMetisMQI/graph/Subgraph.java (revision 14) +++ /src/main/java/weka/clusterers/forMetisMQI/graph/Subgraph.java (revision 15) @@ -204,12 +204,15 @@ @Override public String toString() { - String out = "["; + if(getVertexCount() == 0) + return "[]"; + StringBuffer out =new StringBuffer("["); Iterator it = nodes.iterator(); while(it.hasNext()) { Node u = it.next(); - out = out + u + ","; - } - out = out + "]"; - return out; + out.append(u.toString() + ","); + } + out.setLength(out.length() - 1); + out.append("]"); + return out.toString(); } Index: /src/main/java/weka/clusterers/forMetisMQI/util/Util.java =================================================================== --- /src/main/java/weka/clusterers/forMetisMQI/util/Util.java (revision 14) +++ /src/main/java/weka/clusterers/forMetisMQI/util/Util.java (revision 15) @@ -91,5 +91,29 @@ vv.getRenderContext().setVertexLabelTransformer(new ToStringLabeller()); vv.getRenderContext().setEdgeLabelTransformer(new ToStringLabeller()); - + JFrame frame = new JFrame("Simple Graph View"); + frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); + frame.getContentPane().add(vv); + frame.pack(); + frame.setVisible(true); + } + + public static void viewFlowGraph(Graph g, Map edgeFlowMap){ + class EdgeTransformer implements Transformer { + Map edgeFlowMap = null; + public String transform(Edge edge){ + return edgeFlowMap.get(edge) + "/" + edge.getCapacity(); + } + public EdgeTransformer(Map edgeFlowMap) { + this.edgeFlowMap = edgeFlowMap; + } + } + Layout layout = new FRLayout(g); + 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(800,600)); //Sets the viewing area size + vv.getRenderContext().setVertexLabelTransformer(new ToStringLabeller()); + vv.getRenderContext().setEdgeLabelTransformer(new EdgeTransformer(edgeFlowMap)); JFrame frame = new JFrame("Simple Graph View"); frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);