Changeset 12 for src/main/java
- Timestamp:
- Sep 16, 2010, 7:01:57 PM (14 years ago)
- Location:
- src/main/java/weka/clusterers/forMetisMQI
- Files:
-
- 3 edited
Legend:
- Unmodified
- Added
- Removed
-
src/main/java/weka/clusterers/forMetisMQI/GraphAlgorithms.java
r11 r12 1 1 package weka.clusterers.forMetisMQI; 2 2 3 import java.util.HashSet; 4 import java.util.Set; 3 5 import java.util.Stack; 4 6 … … 10 12 11 13 public class GraphAlgorithms { 12 14 13 15 public Bisection KL(UndirectedGraph g) { 14 16 Bisection partition = new Bisection(g); … … 16 18 int bestEdgeCut = Integer.MAX_VALUE; 17 19 Node u = partition.getCandidate(); 18 while (u != null) {20 while (u != null) { 19 21 partition.swap(u); 20 if (partition.edgeCut() <=bestEdgeCut) {22 if (partition.edgeCut() <= bestEdgeCut) { 21 23 bestEdgeCut = partition.edgeCut(); 22 24 result = partition.copy(); … … 26 28 return result; 27 29 } 28 30 29 31 public void METIS(UndirectedGraph g) { 30 MQI.viewGraph(g); 31 Bisection partition = null; 32 Coarse.setFinerSize(8); 33 Stack<CoarserGraphElement> stack = Coarse.coarse(g); 34 if(stack.size() > 0) { 35 partition = KL(stack.peek().getContracted()); 36 System.out.println(partition.toString()); 37 partition = new Uncoarse().uncoarse(stack, partition); 38 System.out.println(partition.toString()); 32 // MQI.viewGraph(g); 33 Set<Set<Node>> clusters = new HashSet<Set<Node>>(); 34 for (int i = 0; i < 8; i++) { 35 Coarse.setFinerSize(8); 36 Stack<CoarserGraphElement> stack = Coarse.coarse(g); 37 Bisection partition = null; 38 if (stack.size() > 0) { 39 partition = KL(stack.peek().getContracted()); 40 // System.out.println(partition.toString()); 41 partition = new Uncoarse().uncoarse(stack, partition); 42 // System.out.println(partition.toString()); 43 Set<Node> cluster = MQI.mqi(partition); 44 clusters.add(cluster); 45 // Set<Set<Node>> foundCluster = new HashSet<Set<Node>>(); 46 // foundCluster.add(cluster); 47 // MQI.viewClusters(g, foundCluster); 48 } 39 49 } 40 System.out.println("AAAAAA"); 41 System.out.println(MQI.mqi(partition).toString()); 42 50 MQI.viewClusters(g, clusters); 43 51 } 44 52 -
src/main/java/weka/clusterers/forMetisMQI/MQI.java
r11 r12 1 1 package weka.clusterers.forMetisMQI; 2 2 3 import java.awt.Color; 3 4 import java.awt.Dimension; 5 import java.awt.Paint; 6 import java.util.Collection; 4 7 import java.util.HashMap; 8 import java.util.HashSet; 5 9 import java.util.Iterator; 6 10 import java.util.Map; 7 11 import java.util.Set; 12 import java.util.Stack; 8 13 9 14 import javax.swing.JFrame; … … 30 35 static int i = -1; 31 36 37 public static void viewClusters(Graph<Node, Edge> g, Set<Set<Node>> clusters) { 38 Layout<Node, Edge> layout = new KKLayout<Node, Edge>(g); 39 layout.setSize(new Dimension(800, 600)); // sets the initial size of the space 40 // The BasicVisualizationServer<V,E> is parameterized by the edge types 41 BasicVisualizationServer<Node, Edge> vv = new BasicVisualizationServer<Node, Edge>( 42 layout); 43 44 class VertexPaintTransformer implements Transformer<Node, Paint> { 45 Set<Set<Node>> clusters = null; 46 Map<Set<Node>, Color> clustersColor = null; 47 48 public Set<Node> getCluster(Node node) { 49 Iterator<Set<Node>> clusterIterator = clusters.iterator(); 50 while (clusterIterator.hasNext()) { 51 Set<Node> cluster = clusterIterator.next(); 52 if (cluster.contains(node)) 53 return cluster; 54 } 55 return null; 56 } 57 58 public VertexPaintTransformer(Set<Set<Node>> clusters) { 59 this.clusters = clusters; 60 clustersColor = new HashMap<Set<Node>, Color>(clusters.size()); 61 Iterator<Set<Node>> clusterIterator = clusters.iterator(); 62 while (clusterIterator.hasNext()) { 63 Set<Node> cluster = clusterIterator.next(); 64 clustersColor.put(cluster, new Color(Random.instance() 65 .nextInt(256), Random.instance().nextInt(256), 66 Random.instance().nextInt(256))); 67 } 68 } 69 70 public Paint transform(Node i) { 71 Set<Node> cluster = getCluster(i); 72 if (cluster == null) 73 return Color.RED; 74 else 75 return clustersColor.get(getCluster(i)); 76 } 77 } 78 79 Transformer<Node, Paint> vertexPaint = new VertexPaintTransformer( 80 clusters); 81 vv.setPreferredSize(new Dimension(800, 600)); // Sets the viewing area 82 // size 83 vv.getRenderContext().setVertexLabelTransformer( 84 new ToStringLabeller<Node>()); 85 vv.getRenderContext().setEdgeLabelTransformer( 86 new ToStringLabeller<Edge>()); 87 vv.getRenderContext().setVertexFillPaintTransformer(vertexPaint); 88 JFrame frame = new JFrame("Graph View"); 89 frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); 90 frame.getContentPane().add(vv); 91 frame.pack(); 92 frame.setVisible(true); 93 } 94 32 95 public static void viewGraph(Graph<Node, Edge> g){ 33 96 Layout<Node, Edge> layout = new KKLayout<Node, Edge>(g); … … 47 110 } 48 111 49 /** 50 * Given a bisection, returns the cardinality of the larger subgraph. 51 * @param b 52 * @return 53 */ 54 static private int getMaxCardinality(Bisection b) { 55 Subgraph A = null; 56 if(b.getSubgraph().getVertexCount() > b.getComplement().getVertexCount()) { 57 A = b.getSubgraph(); 58 } 59 else { 60 A = b.getComplement(); 61 } 62 return A.getVertexCount(); 112 static private Set<Node> BFSReversed(Node sink, DirectedGraph<Node, Edge> g, Map<Edge, Number> edgeFlowMap) { 113 Set<Node> result = new HashSet<Node>(); 114 Set<Node> visitedNodes = new HashSet<Node>(); 115 Stack<Node> nodesToVisit = new Stack<Node>(); 116 result.add(sink); 117 nodesToVisit.push(sink); 118 while(!nodesToVisit.empty()) { 119 Node currentNode = nodesToVisit.pop(); 120 visitedNodes.add(currentNode); 121 Collection<Edge> inEdges = g.getInEdges(currentNode); 122 Iterator<Edge> inEdgesIterator = inEdges.iterator(); 123 while(inEdgesIterator.hasNext()) { 124 Edge edge = inEdgesIterator.next(); 125 Node src = g.getSource(edge); 126 Edge reverseEdge = g.findEdge(src, currentNode); 127 if((reverseEdge != null) && ((Integer)edgeFlowMap.get(reverseEdge) < reverseEdge.getCapacity())) { 128 if(!nodesToVisit.contains(src) && !visitedNodes.contains(src)) { 129 nodesToVisit.push(src); 130 } 131 result.add(src); 132 } 133 } 134 } 135 return result; 63 136 } 64 137 … … 66 139 Subgraph A = null; 67 140 Subgraph B = null; 68 if(partition.getSubgraph().getVertexCount() >partition.getComplement().getVertexCount()) {141 if(partition.getSubgraph().getVertexCount() < partition.getComplement().getVertexCount()) { 69 142 A = partition.getSubgraph(); 70 143 B = partition.getComplement(); … … 123 196 } 124 197 125 static public Bisection mqi(Bisection partition) { 198 /** 199 * Given a partion of a graph, execute the Max-Flow Quotient-cut Improvement algorithm, 200 * to find an improved cut and then returns the cluster which yields the best quotient cut. 201 * @param partition 202 * @return 203 */ 204 static public Set<Node> mqi(Bisection partition) { 205 System.out.println("INITIAL BISECTION: " + partition.toString()); 126 206 boolean finished = false; 127 207 Bisection bisection = partition; 208 Set<Node> cluster = new HashSet<Node>(partition.getSubgraph().createInducedSubgraph().getVertices()); 128 209 int maxFlowThreshold = Integer.MAX_VALUE; 129 210 while (!finished) { 130 UndirectedGraph startingGraph = partition.getGraph();131 211 Node source = new Node("S"); 132 212 Node sink = new Node("T"); 133 DirectedGraph<Node, Edge> g= prepareDirectedGraph(bisection, source, sink);213 DirectedGraph<Node, Edge> directedGraph = prepareDirectedGraph(bisection, source, sink); 134 214 Transformer<Edge, Number> capTransformer = new Transformer<Edge, Number>() { 135 215 public Double transform(Edge e) { … … 147 227 }; 148 228 EdmondsKarpMaxFlow<Node, Edge> alg = new EdmondsKarpMaxFlow<Node, Edge>( 149 g, source, sink, capTransformer, edgeFlowMap, edgeFactory);229 directedGraph, source, sink, capTransformer, edgeFlowMap, edgeFactory); 150 230 151 maxFlowThreshold = getMaxCardinality(bisection) * bisection.edgeCut() / 2;231 maxFlowThreshold = bisection.getSmallerSubgraph().getVertexCount() * bisection.edgeCut() / 2; 152 232 alg.evaluate(); 233 System.out.println("MAX FLOW: " + alg.getMaxFlow() + " THRESHOLD: " + maxFlowThreshold); 153 234 if(alg.getMaxFlow() < maxFlowThreshold) { 154 235 Set<Node> sinkPartition = alg.getNodesInSinkPartition(); 236 System.out.println(sinkPartition); 155 237 Set<Node> sourcePartition = alg.getNodesInSourcePartition(); 156 bisection = prepareBisection(startingGraph, sourcePartition, sinkPartition); 238 System.out.println(sourcePartition); 239 bisection = prepareBisection(bisection.getSmallerSubgraph().createInducedSubgraph(), sourcePartition, sinkPartition); 240 // bisection = new Bisection(new Subgraph(bisection.getSmallerSubgraph().createInducedSubgraph(), BFSReversed(sink, directedGraph, edgeFlowMap))); 241 System.out.println("NEW BISECTION: " + bisection.toString()); 242 cluster = sinkPartition; 157 243 } else 158 244 finished = true; 159 245 } 160 return bisection;246 return cluster; 161 247 } 162 248 -
src/main/java/weka/clusterers/forMetisMQI/graph/Bisection.java
r11 r12 137 137 return out; 138 138 } 139 140 /** 141 * Returns the smaller subgraph of this bisection. 142 * @return 143 */ 144 public Subgraph getSmallerSubgraph() { 145 if(a.getVertexCount() < b.getVertexCount()) 146 return a; 147 else 148 return b; 149 } 139 150 }
Note: See TracChangeset
for help on using the changeset viewer.