Changeset 8

Timestamp:

Sep 11, 2010, 4:12:16 PM (14 years ago)

Author:

gnappo

Message:

Aggiunta la libreria Jung per lavorare con i grafi. Primi esperimenti. A breve riorganizzazione completa del codice per usufruire della libreria.

Files:

• lib/collections-generic-4.01.jar (added)
• lib/colt-1.2.0.jar (added)
• lib/concurrent-1.3.4.jar (added)
• lib/j3d-core-1.3.1.jar (added)
• lib/jung-3d-2.0.1.jar (added)
• lib/jung-3d-demos-2.0.1.jar (added)
• lib/jung-algorithms-2.0.1.jar (added)
• lib/jung-api-2.0.1.jar (added)
• lib/jung-graph-impl-2.0.1.jar (added)
• lib/jung-io-2.0.1.jar (added)
• lib/jung-jai-2.0.1.jar (added)
• lib/jung-jai-samples-2.0.1.jar (added)
• lib/jung-samples-2.0.1.jar (added)
• lib/jung-visualization-2.0.1.jar (added)
• lib/jung2-2_0_1.zip (added)
• lib/stax-api-1.0.1.jar (added)
• lib/vecmath-1.3.1.jar (added)
• lib/wstx-asl-3.2.6.jar (added)
• src/main/java/weka/clusterers/forMetisMQI/Coarse.java (modified) (5 diffs)
• src/main/java/weka/clusterers/forMetisMQI/Edge.java (added)
• src/main/java/weka/clusterers/forMetisMQI/GraphAlgorithms.java (modified) (2 diffs)
• src/main/java/weka/clusterers/forMetisMQI/KLPartition.java (modified) (1 diff)
• src/main/java/weka/clusterers/forMetisMQI/MQI.java (added)
• src/main/java/weka/clusterers/forMetisMQI/Node.java (added)
• src/main/java/weka/clusterers/forMetisMQI/Subgraph.java (modified) (2 diffs)

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

@@ -13 +13 @@
         private static boolean debug = true;
         private static PrintStream debugStream = System.err;
-        private static int nodesContracted = 5;
+        private static int finerSize = 5;
 
         /**
@@ -61 +61 @@
                                         map.set(g.getIndex(matchedNode), labelCounter);
                                         if(debug) debugStream.println("Contracting node " + u + " with " + matchedNode + ". Node id: " + getMappedNode(g, map, u));
-                                } else
+                                } else {
                                         map.set(g.getIndex(u), labelCounter);
+                                        if(debug) debugStream.println("Node " + u + " with " + " new node id: " + getMappedNode(g, map, u));
+                                }
                                 labelCounter++;
                         }
@@ -106 +108 @@
                 //calcolo dei pesi del nuovo grafo: per ogni arco (u,v) && u < v.
                 //w(map(u),map(v)) += w(u,v). 
-                for(int u=0; u < g.size(); u++) {
+                for(int i=0; i < g.size(); i++) {
+                        int u = g.getLabel(i);
                         Iterator<Integer> it = g.getNeighbors(u).iterator();
                         while(it.hasNext()) {
@@ -115 +118 @@
                         }
                 }
-                for(int u = 0; u < g.size(); u++) {
+                for(int i=0; i < g.size(); i++) {
+                        int u = g.getLabel(i);
                         if(isMatched(g,match,u)) {
                                 int v = getMatchedNode(g,match,u);
@@ -159 +163 @@
                 if(debug)
                         debugStream.println("-----------------------------------------------------");
-            } while(e.getProjected().size() > e.getContracted().size() && e.getContracted().size() > nodesContracted);
+            } while(e.getProjected().size() > e.getContracted().size() && e.getContracted().size() > finerSize);
             return stack;
         }
+
+        public static void setFinerSize(int i) {
+                finerSize = i;
+        }
 }

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

@@ -23 +23 @@
         public void METIS(Graph g) {
                 KLPartition partition = null;
+                Coarse.setFinerSize(10);
                 Stack<CoarserGraphElement> stack = Coarse.coarse(g);
                 
@@ -32 +33 @@
                 }
                 
+                MQI.start(partition);
+                
         }
 

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

@@ -33 +33 @@
                 a = new Subgraph(g);
                 b = new Subgraph(g);
-                Random r = Random.instance();
-                for(int i=0;i<g.size();i++) {
-                        if(r.nextBoolean())
-                                a.addNode(g.getLabel(i));
+                Iterator<Integer> graph = g.vtxsPermutation().iterator();
+                int i = 0;
+                while(graph.hasNext()) {
+                        int u = graph.next();
+                        if((i%2)==0)
+                                a.addNode(u);
                         else
-                                b.addNode(g.getLabel(i));
+                                b.addNode(u);
+                        i++;
                 }
                 marked = new ArrayList<Integer>();

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

@@ -9 +9 @@
 import java.util.TreeSet;
 import java.util.Map.Entry;
-
-import weka.clusterers.forMetisMQI.Graph.NodeInfo;
 
 public class Subgraph {
@@ -134 +132 @@
         }
         
+        public int getWeight(int u, int v) {
+                int ret = -1;
+                if(isEdge(u,v))
+                        ret = g.getWeight(u, v);
+                return ret;
+        }
+        
         public Iterator<Integer> iterator() {
                 return listOfNodes.iterator();