Changeset 20

Timestamp:

Sep 30, 2010, 5:33:45 PM (14 years ago)

Author:

gnappo

Message:

Aggiunto metodo per stampare i grafi in formato utile per kmetis; modificato politica di azione di mqi, ora agisce sulla partizione piu` grande.

Location:

src/main/java/weka/clusterers/forMetisMQI

Files:

• GraphAlgorithms.java (modified) (4 diffs)
• MQI.java (modified) (7 diffs)
• graph/Bisection.java (modified) (1 diff)
• graph/UndirectedGraph.java (modified) (2 diffs)

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

@@ -81 +81 @@
          */
         static public Set<Set<Node>> metisMqi(UndirectedGraph g, int numberOfCluster, int sizeFinerGraph) {
-                System.out.println("VERTEX: " + g.getVertexCount());
-                System.out.println("EDGE: " + g.getEdgeCount());
+                System.out.println("Vertex count: " + g.getVertexCount());
+                System.out.println("Edges count: " + g.getEdgeCount());
                 Iterator<Node> iNodes = g.getVertices().iterator();
                 int degreeCounter = 0;
@@ -95 +95 @@
 //              Util.viewGraph(g);
                 for (int i = 0; i < numberOfCluster; i++) {
-                        Bisection partition = metis(g,sizeFinerGraph);
-                        System.out.println("Partizione iniziale (Metis)");
-//                      System.out.println("Edge-cut: " + partition.edgeCut() / 2);
+//                      Bisection partition = metis(g,sizeFinerGraph);
+                        Bisection partition = new Bisection(g);
+                        System.out.print("Partizione iniziale: ");
+                        System.out.print("V1: " + partition.getSubgraph().getVertexCount());
+                        System.out.print(" V2: " + partition.getComplement().getVertexCount());
+                        System.out.println(" EC: " + partition.edgeCut() * 0.5);
                         System.out.println("Conductance: " + 
                                         ((double)partition.edgeCut() / 2) / Math.min(partition.getSubgraph().totalDegree(),partition.getComplement().totalDegree()));
@@ -107 +110 @@
                         Bisection mqiBisection = new Bisection(new Subgraph(g,cluster));
                         System.out.println("Partizione raffinata (MQI)");
-//                      System.out.println("Edge-cut: " + mqiBisection.edgeCut() / 2);
                         double newConductance = ((double)mqiBisection.edgeCut() / 2) / Math.min(mqiBisection.getSubgraph().totalDegree(),mqiBisection.getComplement().totalDegree());
                         System.out.println("Conductance: " + newConductance);
@@ -117 +119 @@
                         }
                         
+                        System.out.println();
                         Iterator<Node> clustersNode = cluster.iterator();
                         while(clustersNode.hasNext()){

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

@@ -81 +81 @@
 
         static private DirectedGraph<Node, Edge> prepareDirectedGraph(
-                        Bisection partition, Node source, Node sink, boolean forConductance) {
-                Subgraph A = null;
-                Subgraph B = null;
-                if (partition.getSubgraph().getVertexCount() < partition
-                                .getComplement().getVertexCount()) {
-                        A = partition.getSubgraph();
-                        B = partition.getComplement();
-                } else {
-                        A = partition.getComplement();
-                        B = partition.getSubgraph();
-                }
+                        Bisection bisection, Node source, Node sink, boolean forConductance) {
+                Subgraph A = bisection.getLargerSubgraph();
+                Subgraph B = bisection.getSmallerSubgraph();
                 int a = 0;
                 if (!forConductance)
@@ -98 +90 @@
                         Iterator<Node> aIterator = A.iterator();
                         while(aIterator.hasNext()) {
-                                a += partition.getGraph().degree(aIterator.next());
-                        }
-                }
-                int c = partition.edgeCut() / 2;
+                                a += bisection.getGraph().degree(aIterator.next());
+                        }
+                }
+                int c = bisection.edgeCut() / 2;
 
                 DirectedGraph<Node, Edge> g = new DirectedSparseGraph<Node, Edge>();
@@ -109 +101 @@
                         g.addVertex(u);
                 }
-
                 nodes = A.iterator();
                 int id = 0;
@@ -153 +144 @@
                         if(forConductance)
                                 //FIXME: CONTROLLAMI
-                                g.addEdge(new Edge(Integer.toString(id), 1, c * partition.getGraph().degree(u)), u, sink);
+                                g.addEdge(new Edge(Integer.toString(id), 1, c * bisection.getGraph().degree(u)), u, sink);
                         else
                                 g.addEdge(new Edge(Integer.toString(id), 1, c), u, sink);
@@ -173 +164 @@
                 boolean finished = false;
                 Bisection bisection = partition;
-                Set<Node> cluster = new HashSet<Node>(partition.getSmallerNotEmptySubgraph()
+                Set<Node> cluster = new HashSet<Node>(partition.getLargerSubgraph()
                                 .createInducedSubgraph().getVertices());
                 int maxFlowThreshold = Integer.MAX_VALUE;
@@ -200 +191 @@
 
                         if (!forConductance)
-                                maxFlowThreshold = bisection.getSmallerNotEmptySubgraph()
+                                maxFlowThreshold = bisection.getLargerSubgraph()
                                                 .getVertexCount()
                                                 * bisection.edgeCut() / 2;
                         else {
-                                Iterator<Node> aIterator = bisection.getSmallerNotEmptySubgraph().iterator();
+                                Iterator<Node> aIterator = bisection.getLargerSubgraph().iterator();
                                 maxFlowThreshold = 0;
                                 while(aIterator.hasNext())
@@ -212 +203 @@
                         }
                         alg.evaluate();
-//                       Util.viewFlowGraph(directedGraph, edgeFlowMap);
-//                      System.out.println("MAX FLOW: " + alg.getMaxFlow() + " THRESHOLD: "
-//                                      + maxFlowThreshold);
+//                      Util.viewFlowGraph(directedGraph, edgeFlowMap);
+                        System.out.println("MAX FLOW: " + alg.getMaxFlow() + " THRESHOLD: "
+                                        + maxFlowThreshold);
                         if (alg.getMaxFlow() < maxFlowThreshold) {
                                 Set<Node> dfsResult = DFSReversed(sink, directedGraph,
                                                 edgeFlowMap, new HashSet<Node>());
                                 dfsResult.remove(sink);
-//                              if (dfsResult.size() > 0) {
-                                        cluster = dfsResult;
-                                        bisection = new Bisection(new Subgraph(
-                                                        bisection.getGraph(), cluster));
-//                                      System.out
-//                                                      .println("NEW BISECTION: " + bisection.toString());
-//                              } else
-//                                      finished = true;
+                                cluster = dfsResult;
+                                bisection = new Bisection(new Subgraph(
+                                        bisection.getGraph(), cluster));
                         } else
                                 finished = true;

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

@@ -139 +139 @@
         }
         
+        public Subgraph getLargerSubgraph() {
+                if(a.getVertexCount() < b.getVertexCount())
+                        return b;
+                else
+                        return a;
+        }
+        
         /**
-         * Returns the smaller not empty subgraph of this bisection, null otherwise.
+         * Returns the smaller subgraph of this bisection, null otherwise.
          * @return
          */
-        public Subgraph getSmallerNotEmptySubgraph() {
-                if(a.getVertexCount() > 0 && b.getVertexCount() == 0)
-                        return a;
-                if(b.getVertexCount() > 0 && a.getVertexCount() == 0)
-                        return b;
+        public Subgraph getSmallerSubgraph() {
                 if(a.getVertexCount() < b.getVertexCount())
                         return a;

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

@@ -1 +1 @@
 package weka.clusterers.forMetisMQI.graph;
 
+import java.io.PrintStream;
 import java.util.ArrayList;
 import java.util.Collection;
+import java.util.HashMap;
 import java.util.Iterator;
 import java.util.List;
+import java.util.TreeMap;
 
 import weka.clusterers.forMetisMQI.Random;
@@ -109 +112 @@
         }
         
+        public void printForMetis(PrintStream output) {
+                TreeMap<Integer,Node> map = new TreeMap<Integer,Node>();
+                HashMap<Node,Integer> reverseMap = new HashMap<Node,Integer>();
+                Iterator<Node> nodesIterator = getVertices().iterator();
+                int id = 1;
+                while(nodesIterator.hasNext()) {
+                        Node node = nodesIterator.next();
+                        map.put(id, node);
+                        reverseMap.put(node,id);
+                        id++;
+                }
+                output.println(getVertexCount() + " "+ getEdgeCount());
+                Iterator<Integer> mappedIterator = map.keySet().iterator();
+                while(mappedIterator.hasNext()) {
+                        id = mappedIterator.next();
+                        Iterator<Node> neighbors = getNeighbors(map.get(id)).iterator();
+                        while(neighbors.hasNext()){
+                                output.print(reverseMap.get(neighbors.next()));
+                                if(neighbors.hasNext()) output.print(" ");
+                        }
+                        output.println();
+                }
+        }
+        
         public String toString() {
                 StringBuffer sb = new StringBuffer("Vertices:");