Changeset 16 for src

Timestamp:

Sep 18, 2010, 12:37:10 PM (14 years ago)

Author:

gnappo

Message:

Corretta la creazione del grafo per il calcolo del flusso massimo (errore logico); implementata DFS ricorsiva sul grafo.

Location:

src/main/java/weka/clusterers/forMetisMQI

Files:

• GraphAlgorithms.java (modified) (1 diff)
• MQI.java (modified) (7 diffs)

src/main/java/weka/clusterers/forMetisMQI/GraphAlgorithms.java

@@ -64 +64 @@
                         System.out.println("CLUSTER "+ i + ": " + cluster);
                 }
+                Util.viewClusters(g, clusters);
                 return clusters;
         }

src/main/java/weka/clusterers/forMetisMQI/MQI.java

@@ -23 +23 @@
 
 public class MQI {
-        
+
         static int i = -1;
-        
-        static private Set<Node> reversedLookup(Node sink, DirectedGraph<Node, Edge> g, Map<Edge, Number> edgeFlowMap) {
+
+        static private Set<Node> DFSReversed(Node currentNode,
+                        DirectedGraph<Node, Edge> g, Map<Edge, Number> edgeFlowMap, Set<Node> marked) {
+                Collection<Edge> inEdges = g.getInEdges(currentNode);
                 Set<Node> result = new HashSet<Node>();
-                Collection<Edge> inEdges = g.getInEdges(sink);
+                result.add(currentNode);
                 Iterator<Edge> 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<Node> DFSReversed(Node sink, DirectedGraph<Node, Edge> g, Map<Edge, Number> edgeFlowMap) {
-                Stack<Node> stack = new Stack<Node>();
-                stack.push(sink);
+
+
+
+        static private Set<Node> BFSReversed(Node sink,
+                        DirectedGraph<Node, Edge> g, Map<Edge, Number> edgeFlowMap) {
                 Set<Node> result = new HashSet<Node>();
-                Set<Node> discardedNodes = new HashSet<Node>();
+                Set<Node> visitedNodes = new HashSet<Node>();
+                Stack<Node> nodesToVisit = new Stack<Node>();
                 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<Edge> inEdges = g.getInEdges(currentNode);
                         Iterator<Edge> inEdgesIterator = inEdges.iterator();
@@ -59 +66 @@
                                 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<Node> BFSReversed(Node sink, DirectedGraph<Node, Edge> g, Map<Edge, Number> edgeFlowMap) {
-                Set<Node> result = new HashSet<Node>();
-                Set<Node> visitedNodes = new HashSet<Node>();
-                Stack<Node> nodesToVisit = new Stack<Node>();
-                result.add(sink);
-                nodesToVisit.push(sink);
-                while(!nodesToVisit.empty()) {
-                        Node currentNode = nodesToVisit.pop();
-                        visitedNodes.add(currentNode);
-                        Collection<Edge> inEdges = g.getInEdges(currentNode);
-                        Iterator<Edge> 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<Node,       Edge> prepareDirectedGraph(Bisection partition, Node source, Node sink) {
+
+        static private DirectedGraph<Node, Edge> 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 +96 @@
                 int a = A.getVertexCount();
                 int c = partition.edgeCut() / 2;
-                
-                
-                DirectedGraph<Node,Edge> g = new DirectedSparseGraph<Node, Edge>();
-                Iterator<Node> nodes =  A.iterator();
-                while(nodes.hasNext()) {
+
+                DirectedGraph<Node, Edge> g = new DirectedSparseGraph<Node, Edge>();
+                Iterator<Node> 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<Node> 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<Node> 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 +162 @@
                 boolean finished = false;
                 Bisection bisection = partition;
-                Set<Node> cluster = new HashSet<Node>(partition.getSmallerNotEmptySubgraph().createInducedSubgraph().getVertices());
+                Set<Node> cluster = new HashSet<Node>(partition
+                                .getSmallerNotEmptySubgraph().createInducedSubgraph()
+                                .getVertices());
                 int maxFlowThreshold = Integer.MAX_VALUE;
                 while (!finished) {
                         Node source = new Node("S");
                         Node sink = new Node("T");
-                        DirectedGraph<Node, Edge> directedGraph = prepareDirectedGraph(bisection, source, sink);
-//                      Util.viewGraph(directedGraph);
+                        DirectedGraph<Node, Edge> directedGraph = prepareDirectedGraph(
+                                        bisection, source, sink);
                         Transformer<Edge, Number> capTransformer = new Transformer<Edge, Number>() {
                                 public Double transform(Edge e) {
@@ -181 +177 @@
                         };
                         Map<Edge, Number> edgeFlowMap = new HashMap<Edge, Number>();
-                        i=-1;
+                        i = -1;
                         // This Factory produces new edges for use by the algorithm
                         Factory<Edge> edgeFactory = new Factory<Edge>() {
@@ -190 +186 @@
                         };
                         EdmondsKarpMaxFlow<Node, Edge> alg = new EdmondsKarpMaxFlow<Node, Edge>(
-                                        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<Node>());
                                 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 +207 @@
                 return cluster;
         }
-        
-        private static Bisection prepareBisection(UndirectedGraph g, Set<Node> sourcePartition, Set<Node> 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;
-        }
-        
+
 }