Changeset 15 for src/main/java/weka/clusterers/forMetisMQI
- Timestamp:
- Sep 17, 2010, 6:04:18 PM (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
r14 r15 57 57 static public Set<Set<Node>> metisMqi(UndirectedGraph g, int numberOfCluster, int sizeFinerGraph) { 58 58 Set<Set<Node>> clusters = new HashSet<Set<Node>>(); 59 Util.viewGraph(g); 59 60 for (int i = 0; i < numberOfCluster; i++) { 60 61 Bisection partition = metis(g,sizeFinerGraph); 61 62 Set<Node> cluster = MQI.mqi(partition); 62 63 clusters.add(cluster); 64 System.out.println("CLUSTER "+ i + ": " + cluster); 63 65 } 64 66 return clusters; -
src/main/java/weka/clusterers/forMetisMQI/MQI.java
r14 r15 1 1 package weka.clusterers.forMetisMQI; 2 2 3 import java.awt.Color;4 import java.awt.Dimension;5 import java.awt.Paint;6 3 import java.util.Collection; 7 4 import java.util.HashMap; … … 12 9 import java.util.Stack; 13 10 14 import javax.swing.JFrame;15 16 11 import org.apache.commons.collections15.Factory; 17 12 import org.apache.commons.collections15.Transformer; … … 22 17 import weka.clusterers.forMetisMQI.graph.Subgraph; 23 18 import weka.clusterers.forMetisMQI.graph.UndirectedGraph; 19 import weka.clusterers.forMetisMQI.util.Util; 24 20 import edu.uci.ics.jung.algorithms.flows.EdmondsKarpMaxFlow; 25 import edu.uci.ics.jung.algorithms.layout.FRLayout;26 import edu.uci.ics.jung.algorithms.layout.KKLayout;27 import edu.uci.ics.jung.algorithms.layout.Layout;28 21 import edu.uci.ics.jung.graph.DirectedGraph; 29 22 import edu.uci.ics.jung.graph.DirectedSparseGraph; 30 import edu.uci.ics.jung.graph.Graph;31 import edu.uci.ics.jung.visualization.BasicVisualizationServer;32 import edu.uci.ics.jung.visualization.decorators.ToStringLabeller;33 23 34 24 public class MQI { 35 25 36 26 static int i = -1; 27 28 static private Set<Node> reversedLookup(Node sink, DirectedGraph<Node, Edge> g, Map<Edge, Number> edgeFlowMap) { 29 Set<Node> result = new HashSet<Node>(); 30 Collection<Edge> inEdges = g.getInEdges(sink); 31 Iterator<Edge> inEdgesIterator = inEdges.iterator(); 32 while (inEdgesIterator.hasNext()) { 33 Edge edge = inEdgesIterator.next(); 34 Node src = g.getSource(edge); 35 Edge reverseEdge = g.findEdge(src, sink); 36 if ((reverseEdge != null) 37 && ((Integer) edgeFlowMap.get(reverseEdge) < reverseEdge 38 .getCapacity())) { 39 result.add(src); 40 } 41 } 42 return result; 43 } 44 45 static private Set<Node> DFSReversed(Node sink, DirectedGraph<Node, Edge> g, Map<Edge, Number> edgeFlowMap) { 46 Stack<Node> stack = new Stack<Node>(); 47 stack.push(sink); 48 Set<Node> result = new HashSet<Node>(); 49 Set<Node> discardedNodes = new HashSet<Node>(); 50 result.add(sink); 51 while (!stack.empty()) { 52 boolean founded = false; 53 Node currentNode = stack.pop(); 54 discardedNodes.add(currentNode); 55 Collection<Edge> inEdges = g.getInEdges(currentNode); 56 Iterator<Edge> inEdgesIterator = inEdges.iterator(); 57 while (inEdgesIterator.hasNext()) { 58 Edge edge = inEdgesIterator.next(); 59 Node src = g.getSource(edge); 60 Edge reverseEdge = g.findEdge(src, currentNode); 61 if ((reverseEdge != null) && !discardedNodes.contains(src) 62 && ((Integer) edgeFlowMap.get(reverseEdge) < reverseEdge 63 .getCapacity()) && !founded) { 64 founded=true; 65 stack.push(src); 66 result.add(src); 67 } 68 discardedNodes.add(src); 69 } 70 } 71 return result; 72 } 37 73 38 74 static private Set<Node> BFSReversed(Node sink, DirectedGraph<Node, Edge> g, Map<Edge, Number> edgeFlowMap) { … … 132 168 boolean finished = false; 133 169 Bisection bisection = partition; 134 Set<Node> cluster = new HashSet<Node>(partition.getS ubgraph().createInducedSubgraph().getVertices());170 Set<Node> cluster = new HashSet<Node>(partition.getSmallerNotEmptySubgraph().createInducedSubgraph().getVertices()); 135 171 int maxFlowThreshold = Integer.MAX_VALUE; 136 172 while (!finished) { … … 138 174 Node sink = new Node("T"); 139 175 DirectedGraph<Node, Edge> directedGraph = prepareDirectedGraph(bisection, source, sink); 176 // Util.viewGraph(directedGraph); 140 177 Transformer<Edge, Number> capTransformer = new Transformer<Edge, Number>() { 141 178 public Double transform(Edge e) { … … 144 181 }; 145 182 Map<Edge, Number> edgeFlowMap = new HashMap<Edge, Number>(); 183 i=-1; 146 184 // This Factory produces new edges for use by the algorithm 147 i=-1;148 185 Factory<Edge> edgeFactory = new Factory<Edge>() { 149 186 public Edge create() { 150 187 i++; 151 return new Edge( Integer.toString(i), 1, 1);188 return new Edge("f" + Integer.toString(i), 1, 1); 152 189 } 153 190 }; … … 155 192 directedGraph, source, sink, capTransformer, edgeFlowMap, edgeFactory); 156 193 157 maxFlowThreshold = bisection.getSmaller Subgraph().getVertexCount() * bisection.edgeCut() / 2;194 maxFlowThreshold = bisection.getSmallerNotEmptySubgraph().getVertexCount() * bisection.edgeCut() / 2; 158 195 alg.evaluate(); 196 Util.viewFlowGraph(directedGraph, edgeFlowMap); 159 197 System.out.println("MAX FLOW: " + alg.getMaxFlow() + " THRESHOLD: " + maxFlowThreshold); 160 198 if(alg.getMaxFlow() < maxFlowThreshold) { 161 Set<Node> sinkPartition = alg.getNodesInSinkPartition(); 162 System.out.println(sinkPartition); 163 Set<Node> sourcePartition = alg.getNodesInSourcePartition(); 164 System.out.println(sourcePartition); 165 bisection = prepareBisection(bisection.getSmallerSubgraph().createInducedSubgraph(), sourcePartition, sinkPartition); 166 // bisection = new Bisection(new Subgraph(bisection.getSmallerSubgraph().createInducedSubgraph(), BFSReversed(sink, directedGraph, edgeFlowMap))); 199 // bisection = prepareBisection(bisection.getSmallerNotEmptySubgraph().createInducedSubgraph(), sourcePartition, sinkPartition); 200 cluster = BFSReversed(sink, directedGraph, edgeFlowMap); 201 // System.out.println("DFSReversed: " + DFSReversed(sink, directedGraph, edgeFlowMap)); 202 // bisection = new Bisection(new Subgraph(bisection.getSmallerNotEmptySubgraph().createInducedSubgraph(), DFSReversed(sink, directedGraph, edgeFlowMap))); 203 // cluster = reversedLookup(sink, directedGraph, edgeFlowMap); 204 cluster.remove(sink); 205 bisection = new Bisection(new Subgraph(bisection.getSmallerNotEmptySubgraph().createInducedSubgraph(), cluster)); 167 206 System.out.println("NEW BISECTION: " + bisection.toString()); 168 cluster = sinkPartition;169 207 } else 170 208 finished = true; -
src/main/java/weka/clusterers/forMetisMQI/graph/Bisection.java
r12 r15 139 139 140 140 /** 141 * Returns the smaller subgraph of this bisection.141 * Returns the smaller not empty subgraph of this bisection, null otherwise. 142 142 * @return 143 143 */ 144 public Subgraph getSmallerSubgraph() { 144 public Subgraph getSmallerNotEmptySubgraph() { 145 if(a.getVertexCount() > 0 && b.getVertexCount() == 0) 146 return a; 147 if(b.getVertexCount() > 0 && a.getVertexCount() == 0) 148 return b; 145 149 if(a.getVertexCount() < b.getVertexCount()) 146 150 return a; -
src/main/java/weka/clusterers/forMetisMQI/graph/Edge.java
r11 r15 28 28 Edge e = (Edge) o; 29 29 result = result && (e.getId().equals(id)); 30 result = result && (e.getWeight() == weight);31 result = result && (e.getCapacity() == capacity);32 30 } 33 31 return result; -
src/main/java/weka/clusterers/forMetisMQI/graph/Subgraph.java
r13 r15 204 204 @Override 205 205 public String toString() { 206 String out = "["; 206 if(getVertexCount() == 0) 207 return "[]"; 208 StringBuffer out =new StringBuffer("["); 207 209 Iterator<Node> it = nodes.iterator(); 208 210 while(it.hasNext()) { 209 211 Node u = it.next(); 210 out = out + u + ","; 211 } 212 out = out + "]"; 213 return out; 212 out.append(u.toString() + ","); 213 } 214 out.setLength(out.length() - 1); 215 out.append("]"); 216 return out.toString(); 214 217 } 215 218 -
src/main/java/weka/clusterers/forMetisMQI/util/Util.java
r14 r15 91 91 vv.getRenderContext().setVertexLabelTransformer(new ToStringLabeller<Node>()); 92 92 vv.getRenderContext().setEdgeLabelTransformer(new ToStringLabeller<Edge>()); 93 93 JFrame frame = new JFrame("Simple Graph View"); 94 frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); 95 frame.getContentPane().add(vv); 96 frame.pack(); 97 frame.setVisible(true); 98 } 99 100 public static void viewFlowGraph(Graph<Node, Edge> g, Map<Edge, Number> edgeFlowMap){ 101 class EdgeTransformer implements Transformer<Edge,String> { 102 Map<Edge,Number> edgeFlowMap = null; 103 public String transform(Edge edge){ 104 return edgeFlowMap.get(edge) + "/" + edge.getCapacity(); 105 } 106 public EdgeTransformer(Map<Edge,Number> edgeFlowMap) { 107 this.edgeFlowMap = edgeFlowMap; 108 } 109 } 110 Layout<Node, Edge> layout = new FRLayout<Node, Edge>(g); 111 layout.setSize(new Dimension(800,600)); // sets the initial size of the space 112 // The BasicVisualizationServer<V,E> is parameterized by the edge types 113 BasicVisualizationServer<Node,Edge> vv = 114 new BasicVisualizationServer<Node,Edge>(layout); 115 vv.setPreferredSize(new Dimension(800,600)); //Sets the viewing area size 116 vv.getRenderContext().setVertexLabelTransformer(new ToStringLabeller<Node>()); 117 vv.getRenderContext().setEdgeLabelTransformer(new EdgeTransformer(edgeFlowMap)); 94 118 JFrame frame = new JFrame("Simple Graph View"); 95 119 frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
Note: See TracChangeset
for help on using the changeset viewer.