Changeset 15 for src/main/java/weka/clusterers/forMetisMQI/MQI.java

Timestamp:

Sep 17, 2010, 6:04:18 PM (14 years ago)

Author:

gnappo

Message:

Individuazione del miglioramento del taglio: tentativi.

File:

• src/main/java/weka/clusterers/forMetisMQI/MQI.java (modified) (7 diffs)

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

@@ -1 +1 @@
 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 +9 @@
 import java.util.Stack;
 
-import javax.swing.JFrame;
-
 import org.apache.commons.collections15.Factory;
 import org.apache.commons.collections15.Transformer;
@@ -22 +17 @@
 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<Node> reversedLookup(Node sink, DirectedGraph<Node, Edge> g, Map<Edge, Number> edgeFlowMap) {
+                Set<Node> result = new HashSet<Node>();
+                Collection<Edge> inEdges = g.getInEdges(sink);
+                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);
+                        }
+                }
+                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);
+                Set<Node> result = new HashSet<Node>();
+                Set<Node> discardedNodes = new HashSet<Node>();
+                result.add(sink);
+                while (!stack.empty()) {
+                        boolean founded = false;
+                        Node currentNode = stack.pop();
+                        discardedNodes.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) && !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<Node> BFSReversed(Node sink, DirectedGraph<Node, Edge> g, Map<Edge, Number> edgeFlowMap) {
@@ -132 +168 @@
                 boolean finished = false;
                 Bisection bisection = partition;
-                Set<Node> cluster = new HashSet<Node>(partition.getSubgraph().createInducedSubgraph().getVertices());
+                Set<Node> cluster = new HashSet<Node>(partition.getSmallerNotEmptySubgraph().createInducedSubgraph().getVertices());
                 int maxFlowThreshold = Integer.MAX_VALUE;
                 while (!finished) {
@@ -138 +174 @@
                         Node sink = new Node("T");
                         DirectedGraph<Node, Edge> directedGraph = prepareDirectedGraph(bisection, source, sink);
+//                      Util.viewGraph(directedGraph);
                         Transformer<Edge, Number> capTransformer = new Transformer<Edge, Number>() {
                                 public Double transform(Edge e) {
@@ -144 +181 @@
                         };
                         Map<Edge, Number> edgeFlowMap = new HashMap<Edge, Number>();
+                        i=-1;
                         // This Factory produces new edges for use by the algorithm
-                        i=-1;
                         Factory<Edge> edgeFactory = new Factory<Edge>() {
                                 public Edge create() {
                                         i++;
-                                        return new Edge(Integer.toString(i), 1, 1);
+                                        return new Edge("f" + Integer.toString(i), 1, 1);
                                 }
                         };
@@ -155 +192 @@
                                         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<Node> sinkPartition = alg.getNodesInSinkPartition();
-                                System.out.println(sinkPartition);
-                                Set<Node> 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;