Changeset 11
- Timestamp:
- Sep 16, 2010, 10:44:40 AM (14 years ago)
- Location:
- src/main/java/weka/clusterers
- Files:
-
- 2 added
- 4 edited
- 7 moved
Legend:
- Unmodified
- Added
- Removed
-
src/main/java/weka/clusterers/SimpleClusterer.java
r9 r11 3 3 4 4 import weka.clusterers.forMetisMQI.GraphAlgorithms; 5 import weka.clusterers.forMetisMQI. UndirectedGraph;5 import weka.clusterers.forMetisMQI.graph.UndirectedGraph; 6 6 import weka.core.Capabilities; 7 7 import weka.core.Instance; -
src/main/java/weka/clusterers/forMetisMQI/GraphAlgorithms.java
r10 r11 3 3 import java.util.Stack; 4 4 5 import weka.clusterers.forMetisMQI.coarse.Coarse; 6 import weka.clusterers.forMetisMQI.coarse.CoarserGraphElement; 7 import weka.clusterers.forMetisMQI.graph.Bisection; 8 import weka.clusterers.forMetisMQI.graph.Node; 9 import weka.clusterers.forMetisMQI.graph.UndirectedGraph; 10 5 11 public class GraphAlgorithms { 6 12 7 public KLPartition KL(UndirectedGraph g) {8 KLPartition partition = new KLPartition(g);9 KLPartition result = partition;13 public Bisection KL(UndirectedGraph g) { 14 Bisection partition = new Bisection(g); 15 Bisection result = partition; 10 16 int bestEdgeCut = Integer.MAX_VALUE; 11 17 Node u = partition.getCandidate(); … … 22 28 23 29 public void METIS(UndirectedGraph g) { 24 KLPartition partition = null; 30 MQI.viewGraph(g); 31 Bisection partition = null; 25 32 Coarse.setFinerSize(8); 26 33 Stack<CoarserGraphElement> stack = Coarse.coarse(g); 27 28 34 if(stack.size() > 0) { 29 35 partition = KL(stack.peek().getContracted()); … … 32 38 System.out.println(partition.toString()); 33 39 } 34 35 MQI.start(partition);40 System.out.println("AAAAAA"); 41 System.out.println(MQI.mqi(partition).toString()); 36 42 37 43 } -
src/main/java/weka/clusterers/forMetisMQI/MQI.java
r10 r11 2 2 3 3 import java.awt.Dimension; 4 import java.util.HashMap; 4 5 import java.util.Iterator; 6 import java.util.Map; 7 import java.util.Set; 5 8 6 9 import javax.swing.JFrame; 7 10 11 import org.apache.commons.collections15.Factory; 12 import org.apache.commons.collections15.Transformer; 13 14 import weka.clusterers.forMetisMQI.graph.Bisection; 15 import weka.clusterers.forMetisMQI.graph.Edge; 16 import weka.clusterers.forMetisMQI.graph.Node; 17 import weka.clusterers.forMetisMQI.graph.Subgraph; 18 import weka.clusterers.forMetisMQI.graph.UndirectedGraph; 19 import edu.uci.ics.jung.algorithms.flows.EdmondsKarpMaxFlow; 8 20 import edu.uci.ics.jung.algorithms.layout.KKLayout; 9 21 import edu.uci.ics.jung.algorithms.layout.Layout; 22 import edu.uci.ics.jung.graph.DirectedGraph; 10 23 import edu.uci.ics.jung.graph.DirectedSparseGraph; 11 24 import edu.uci.ics.jung.graph.Graph; … … 15 28 public class MQI { 16 29 30 static int i = -1; 31 17 32 public static void viewGraph(Graph<Node, Edge> g){ 18 33 Layout<Node, Edge> layout = new KKLayout<Node, Edge>(g); 19 layout.setSize(new Dimension( 300,300)); // sets the initial size of the space34 layout.setSize(new Dimension(800,600)); // sets the initial size of the space 20 35 // The BasicVisualizationServer<V,E> is parameterized by the edge types 21 36 BasicVisualizationServer<Node,Edge> vv = 22 37 new BasicVisualizationServer<Node,Edge>(layout); 23 vv.setPreferredSize(new Dimension( 350,350)); //Sets the viewing area size38 vv.setPreferredSize(new Dimension(800,600)); //Sets the viewing area size 24 39 vv.getRenderContext().setVertexLabelTransformer(new ToStringLabeller<Node>()); 25 40 vv.getRenderContext().setEdgeLabelTransformer(new ToStringLabeller<Edge>()); … … 31 46 frame.setVisible(true); 32 47 } 48 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(); 63 } 33 64 34 static p ublic void start(KLPartition partition) {65 static private DirectedGraph<Node, Edge> prepareDirectedGraph(Bisection partition, Node source, Node sink) { 35 66 Subgraph A = null; 36 67 Subgraph B = null; … … 44 75 } 45 76 int a = A.getVertexCount(); 46 int c = partition.edgeCut() ;77 int c = partition.edgeCut() / 2; 47 78 48 79 49 Graph<Node,Edge> g = new DirectedSparseGraph<Node, Edge>();80 DirectedGraph<Node,Edge> g = new DirectedSparseGraph<Node, Edge>(); 50 81 Iterator<Node> nodes = A.iterator(); 51 82 while(nodes.hasNext()) { … … 66 97 } 67 98 68 Node source = new Node("S");69 Node sink = new Node("T");70 99 g.addVertex(source); 71 100 g.addVertex(sink); … … 91 120 id++; 92 121 } 93 94 // viewGraph(g); 95 System.out.println(g.toString()); 96 122 return g; 123 } 124 125 static public Bisection mqi(Bisection partition) { 126 boolean finished = false; 127 Bisection bisection = partition; 128 int maxFlowThreshold = Integer.MAX_VALUE; 129 while (!finished) { 130 UndirectedGraph startingGraph = partition.getGraph(); 131 Node source = new Node("S"); 132 Node sink = new Node("T"); 133 DirectedGraph<Node, Edge> g = prepareDirectedGraph(bisection, source, sink); 134 Transformer<Edge, Number> capTransformer = new Transformer<Edge, Number>() { 135 public Double transform(Edge e) { 136 return (double) e.getCapacity(); 137 } 138 }; 139 Map<Edge, Number> edgeFlowMap = new HashMap<Edge, Number>(); 140 // This Factory produces new edges for use by the algorithm 141 i=-1; 142 Factory<Edge> edgeFactory = new Factory<Edge>() { 143 public Edge create() { 144 i++; 145 return new Edge(Integer.toString(i), 1, 1); 146 } 147 }; 148 EdmondsKarpMaxFlow<Node, Edge> alg = new EdmondsKarpMaxFlow<Node, Edge>( 149 g, source, sink, capTransformer, edgeFlowMap, edgeFactory); 150 151 maxFlowThreshold = getMaxCardinality(bisection) * bisection.edgeCut() / 2; 152 alg.evaluate(); 153 if(alg.getMaxFlow() < maxFlowThreshold) { 154 Set<Node> sinkPartition = alg.getNodesInSinkPartition(); 155 Set<Node> sourcePartition = alg.getNodesInSourcePartition(); 156 bisection = prepareBisection(startingGraph, sourcePartition, sinkPartition); 157 } else 158 finished = true; 159 } 160 return bisection; 161 } 162 163 private static Bisection prepareBisection(UndirectedGraph g, Set<Node> sourcePartition, Set<Node> sinkPartition) { 164 Bisection b = null; 165 Subgraph sourceSubgraph = new Subgraph(g, sourcePartition); 166 Subgraph sinkSubgraph = new Subgraph(g, sinkPartition); 167 Subgraph subgraph = null; 168 if(sourceSubgraph.getVertexCount() > sinkSubgraph.getVertexCount()) 169 subgraph =sourceSubgraph; 170 else 171 subgraph = sinkSubgraph; 172 b = new Bisection(subgraph); 173 return b; 97 174 } 98 175 -
src/main/java/weka/clusterers/forMetisMQI/Uncoarse.java
r9 r11 4 4 import java.util.Stack; 5 5 6 import weka.clusterers.forMetisMQI.coarse.CoarserGraphElement; 7 import weka.clusterers.forMetisMQI.graph.Bisection; 8 import weka.clusterers.forMetisMQI.graph.Node; 9 import weka.clusterers.forMetisMQI.graph.Subgraph; 10 import weka.clusterers.forMetisMQI.graph.UndirectedGraph; 11 6 12 public class Uncoarse { 7 13 8 private boolean projectedBelongs(Node u, KLPartition partition, CoarserGraphElement cge) {14 private boolean projectedBelongs(Node u, Bisection partition, CoarserGraphElement cge) { 9 15 Subgraph s = partition.getSubgraph(); 10 16 Node mappedNode = cge.getMap().get(u); … … 18 24 * @param cge 19 25 */ 20 public KLPartition uncoarseOneStep(KLPartition partition, CoarserGraphElement cge) {26 public Bisection uncoarseOneStep(Bisection partition, CoarserGraphElement cge) { 21 27 UndirectedGraph projected = cge.getProjected(); 22 28 Subgraph part = new Subgraph(projected); … … 27 33 part.addVertex(u); 28 34 } 29 return new KLPartition(part);35 return new Bisection(part); 30 36 } 31 37 32 public KLPartition uncoarse(Stack<CoarserGraphElement> stack, KLPartition partition) {38 public Bisection uncoarse(Stack<CoarserGraphElement> stack, Bisection partition) { 33 39 while(stack.size() > 0) { 34 40 CoarserGraphElement element = stack.pop(); -
src/main/java/weka/clusterers/forMetisMQI/coarse/Coarse.java
r10 r11 1 package weka.clusterers.forMetisMQI ;1 package weka.clusterers.forMetisMQI.coarse; 2 2 3 3 import java.io.PrintStream; … … 8 8 import java.util.Set; 9 9 import java.util.Stack; 10 11 import weka.clusterers.forMetisMQI.graph.Edge; 12 import weka.clusterers.forMetisMQI.graph.Node; 13 import weka.clusterers.forMetisMQI.graph.UndirectedGraph; 10 14 11 15 import edu.uci.ics.jung.graph.util.Pair; -
src/main/java/weka/clusterers/forMetisMQI/coarse/CoarserGraphElement.java
r9 r11 1 package weka.clusterers.forMetisMQI ;1 package weka.clusterers.forMetisMQI.coarse; 2 2 3 3 import java.util.Map; 4 5 import weka.clusterers.forMetisMQI.graph.Node; 6 import weka.clusterers.forMetisMQI.graph.UndirectedGraph; 4 7 5 8 public class CoarserGraphElement { -
src/main/java/weka/clusterers/forMetisMQI/graph/Bisection.java
r10 r11 1 package weka.clusterers.forMetisMQI ;1 package weka.clusterers.forMetisMQI.graph; 2 2 3 3 import java.util.HashSet; … … 6 6 7 7 8 public class KLPartition { 8 9 public class Bisection { 9 10 10 11 private Subgraph a = null; … … 13 14 14 15 private Set<Node> marked = null; 16 17 private UndirectedGraph g = null; 15 18 16 private KLPartition() {19 private Bisection() { 17 20 } 18 21 19 public KLPartition(Subgraph s) { 20 UndirectedGraph g = s.getGraph(); 22 /** 23 * Initialize the bisection with a given subgraph. 24 * @param s 25 */ 26 public Bisection(Subgraph s) { 27 g = s.getGraph(); 21 28 a = s; 22 29 b = new Subgraph(g); … … 30 37 } 31 38 32 public KLPartition(UndirectedGraph g){ 39 /** 40 * Creates a bisection choosing randomly the nodes for each subgraph. 41 * @param g 42 */ 43 public Bisection(UndirectedGraph g){ 44 this.g = g; 33 45 a = new Subgraph(g); 34 46 b = new Subgraph(g); … … 44 56 } 45 57 marked = new HashSet<Node>(); 58 } 59 60 public UndirectedGraph getGraph() { 61 return g; 46 62 } 47 63 … … 106 122 } 107 123 108 public KLPartition copy(){109 KLPartition clone = new KLPartition();124 public Bisection copy(){ 125 Bisection clone = new Bisection(); 110 126 clone.a = (Subgraph) a.clone(); 111 127 clone.b = (Subgraph) b.clone(); -
src/main/java/weka/clusterers/forMetisMQI/graph/Edge.java
r10 r11 1 package weka.clusterers.forMetisMQI ;1 package weka.clusterers.forMetisMQI.graph; 2 2 3 3 public class Edge { … … 48 48 @Override 49 49 public String toString() { 50 return "E" + id + " w:" + weight;50 return Integer.toString(capacity); 51 51 } 52 52 -
src/main/java/weka/clusterers/forMetisMQI/graph/Node.java
r10 r11 1 package weka.clusterers.forMetisMQI ;1 package weka.clusterers.forMetisMQI.graph; 2 2 3 3 -
src/main/java/weka/clusterers/forMetisMQI/graph/Subgraph.java
r9 r11 1 package weka.clusterers.forMetisMQI ;1 package weka.clusterers.forMetisMQI.graph; 2 2 3 3 import java.util.ArrayList; … … 11 11 import java.util.Map.Entry; 12 12 13 import edu.uci.ics.jung.algorithms.filters.FilterUtils; 14 15 13 16 public class Subgraph { 14 17 … … 17 20 private Set<Node> nodes = null; 18 21 19 // private BitSet nodes = null;20 // private List<Integer> listOfNodes = null;21 22 private HashMap<Node,Integer> ID = null; 22 23 private HashMap<Node,Integer> ED = null; … … 34 35 } 35 36 37 public Subgraph(UndirectedGraph g, Set<Node> nodes) { 38 this.g = g; 39 this.nodes = new HashSet<Node>(); 40 this.ID = new HashMap<Node,Integer>(); 41 this.ED = new HashMap<Node,Integer>(); 42 this.bucketGain = new HashMap<Integer, List<Node>>(); 43 this.gainSet = new TreeSet<Integer>(); 44 Iterator<Node> nodesIterator = nodes.iterator(); 45 while(nodesIterator.hasNext()) { 46 addVertex(nodesIterator.next()); 47 } 48 } 49 36 50 public UndirectedGraph getGraph() { 37 51 return g; 38 52 } 39 53 54 /** 55 * Adds to the subgraph the node u iff u belongs to the graph. 56 * @param u 57 */ 40 58 public void addVertex(Node u) { 41 nodes.add(u); 42 ID.put(u, 0); 43 ED.put(u, 0); 44 recomputeGain = true; 59 if(g.containsVertex(u)) { 60 nodes.add(u); 61 ID.put(u, 0); 62 ED.put(u, 0); 63 recomputeGain = true; 64 } 45 65 } 46 66 … … 233 253 return clone; 234 254 } 255 256 public UndirectedGraph createInducedSubgraph() { 257 return FilterUtils.createInducedSubgraph(nodes,g); 258 } 235 259 } -
src/main/java/weka/clusterers/forMetisMQI/graph/UndirectedGraph.java
r10 r11 1 package weka.clusterers.forMetisMQI ;1 package weka.clusterers.forMetisMQI.graph; 2 2 3 3 import java.util.ArrayList; … … 6 6 import java.util.List; 7 7 8 import weka.clusterers.forMetisMQI.Random; 8 9 import weka.core.Attribute; 9 10 import weka.core.Instance; … … 89 90 g.addVertex(nodesIterator.next().clone()); 90 91 } 91 92 92 Iterator<Edge> edgesIterator = getEdges().iterator(); 93 93 while(edgesIterator.hasNext()) {
Note: See TracChangeset
for help on using the changeset viewer.