Changeset 15

Timestamp:

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

Author:

gnappo

Message:

Individuazione del miglioramento del taglio: tentativi.

Location:

src/main/java/weka/clusterers/forMetisMQI

Files:

• GraphAlgorithms.java (modified) (1 diff)
• MQI.java (modified) (7 diffs)
• graph/Bisection.java (modified) (1 diff)
• graph/Edge.java (modified) (1 diff)
• graph/Subgraph.java (modified) (1 diff)
• util/Util.java (modified) (1 diff)

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

@@ -57 +57 @@
         static public Set<Set<Node>> metisMqi(UndirectedGraph g, int numberOfCluster, int sizeFinerGraph) {
                 Set<Set<Node>> clusters = new HashSet<Set<Node>>();
+                Util.viewGraph(g);
                 for (int i = 0; i < numberOfCluster; i++) {
                         Bisection partition = metis(g,sizeFinerGraph);
                         Set<Node> cluster = MQI.mqi(partition);
                         clusters.add(cluster);
+                        System.out.println("CLUSTER "+ i + ": " + cluster);
                 }
                 return clusters;

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;

src/main/java/weka/clusterers/forMetisMQI/graph/Bisection.java

@@ -139 +139 @@
         
         /**
-         * 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;

src/main/java/weka/clusterers/forMetisMQI/graph/Edge.java

@@ -28 +28 @@
                         Edge e = (Edge) o;
                         result = result && (e.getId().equals(id));
-                        result = result && (e.getWeight() == weight);
-                        result = result && (e.getCapacity() == capacity);
                 }
                 return result;

src/main/java/weka/clusterers/forMetisMQI/graph/Subgraph.java

@@ -204 +204 @@
         @Override
         public String toString() {
-                String out = "[";
+                if(getVertexCount() == 0)
+                        return "[]";
+                StringBuffer out =new StringBuffer("[");
                 Iterator<Node> 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();
         }
         

src/main/java/weka/clusterers/forMetisMQI/util/Util.java

@@ -91 +91 @@
                 vv.getRenderContext().setVertexLabelTransformer(new ToStringLabeller<Node>());
                 vv.getRenderContext().setEdgeLabelTransformer(new ToStringLabeller<Edge>());
-
+                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<Node, Edge> g, Map<Edge, Number> edgeFlowMap){
+                class EdgeTransformer implements Transformer<Edge,String> {
+                        Map<Edge,Number> edgeFlowMap = null;
+                        public String transform(Edge edge){
+                                return edgeFlowMap.get(edge) + "/" + edge.getCapacity();
+                        }
+                        public EdgeTransformer(Map<Edge,Number> edgeFlowMap) {
+                                this.edgeFlowMap = edgeFlowMap;
+                        }
+                }
+                Layout<Node, Edge> layout = new FRLayout<Node, Edge>(g);
+                layout.setSize(new Dimension(800,600)); // sets the initial size of the space
+                // The BasicVisualizationServer<V,E> is parameterized by the edge types
+                BasicVisualizationServer<Node,Edge> vv =
+                new BasicVisualizationServer<Node,Edge>(layout);
+                vv.setPreferredSize(new Dimension(800,600)); //Sets the viewing area size
+                vv.getRenderContext().setVertexLabelTransformer(new ToStringLabeller<Node>());
+                vv.getRenderContext().setEdgeLabelTransformer(new EdgeTransformer(edgeFlowMap));
                 JFrame frame = new JFrame("Simple Graph View");
                 frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);