Changeset 11 for src/main/java/weka/clusterers/forMetisMQI/graph

Timestamp:

Sep 16, 2010, 10:44:40 AM (14 years ago)

Author:

gnappo

Message:

Un po' di refactoring e implementazione dell'algoritmo di raffinamento.

Location:

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

Files:

• . (added)
• Bisection.java (moved) (moved from src/main/java/weka/clusterers/forMetisMQI/KLPartition.java) (6 diffs)
• Edge.java (moved) (moved from src/main/java/weka/clusterers/forMetisMQI/Edge.java) (2 diffs)
• Node.java (moved) (moved from src/main/java/weka/clusterers/forMetisMQI/Node.java) (1 diff)
• Subgraph.java (moved) (moved from src/main/java/weka/clusterers/forMetisMQI/Subgraph.java) (5 diffs)
• UndirectedGraph.java (moved) (moved from src/main/java/weka/clusterers/forMetisMQI/UndirectedGraph.java) (3 diffs)

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

@@ -1 @@
-package weka.clusterers.forMetisMQI;
+package weka.clusterers.forMetisMQI.graph;
 
 import java.util.HashSet;
@@ -6 +6 @@
 
 
-public class KLPartition {
+
+public class Bisection {
         
         private Subgraph a = null;
@@ -13 +14 @@
         
         private Set<Node> marked = null;
+        
+        private UndirectedGraph g = null;
 
-        private KLPartition() {
+        private Bisection() {
         }
         
-        public KLPartition(Subgraph s) {
-                UndirectedGraph g  = s.getGraph();
+        /**
+         * Initialize the bisection with a given subgraph.
+         * @param s
+         */
+        public Bisection(Subgraph s) {
+                g  = s.getGraph();
                 a = s;
                 b = new Subgraph(g);
@@ -30 +37 @@
         }
         
-        public KLPartition(UndirectedGraph g){
+        /**
+         * Creates a bisection choosing randomly the nodes for each subgraph.
+         * @param g
+         */
+        public Bisection(UndirectedGraph g){
+                this.g = g;
                 a = new Subgraph(g);
                 b = new Subgraph(g);
@@ -44 +56 @@
                 }
                 marked = new HashSet<Node>();
+        }
+        
+        public UndirectedGraph getGraph() {
+                return g;
         }
         
@@ -106 +122 @@
         }
         
-        public KLPartition copy(){
-                KLPartition clone = new KLPartition();
+        public Bisection copy(){
+                Bisection clone = new Bisection();
                 clone.a = (Subgraph) a.clone();
                 clone.b = (Subgraph) b.clone();

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

@@ -1 @@
-package weka.clusterers.forMetisMQI;
+package weka.clusterers.forMetisMQI.graph;
 
 public class Edge {
@@ -48 +48 @@
         @Override
         public String toString() {
-                return "E" + id + " w:" + weight;
+                return Integer.toString(capacity);
         }
 

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

@@ -1 @@
-package weka.clusterers.forMetisMQI;
+package weka.clusterers.forMetisMQI.graph;
 
 

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

@@ -1 @@
-package weka.clusterers.forMetisMQI;
+package weka.clusterers.forMetisMQI.graph;
 
 import java.util.ArrayList;
@@ -11 +11 @@
 import java.util.Map.Entry;
 
+import edu.uci.ics.jung.algorithms.filters.FilterUtils;
+
+
 public class Subgraph {
         
@@ -17 +20 @@
         private Set<Node> nodes = null;
         
-//      private BitSet nodes = null;
-//      private List<Integer> listOfNodes = null;
         private HashMap<Node,Integer> ID = null;
         private HashMap<Node,Integer> ED = null;
@@ -34 +35 @@
         }
         
+        public Subgraph(UndirectedGraph g, Set<Node> nodes) {
+                this.g = g;
+                this.nodes = new HashSet<Node>();
+                this.ID = new HashMap<Node,Integer>();
+                this.ED = new HashMap<Node,Integer>();
+                this.bucketGain = new HashMap<Integer, List<Node>>();
+                this.gainSet = new TreeSet<Integer>();
+                Iterator<Node> nodesIterator = nodes.iterator();
+                while(nodesIterator.hasNext()) {
+                        addVertex(nodesIterator.next());
+                }
+        }
+        
         public UndirectedGraph getGraph() {
                 return g;
         }
         
+        /**
+         * Adds to the subgraph the node u iff u belongs to the graph.
+         * @param u
+         */
         public void addVertex(Node u) {
-                nodes.add(u);
-                ID.put(u, 0);
-                ED.put(u, 0);
-                recomputeGain = true;
+                if(g.containsVertex(u)) {
+                        nodes.add(u);
+                        ID.put(u, 0);
+                        ED.put(u, 0);
+                        recomputeGain = true;
+                }
         }
         
@@ -233 +253 @@
                 return clone;
         }
+        
+        public UndirectedGraph createInducedSubgraph() {
+                return FilterUtils.createInducedSubgraph(nodes,g);
+        }
 }

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

@@ -1 @@
-package weka.clusterers.forMetisMQI;
+package weka.clusterers.forMetisMQI.graph;
 
 import java.util.ArrayList;
@@ -6 +6 @@
 import java.util.List;
 
+import weka.clusterers.forMetisMQI.Random;
 import weka.core.Attribute;
 import weka.core.Instance;
@@ -89 +90 @@
                         g.addVertex(nodesIterator.next().clone());
                 }
-                
                 Iterator<Edge> edgesIterator = getEdges().iterator();
                 while(edgesIterator.hasNext()) {