Changeset 16 for src/main/java/weka/clusterers/forMetisMQI
- Timestamp:
- Sep 18, 2010, 12:37:10 PM (14 years ago)
- Location:
- src/main/java/weka/clusterers/forMetisMQI
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
src/main/java/weka/clusterers/forMetisMQI/GraphAlgorithms.java
r15 r16 64 64 System.out.println("CLUSTER "+ i + ": " + cluster); 65 65 } 66 Util.viewClusters(g, clusters); 66 67 return clusters; 67 68 } -
src/main/java/weka/clusterers/forMetisMQI/MQI.java
r15 r16 23 23 24 24 public class MQI { 25 25 26 26 static int i = -1; 27 28 static private Set<Node> reversedLookup(Node sink, DirectedGraph<Node, Edge> g, Map<Edge, Number> edgeFlowMap) { 27 28 static private Set<Node> DFSReversed(Node currentNode, 29 DirectedGraph<Node, Edge> g, Map<Edge, Number> edgeFlowMap, Set<Node> marked) { 30 Collection<Edge> inEdges = g.getInEdges(currentNode); 29 31 Set<Node> result = new HashSet<Node>(); 30 Collection<Edge> inEdges = g.getInEdges(sink);32 result.add(currentNode); 31 33 Iterator<Edge> inEdgesIterator = inEdges.iterator(); 32 34 while (inEdgesIterator.hasNext()) { 33 35 Edge edge = inEdgesIterator.next(); 34 36 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); 37 Edge reverseEdge = g.findEdge(src, currentNode); 38 if (reverseEdge != null && !marked.contains(src)) { 39 int flow = (Integer) edgeFlowMap.get(reverseEdge); 40 int capacity = reverseEdge.getCapacity(); 41 if (flow < capacity) { 42 marked.add(src); 43 result.addAll(DFSReversed(src, g, edgeFlowMap, marked)); 44 } 40 45 } 41 46 } 42 47 return result; 43 48 } 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); 49 50 51 52 static private Set<Node> BFSReversed(Node sink, 53 DirectedGraph<Node, Edge> g, Map<Edge, Number> edgeFlowMap) { 48 54 Set<Node> result = new HashSet<Node>(); 49 Set<Node> discardedNodes = new HashSet<Node>(); 55 Set<Node> visitedNodes = new HashSet<Node>(); 56 Stack<Node> nodesToVisit = new Stack<Node>(); 50 57 result.add(sink); 51 while (!stack.empty()) {52 boolean founded = false;53 Node currentNode = stack.pop();54 discardedNodes.add(currentNode);58 nodesToVisit.push(sink); 59 while (!nodesToVisit.empty()) { 60 Node currentNode = nodesToVisit.pop(); 61 visitedNodes.add(currentNode); 55 62 Collection<Edge> inEdges = g.getInEdges(currentNode); 56 63 Iterator<Edge> inEdgesIterator = inEdges.iterator(); … … 59 66 Node src = g.getSource(edge); 60 67 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); 68 if (reverseEdge != null) { 69 int flow = (Integer) edgeFlowMap.get(reverseEdge); 70 int capacity = reverseEdge.getCapacity(); 71 if (flow < capacity) { 72 if (!nodesToVisit.contains(src) 73 && !visitedNodes.contains(src)) { 74 nodesToVisit.push(src); 75 } 76 result.add(src); 77 } 78 } 69 79 } 70 80 } 71 81 return result; 72 82 } 73 74 static private Set<Node> BFSReversed(Node sink, DirectedGraph<Node, Edge> g, Map<Edge, Number> edgeFlowMap) { 75 Set<Node> result = new HashSet<Node>(); 76 Set<Node> visitedNodes = new HashSet<Node>(); 77 Stack<Node> nodesToVisit = new Stack<Node>(); 78 result.add(sink); 79 nodesToVisit.push(sink); 80 while(!nodesToVisit.empty()) { 81 Node currentNode = nodesToVisit.pop(); 82 visitedNodes.add(currentNode); 83 Collection<Edge> inEdges = g.getInEdges(currentNode); 84 Iterator<Edge> inEdgesIterator = inEdges.iterator(); 85 while(inEdgesIterator.hasNext()) { 86 Edge edge = inEdgesIterator.next(); 87 Node src = g.getSource(edge); 88 Edge reverseEdge = g.findEdge(src, currentNode); 89 if((reverseEdge != null) && ((Integer)edgeFlowMap.get(reverseEdge) < reverseEdge.getCapacity())) { 90 if(!nodesToVisit.contains(src) && !visitedNodes.contains(src)) { 91 nodesToVisit.push(src); 92 } 93 result.add(src); 94 } 95 } 96 } 97 return result; 98 } 99 100 static private DirectedGraph<Node, Edge> prepareDirectedGraph(Bisection partition, Node source, Node sink) { 83 84 static private DirectedGraph<Node, Edge> prepareDirectedGraph( 85 Bisection partition, Node source, Node sink) { 101 86 Subgraph A = null; 102 87 Subgraph B = null; 103 if(partition.getSubgraph().getVertexCount() < partition.getComplement().getVertexCount()) { 88 if (partition.getSubgraph().getVertexCount() < partition 89 .getComplement().getVertexCount()) { 104 90 A = partition.getSubgraph(); 105 91 B = partition.getComplement(); 106 } 107 else { 92 } else { 108 93 A = partition.getComplement(); 109 94 B = partition.getSubgraph(); … … 111 96 int a = A.getVertexCount(); 112 97 int c = partition.edgeCut() / 2; 113 114 115 DirectedGraph<Node,Edge> g = new DirectedSparseGraph<Node, Edge>(); 116 Iterator<Node> nodes = A.iterator(); 117 while(nodes.hasNext()) { 98 99 DirectedGraph<Node, Edge> g = new DirectedSparseGraph<Node, Edge>(); 100 Iterator<Node> nodes = A.iterator(); 101 while (nodes.hasNext()) { 118 102 Node u = nodes.next(); 119 103 g.addVertex(u); 120 104 } 121 122 nodes = 105 106 nodes = A.iterator(); 123 107 int id = 0; 124 while (nodes.hasNext()) {108 while (nodes.hasNext()) { 125 109 Node u = nodes.next(); 126 110 Iterator<Node> neighbors = A.getNeighbors(u).iterator(); 127 while (neighbors.hasNext()) {111 while (neighbors.hasNext()) { 128 112 Node v = neighbors.next(); 129 g.addEdge(new Edge(Integer.toString(id),A.getWeight(u, v),a),u,v); 113 g.addEdge(new Edge(Integer.toString(id), A.getWeight(u, v), a), 114 u, v); 130 115 id++; 131 116 } 132 117 } 133 118 134 119 g.addVertex(source); 135 120 g.addVertex(sink); 121 136 122 137 138 nodes = B.iterator(); 139 while(nodes.hasNext()) { 123 //build the edges from source to each node of A which previously was connected 124 //with a node of B. 125 nodes = B.iterator(); 126 while (nodes.hasNext()) { 140 127 Node u = nodes.next(); 141 128 Iterator<Node> neighbors = B.getGraph().getNeighbors(u).iterator(); 142 while (neighbors.hasNext()) {129 while (neighbors.hasNext()) { 143 130 Node v = neighbors.next(); 144 if(A.contains(v)) { 145 g.addEdge(new Edge(Integer.toString(id),1,a),source,v); 146 id++; 147 } 148 } 149 } 150 151 nodes = A.iterator(); 152 while(nodes.hasNext()) { 153 Node u = nodes.next(); 154 g.addEdge(new Edge(Integer.toString(id),1,c),u,sink); 131 if (A.contains(v)) { 132 Edge e = g.findEdge(source, v); 133 if(e != null) { 134 e.setCapacity(e.getCapacity() + a); 135 } else { 136 g.addEdge(new Edge(Integer.toString(id), 1, a), source, v); 137 id++; 138 } 139 } 140 } 141 } 142 143 nodes = A.iterator(); 144 while (nodes.hasNext()) { 145 Node u = nodes.next(); 146 g.addEdge(new Edge(Integer.toString(id), 1, c), u, sink); 155 147 id++; 156 148 } 157 149 return g; 158 150 } 159 151 160 152 /** 161 * Given a partion of a graph, execute the Max-Flow Quotient-cut Improvement algorithm, 162 * to find an improved cut and then returns the cluster which yields the best quotient cut. 153 * Given a partion of a graph, execute the Max-Flow Quotient-cut Improvement 154 * algorithm, to find an improved cut and then returns the cluster which 155 * yields the best quotient cut. 156 * 163 157 * @param partition 164 158 * @return … … 168 162 boolean finished = false; 169 163 Bisection bisection = partition; 170 Set<Node> cluster = new HashSet<Node>(partition.getSmallerNotEmptySubgraph().createInducedSubgraph().getVertices()); 164 Set<Node> cluster = new HashSet<Node>(partition 165 .getSmallerNotEmptySubgraph().createInducedSubgraph() 166 .getVertices()); 171 167 int maxFlowThreshold = Integer.MAX_VALUE; 172 168 while (!finished) { 173 169 Node source = new Node("S"); 174 170 Node sink = new Node("T"); 175 DirectedGraph<Node, Edge> directedGraph = prepareDirectedGraph( bisection, source, sink);176 // Util.viewGraph(directedGraph);171 DirectedGraph<Node, Edge> directedGraph = prepareDirectedGraph( 172 bisection, source, sink); 177 173 Transformer<Edge, Number> capTransformer = new Transformer<Edge, Number>() { 178 174 public Double transform(Edge e) { … … 181 177 }; 182 178 Map<Edge, Number> edgeFlowMap = new HashMap<Edge, Number>(); 183 i =-1;179 i = -1; 184 180 // This Factory produces new edges for use by the algorithm 185 181 Factory<Edge> edgeFactory = new Factory<Edge>() { … … 190 186 }; 191 187 EdmondsKarpMaxFlow<Node, Edge> alg = new EdmondsKarpMaxFlow<Node, Edge>( 192 directedGraph, source, sink, capTransformer, edgeFlowMap, edgeFactory); 193 194 maxFlowThreshold = bisection.getSmallerNotEmptySubgraph().getVertexCount() * bisection.edgeCut() / 2; 188 directedGraph, source, sink, capTransformer, edgeFlowMap, 189 edgeFactory); 190 191 maxFlowThreshold = bisection.getSmallerNotEmptySubgraph() 192 .getVertexCount() 193 * bisection.edgeCut() / 2; 195 194 alg.evaluate(); 196 Util.viewFlowGraph(directedGraph, edgeFlowMap); 197 System.out.println("MAX FLOW: " + alg.getMaxFlow() + " THRESHOLD: " + maxFlowThreshold); 198 if(alg.getMaxFlow() < maxFlowThreshold) { 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); 195 // Util.viewFlowGraph(directedGraph, edgeFlowMap); 196 System.out.println("MAX FLOW: " + alg.getMaxFlow() + " THRESHOLD: " 197 + maxFlowThreshold); 198 if (alg.getMaxFlow() < maxFlowThreshold) { 199 cluster = DFSReversed(sink, directedGraph, edgeFlowMap, new HashSet<Node>()); 204 200 cluster.remove(sink); 205 bisection = new Bisection(new Subgraph(bisection.getSmallerNotEmptySubgraph().createInducedSubgraph(), cluster)); 201 bisection = new Bisection(new Subgraph(bisection.getGraph(), 202 cluster)); 206 203 System.out.println("NEW BISECTION: " + bisection.toString()); 207 204 } else … … 210 207 return cluster; 211 208 } 212 213 private static Bisection prepareBisection(UndirectedGraph g, Set<Node> sourcePartition, Set<Node> sinkPartition) { 214 Bisection b = null; 215 Subgraph sourceSubgraph = new Subgraph(g, sourcePartition); 216 Subgraph sinkSubgraph = new Subgraph(g, sinkPartition); 217 Subgraph subgraph = null; 218 if(sourceSubgraph.getVertexCount() > sinkSubgraph.getVertexCount()) 219 subgraph =sourceSubgraph; 220 else 221 subgraph = sinkSubgraph; 222 b = new Bisection(subgraph); 223 return b; 224 } 225 209 226 210 }
Note: See TracChangeset
for help on using the changeset viewer.