Changeset 18 for src/main/java/weka/clusterers
- Timestamp:
- Sep 29, 2010, 9:13:19 AM (14 years ago)
- Location:
- src/main/java/weka/clusterers/forMetisMQI
- Files:
-
- 6 edited
Legend:
- Unmodified
- Added
- Removed
-
src/main/java/weka/clusterers/forMetisMQI/GraphAlgorithms.java
r17 r18 8 8 import weka.clusterers.forMetisMQI.graph.Bisection; 9 9 import weka.clusterers.forMetisMQI.graph.Node; 10 import weka.clusterers.forMetisMQI.graph.Subgraph; 10 11 import weka.clusterers.forMetisMQI.graph.UndirectedGraph; 11 12 import weka.clusterers.forMetisMQI.util.CoarserGraphElement; … … 14 15 public class GraphAlgorithms { 15 16 17 18 static public Bisection KLRefinement(Bisection b) { 19 int remainingNumberOfSwap = 50; 20 Bisection partition = b; 21 Bisection result = partition; 22 int bestEdgeCut = partition.edgeCut(); 23 Node u = partition.getCandidate(); 24 while (u != null && remainingNumberOfSwap > 0) { 25 partition.swap(u); 26 if (partition.edgeCut() <= bestEdgeCut) { 27 bestEdgeCut = partition.edgeCut(); 28 result = partition.clone(); 29 remainingNumberOfSwap = 50; 30 } else 31 remainingNumberOfSwap--; 32 u = partition.getCandidate(); 33 } 34 return result; 35 } 36 16 37 17 38 /** … … 22 43 */ 23 44 static public Bisection KL(UndirectedGraph g) { 45 int remainingNumberOfSwap = 50; 24 46 Bisection partition = new Bisection(g); 25 47 Bisection result = partition; 26 int bestEdgeCut = Integer.MAX_VALUE;48 int bestEdgeCut = partition.edgeCut(); 27 49 Node u = partition.getCandidate(); 28 while (u != null ) {50 while (u != null && remainingNumberOfSwap > 0) { 29 51 partition.swap(u); 30 52 if (partition.edgeCut() <= bestEdgeCut) { 31 53 bestEdgeCut = partition.edgeCut(); 32 result = partition.copy(); 33 } 54 result = partition.clone(); 55 remainingNumberOfSwap = 50; 56 } else 57 remainingNumberOfSwap--; 34 58 u = partition.getCandidate(); 35 59 } … … 57 81 */ 58 82 static public Set<Set<Node>> metisMqi(UndirectedGraph g, int numberOfCluster, int sizeFinerGraph) { 83 System.out.println("VERTEX: " + g.getVertexCount()); 84 System.out.println("EDGE: " + g.getEdgeCount()); 85 Iterator<Node> iNodes = g.getVertices().iterator(); 86 int degreeCounter = 0; 87 while(iNodes.hasNext()) { 88 Node node = iNodes.next(); 89 if(g.degree(node) == 1) { 90 degreeCounter++; 91 } 92 } 59 93 Set<Set<Node>> clusters = new HashSet<Set<Node>>(); 60 94 UndirectedGraph gclone = g.clone(); … … 62 96 for (int i = 0; i < numberOfCluster; i++) { 63 97 Bisection partition = metis(g,sizeFinerGraph); 64 Set<Node> cluster = MQI.mqi(partition); 98 System.out.println("Partizione iniziale (Metis)"); 99 // System.out.println("Edge-cut: " + partition.edgeCut() / 2); 100 System.out.println("Conductance: " + 101 ((double)partition.edgeCut() / 2) / Math.min(partition.getSubgraph().totalDegree(),partition.getComplement().totalDegree())); 102 Set<Node> cluster = MQI.mqi(partition,true); 103 104 UndirectedGraph clusterGraph = new Subgraph(gclone,cluster).createInducedSubgraph(); 105 106 // System.out.println(cluster); 107 Bisection mqiBisection = new Bisection(new Subgraph(g,cluster)); 108 System.out.println("Partizione raffinata (MQI)"); 109 // System.out.println("Edge-cut: " + mqiBisection.edgeCut() / 2); 110 double newConductance = ((double)mqiBisection.edgeCut() / 2) / Math.min(mqiBisection.getSubgraph().totalDegree(),mqiBisection.getComplement().totalDegree()); 111 System.out.println("Conductance: " + newConductance); 112 113 114 if(newConductance < 1) { 115 System.out.println("CLUSTER "+ i + ": V=" + clusterGraph.getVertexCount() + ", E=" + clusterGraph.getEdgeCount()+"."); 116 clusters.add(cluster); 117 } 118 65 119 Iterator<Node> clustersNode = cluster.iterator(); 66 120 while(clustersNode.hasNext()){ 67 121 g.removeVertex(clustersNode.next()); 68 122 } 69 70 71 if(cluster.size()>10) {72 clusters.add(cluster);73 }74 System.out.println("CLUSTER "+ i + ": " + cluster);75 123 } 76 124 Util.viewClusters(gclone, clusters); -
src/main/java/weka/clusterers/forMetisMQI/MQI.java
r17 r18 16 16 import weka.clusterers.forMetisMQI.graph.Node; 17 17 import weka.clusterers.forMetisMQI.graph.Subgraph; 18 import weka.clusterers.forMetisMQI.graph.UndirectedGraph;19 18 import weka.clusterers.forMetisMQI.util.Util; 20 19 import edu.uci.ics.jung.algorithms.flows.EdmondsKarpMaxFlow; … … 27 26 28 27 static private Set<Node> DFSReversed(Node currentNode, 29 DirectedGraph<Node, Edge> g, Map<Edge, Number> edgeFlowMap, Set<Node> marked) { 28 DirectedGraph<Node, Edge> g, Map<Edge, Number> edgeFlowMap, 29 Set<Node> marked) { 30 30 Collection<Edge> inEdges = g.getInEdges(currentNode); 31 31 Set<Node> result = new HashSet<Node>(); … … 47 47 return result; 48 48 } 49 50 51 49 52 50 static private Set<Node> BFSReversed(Node sink, … … 83 81 84 82 static private DirectedGraph<Node, Edge> prepareDirectedGraph( 85 Bisection partition, Node source, Node sink ) {83 Bisection partition, Node source, Node sink, boolean forConductance) { 86 84 Subgraph A = null; 87 85 Subgraph B = null; … … 94 92 B = partition.getSubgraph(); 95 93 } 96 int a = A.getVertexCount(); 94 int a = 0; 95 if (!forConductance) 96 a = A.getVertexCount(); 97 else { 98 Iterator<Node> aIterator = A.iterator(); 99 while(aIterator.hasNext()) { 100 a += partition.getGraph().degree(aIterator.next()); 101 } 102 } 97 103 int c = partition.edgeCut() / 2; 98 104 … … 120 126 g.addVertex(sink); 121 127 122 123 // build the edges from source to each node of A which previously wasconnected124 // with a node of B.128 // build the edges from source to each node of A which previously was 129 // connected 130 // with a node of B. 125 131 nodes = B.iterator(); 126 132 while (nodes.hasNext()) { … … 131 137 if (A.contains(v)) { 132 138 Edge e = g.findEdge(source, v); 133 if (e != null) {139 if (e != null) { 134 140 e.setCapacity(e.getCapacity() + a); 135 141 } else { 136 g.addEdge(new Edge(Integer.toString(id), 1, a), source, v); 142 g.addEdge(new Edge(Integer.toString(id), 1, a), source, 143 v); 137 144 id++; 138 145 } … … 144 151 while (nodes.hasNext()) { 145 152 Node u = nodes.next(); 146 g.addEdge(new Edge(Integer.toString(id), 1, c), u, sink); 153 if(forConductance) 154 //FIXME: CONTROLLAMI 155 g.addEdge(new Edge(Integer.toString(id), 1, c * partition.getGraph().degree(u)), u, sink); 156 else 157 g.addEdge(new Edge(Integer.toString(id), 1, c), u, sink); 147 158 id++; 148 159 } … … 158 169 * @return 159 170 */ 160 static public Set<Node> mqi(Bisection partition ) {171 static public Set<Node> mqi(Bisection partition, boolean forConductance) { 161 172 // System.out.println("INITIAL BISECTION: " + partition.toString()); 162 173 boolean finished = false; 163 174 Bisection bisection = partition; 164 Set<Node> cluster = new HashSet<Node>(partition 165 .getSmallerNotEmptySubgraph().createInducedSubgraph() 166 .getVertices()); 175 Set<Node> cluster = new HashSet<Node>(partition.getSmallerNotEmptySubgraph() 176 .createInducedSubgraph().getVertices()); 167 177 int maxFlowThreshold = Integer.MAX_VALUE; 168 178 while (!finished) { … … 170 180 Node sink = new Node("$$$$T"); 171 181 DirectedGraph<Node, Edge> directedGraph = prepareDirectedGraph( 172 bisection, source, sink );182 bisection, source, sink, true); 173 183 Transformer<Edge, Number> capTransformer = new Transformer<Edge, Number>() { 174 184 public Double transform(Edge e) { … … 189 199 edgeFactory); 190 200 191 maxFlowThreshold = bisection.getSmallerNotEmptySubgraph() 192 .getVertexCount() 193 * bisection.edgeCut() / 2; 201 if (!forConductance) 202 maxFlowThreshold = bisection.getSmallerNotEmptySubgraph() 203 .getVertexCount() 204 * bisection.edgeCut() / 2; 205 else { 206 Iterator<Node> aIterator = bisection.getSmallerNotEmptySubgraph().iterator(); 207 maxFlowThreshold = 0; 208 while(aIterator.hasNext()) 209 maxFlowThreshold += partition.getGraph().degree(aIterator.next()); 210 maxFlowThreshold = maxFlowThreshold 211 * (bisection.edgeCut() / 2); 212 } 194 213 alg.evaluate(); 195 // Util.viewFlowGraph(directedGraph, edgeFlowMap);214 // Util.viewFlowGraph(directedGraph, edgeFlowMap); 196 215 // System.out.println("MAX FLOW: " + alg.getMaxFlow() + " THRESHOLD: " 197 216 // + maxFlowThreshold); 198 217 if (alg.getMaxFlow() < maxFlowThreshold) { 199 cluster = DFSReversed(sink, directedGraph, edgeFlowMap, new HashSet<Node>()); 200 cluster.remove(sink); 201 bisection = new Bisection(new Subgraph(bisection.getGraph(), 202 cluster)); 203 // System.out.println("NEW BISECTION: " + bisection.toString()); 218 Set<Node> dfsResult = DFSReversed(sink, directedGraph, 219 edgeFlowMap, new HashSet<Node>()); 220 dfsResult.remove(sink); 221 // if (dfsResult.size() > 0) { 222 cluster = dfsResult; 223 bisection = new Bisection(new Subgraph( 224 bisection.getGraph(), cluster)); 225 // System.out 226 // .println("NEW BISECTION: " + bisection.toString()); 227 // } else 228 // finished = true; 204 229 } else 205 230 finished = true; -
src/main/java/weka/clusterers/forMetisMQI/Uncoarse.java
r14 r18 38 38 /** 39 39 * Given a bisection of the finer graph and the stack of graphs which yielded the finer graph, 40 * it returns the bisection projected into the coarser graph. 40 * it returns the bisection projected into the coarser graph. 41 41 * @param stack 42 42 * @param partition … … 47 47 CoarserGraphElement element = stack.pop(); 48 48 partition = uncoarseOneStep(partition,element); 49 partition = GraphAlgorithms.KLRefinement(partition); 49 50 } 50 51 return partition; -
src/main/java/weka/clusterers/forMetisMQI/graph/Bisection.java
r15 r18 122 122 } 123 123 124 public Bisection c opy(){124 public Bisection clone(){ 125 125 Bisection clone = new Bisection(); 126 126 clone.a = (Subgraph) a.clone(); 127 127 clone.b = (Subgraph) b.clone(); 128 clone.g = g.clone(); 128 129 clone.marked = new HashSet<Node>(); 129 130 return clone; -
src/main/java/weka/clusterers/forMetisMQI/graph/Subgraph.java
r15 r18 260 260 return FilterUtils.createInducedSubgraph(nodes,g); 261 261 } 262 263 public int totalDegree() { 264 int result = 0; 265 Iterator<Node> nodeIterator = iterator(); 266 while(nodeIterator.hasNext()) { 267 int degree = g.degree(nodeIterator.next()); 268 result += degree; 269 } 270 return result; 271 } 262 272 } -
src/main/java/weka/clusterers/forMetisMQI/util/Util.java
r15 r18 5 5 import java.awt.Paint; 6 6 import java.util.HashMap; 7 import java.util.HashSet; 7 8 import java.util.Iterator; 8 9 import java.util.Map; … … 18 19 import weka.clusterers.forMetisMQI.graph.UndirectedGraph; 19 20 import edu.uci.ics.jung.algorithms.layout.FRLayout; 21 import edu.uci.ics.jung.algorithms.layout.ISOMLayout; 20 22 import edu.uci.ics.jung.algorithms.layout.Layout; 21 23 import edu.uci.ics.jung.graph.Graph; … … 24 26 25 27 public class Util { 28 29 public static void viewCluster(Graph<Node, Edge> g, Set<Node> cluster) { 30 Set<Set<Node>> clusters = new HashSet<Set<Node>>(); 31 clusters.add(cluster); 32 viewClusters(g, clusters); 33 } 34 35 26 36 public static void viewClusters(Graph<Node, Edge> g, Set<Set<Node>> clusters) { 27 37 Layout<Node, Edge> layout = new FRLayout<Node, Edge>(g);
Note: See TracChangeset
for help on using the changeset viewer.