Index: src/main/java/weka/clusterers/forMetisMQI/GraphAlgorithms.java =================================================================== --- src/main/java/weka/clusterers/forMetisMQI/GraphAlgorithms.java (revision 15) +++ src/main/java/weka/clusterers/forMetisMQI/GraphAlgorithms.java (revision 16) @@ -64,4 +64,5 @@ System.out.println("CLUSTER "+ i + ": " + cluster); } + Util.viewClusters(g, clusters); return clusters; } Index: src/main/java/weka/clusterers/forMetisMQI/MQI.java =================================================================== --- src/main/java/weka/clusterers/forMetisMQI/MQI.java (revision 15) +++ src/main/java/weka/clusterers/forMetisMQI/MQI.java (revision 16) @@ -23,34 +23,41 @@ public class MQI { - + static int i = -1; - - static private Set reversedLookup(Node sink, DirectedGraph g, Map edgeFlowMap) { + + static private Set DFSReversed(Node currentNode, + DirectedGraph g, Map edgeFlowMap, Set marked) { + Collection inEdges = g.getInEdges(currentNode); Set result = new HashSet(); - Collection inEdges = g.getInEdges(sink); + result.add(currentNode); 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); + Edge reverseEdge = g.findEdge(src, currentNode); + if (reverseEdge != null && !marked.contains(src)) { + int flow = (Integer) edgeFlowMap.get(reverseEdge); + int capacity = reverseEdge.getCapacity(); + if (flow < capacity) { + marked.add(src); + result.addAll(DFSReversed(src, g, edgeFlowMap, marked)); + } } } return result; } - - static private Set DFSReversed(Node sink, DirectedGraph g, Map edgeFlowMap) { - Stack stack = new Stack(); - stack.push(sink); + + + + static private Set BFSReversed(Node sink, + DirectedGraph g, Map edgeFlowMap) { Set result = new HashSet(); - Set discardedNodes = new HashSet(); + Set visitedNodes = new HashSet(); + Stack nodesToVisit = new Stack(); result.add(sink); - while (!stack.empty()) { - boolean founded = false; - Node currentNode = stack.pop(); - discardedNodes.add(currentNode); + nodesToVisit.push(sink); + while (!nodesToVisit.empty()) { + Node currentNode = nodesToVisit.pop(); + visitedNodes.add(currentNode); Collection inEdges = g.getInEdges(currentNode); Iterator inEdgesIterator = inEdges.iterator(); @@ -59,51 +66,29 @@ 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); + if (reverseEdge != null) { + int flow = (Integer) edgeFlowMap.get(reverseEdge); + int capacity = reverseEdge.getCapacity(); + if (flow < capacity) { + if (!nodesToVisit.contains(src) + && !visitedNodes.contains(src)) { + nodesToVisit.push(src); + } + result.add(src); + } + } } } return result; } - - static private Set BFSReversed(Node sink, DirectedGraph g, Map edgeFlowMap) { - Set result = new HashSet(); - Set visitedNodes = new HashSet(); - Stack nodesToVisit = new Stack(); - result.add(sink); - nodesToVisit.push(sink); - while(!nodesToVisit.empty()) { - Node currentNode = nodesToVisit.pop(); - visitedNodes.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) && ((Integer)edgeFlowMap.get(reverseEdge) < reverseEdge.getCapacity())) { - if(!nodesToVisit.contains(src) && !visitedNodes.contains(src)) { - nodesToVisit.push(src); - } - result.add(src); - } - } - } - return result; - } - - static private DirectedGraph prepareDirectedGraph(Bisection partition, Node source, Node sink) { + + static private DirectedGraph prepareDirectedGraph( + Bisection partition, Node source, Node sink) { Subgraph A = null; Subgraph B = null; - if(partition.getSubgraph().getVertexCount() < partition.getComplement().getVertexCount()) { + if (partition.getSubgraph().getVertexCount() < partition + .getComplement().getVertexCount()) { A = partition.getSubgraph(); B = partition.getComplement(); - } - else { + } else { A = partition.getComplement(); B = partition.getSubgraph(); @@ -111,54 +96,63 @@ int a = A.getVertexCount(); int c = partition.edgeCut() / 2; - - - DirectedGraph g = new DirectedSparseGraph(); - Iterator nodes = A.iterator(); - while(nodes.hasNext()) { + + DirectedGraph g = new DirectedSparseGraph(); + Iterator nodes = A.iterator(); + while (nodes.hasNext()) { Node u = nodes.next(); g.addVertex(u); } - - nodes = A.iterator(); + + nodes = A.iterator(); int id = 0; - while(nodes.hasNext()) { + while (nodes.hasNext()) { Node u = nodes.next(); Iterator neighbors = A.getNeighbors(u).iterator(); - while(neighbors.hasNext()) { + while (neighbors.hasNext()) { Node v = neighbors.next(); - g.addEdge(new Edge(Integer.toString(id),A.getWeight(u, v),a),u,v); + g.addEdge(new Edge(Integer.toString(id), A.getWeight(u, v), a), + u, v); id++; } } - + g.addVertex(source); g.addVertex(sink); + - - nodes = B.iterator(); - while(nodes.hasNext()) { + //build the edges from source to each node of A which previously was connected + //with a node of B. + nodes = B.iterator(); + while (nodes.hasNext()) { Node u = nodes.next(); Iterator neighbors = B.getGraph().getNeighbors(u).iterator(); - while(neighbors.hasNext()) { + while (neighbors.hasNext()) { Node v = neighbors.next(); - if(A.contains(v)) { - g.addEdge(new Edge(Integer.toString(id),1,a),source,v); - id++; - } - } - } - - nodes = A.iterator(); - while(nodes.hasNext()) { - Node u = nodes.next(); - g.addEdge(new Edge(Integer.toString(id),1,c),u,sink); + if (A.contains(v)) { + Edge e = g.findEdge(source, v); + if(e != null) { + e.setCapacity(e.getCapacity() + a); + } else { + g.addEdge(new Edge(Integer.toString(id), 1, a), source, v); + id++; + } + } + } + } + + nodes = A.iterator(); + while (nodes.hasNext()) { + Node u = nodes.next(); + g.addEdge(new Edge(Integer.toString(id), 1, c), u, sink); id++; } return g; } - + /** - * Given a partion of a graph, execute the Max-Flow Quotient-cut Improvement algorithm, - * to find an improved cut and then returns the cluster which yields the best quotient cut. + * Given a partion of a graph, execute the Max-Flow Quotient-cut Improvement + * algorithm, to find an improved cut and then returns the cluster which + * yields the best quotient cut. + * * @param partition * @return @@ -168,11 +162,13 @@ boolean finished = false; Bisection bisection = partition; - Set cluster = new HashSet(partition.getSmallerNotEmptySubgraph().createInducedSubgraph().getVertices()); + Set cluster = new HashSet(partition + .getSmallerNotEmptySubgraph().createInducedSubgraph() + .getVertices()); int maxFlowThreshold = Integer.MAX_VALUE; while (!finished) { Node source = new Node("S"); Node sink = new Node("T"); - DirectedGraph directedGraph = prepareDirectedGraph(bisection, source, sink); -// Util.viewGraph(directedGraph); + DirectedGraph directedGraph = prepareDirectedGraph( + bisection, source, sink); Transformer capTransformer = new Transformer() { public Double transform(Edge e) { @@ -181,5 +177,5 @@ }; Map edgeFlowMap = new HashMap(); - i=-1; + i = -1; // This Factory produces new edges for use by the algorithm Factory edgeFactory = new Factory() { @@ -190,18 +186,19 @@ }; EdmondsKarpMaxFlow alg = new EdmondsKarpMaxFlow( - directedGraph, source, sink, capTransformer, edgeFlowMap, edgeFactory); - - maxFlowThreshold = bisection.getSmallerNotEmptySubgraph().getVertexCount() * bisection.edgeCut() / 2; + directedGraph, source, sink, capTransformer, edgeFlowMap, + edgeFactory); + + 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) { -// 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); +// Util.viewFlowGraph(directedGraph, edgeFlowMap); + System.out.println("MAX FLOW: " + alg.getMaxFlow() + " THRESHOLD: " + + maxFlowThreshold); + if (alg.getMaxFlow() < maxFlowThreshold) { + cluster = DFSReversed(sink, directedGraph, edgeFlowMap, new HashSet()); cluster.remove(sink); - bisection = new Bisection(new Subgraph(bisection.getSmallerNotEmptySubgraph().createInducedSubgraph(), cluster)); + bisection = new Bisection(new Subgraph(bisection.getGraph(), + cluster)); System.out.println("NEW BISECTION: " + bisection.toString()); } else @@ -210,17 +207,4 @@ return cluster; } - - 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; - } - + }