Changeset 20 for src/main/java
- Timestamp:
- Sep 30, 2010, 5:33:45 PM (14 years ago)
- Location:
- src/main/java/weka/clusterers/forMetisMQI
- Files:
-
- 4 edited
Legend:
- Unmodified
- Added
- Removed
-
src/main/java/weka/clusterers/forMetisMQI/GraphAlgorithms.java
r18 r20 81 81 */ 82 82 static public Set<Set<Node>> metisMqi(UndirectedGraph g, int numberOfCluster, int sizeFinerGraph) { 83 System.out.println("V ERTEX: " + g.getVertexCount());84 System.out.println("E DGE: " + g.getEdgeCount());83 System.out.println("Vertex count: " + g.getVertexCount()); 84 System.out.println("Edges count: " + g.getEdgeCount()); 85 85 Iterator<Node> iNodes = g.getVertices().iterator(); 86 86 int degreeCounter = 0; … … 95 95 // Util.viewGraph(g); 96 96 for (int i = 0; i < numberOfCluster; i++) { 97 Bisection partition = metis(g,sizeFinerGraph); 98 System.out.println("Partizione iniziale (Metis)"); 99 // System.out.println("Edge-cut: " + partition.edgeCut() / 2); 97 // Bisection partition = metis(g,sizeFinerGraph); 98 Bisection partition = new Bisection(g); 99 System.out.print("Partizione iniziale: "); 100 System.out.print("V1: " + partition.getSubgraph().getVertexCount()); 101 System.out.print(" V2: " + partition.getComplement().getVertexCount()); 102 System.out.println(" EC: " + partition.edgeCut() * 0.5); 100 103 System.out.println("Conductance: " + 101 104 ((double)partition.edgeCut() / 2) / Math.min(partition.getSubgraph().totalDegree(),partition.getComplement().totalDegree())); … … 107 110 Bisection mqiBisection = new Bisection(new Subgraph(g,cluster)); 108 111 System.out.println("Partizione raffinata (MQI)"); 109 // System.out.println("Edge-cut: " + mqiBisection.edgeCut() / 2);110 112 double newConductance = ((double)mqiBisection.edgeCut() / 2) / Math.min(mqiBisection.getSubgraph().totalDegree(),mqiBisection.getComplement().totalDegree()); 111 113 System.out.println("Conductance: " + newConductance); … … 117 119 } 118 120 121 System.out.println(); 119 122 Iterator<Node> clustersNode = cluster.iterator(); 120 123 while(clustersNode.hasNext()){ -
src/main/java/weka/clusterers/forMetisMQI/MQI.java
r18 r20 81 81 82 82 static private DirectedGraph<Node, Edge> prepareDirectedGraph( 83 Bisection partition, Node source, Node sink, boolean forConductance) { 84 Subgraph A = null; 85 Subgraph B = null; 86 if (partition.getSubgraph().getVertexCount() < partition 87 .getComplement().getVertexCount()) { 88 A = partition.getSubgraph(); 89 B = partition.getComplement(); 90 } else { 91 A = partition.getComplement(); 92 B = partition.getSubgraph(); 93 } 83 Bisection bisection, Node source, Node sink, boolean forConductance) { 84 Subgraph A = bisection.getLargerSubgraph(); 85 Subgraph B = bisection.getSmallerSubgraph(); 94 86 int a = 0; 95 87 if (!forConductance) … … 98 90 Iterator<Node> aIterator = A.iterator(); 99 91 while(aIterator.hasNext()) { 100 a += partition.getGraph().degree(aIterator.next());101 } 102 } 103 int c = partition.edgeCut() / 2;92 a += bisection.getGraph().degree(aIterator.next()); 93 } 94 } 95 int c = bisection.edgeCut() / 2; 104 96 105 97 DirectedGraph<Node, Edge> g = new DirectedSparseGraph<Node, Edge>(); … … 109 101 g.addVertex(u); 110 102 } 111 112 103 nodes = A.iterator(); 113 104 int id = 0; … … 153 144 if(forConductance) 154 145 //FIXME: CONTROLLAMI 155 g.addEdge(new Edge(Integer.toString(id), 1, c * partition.getGraph().degree(u)), u, sink);146 g.addEdge(new Edge(Integer.toString(id), 1, c * bisection.getGraph().degree(u)), u, sink); 156 147 else 157 148 g.addEdge(new Edge(Integer.toString(id), 1, c), u, sink); … … 173 164 boolean finished = false; 174 165 Bisection bisection = partition; 175 Set<Node> cluster = new HashSet<Node>(partition.get SmallerNotEmptySubgraph()166 Set<Node> cluster = new HashSet<Node>(partition.getLargerSubgraph() 176 167 .createInducedSubgraph().getVertices()); 177 168 int maxFlowThreshold = Integer.MAX_VALUE; … … 200 191 201 192 if (!forConductance) 202 maxFlowThreshold = bisection.get SmallerNotEmptySubgraph()193 maxFlowThreshold = bisection.getLargerSubgraph() 203 194 .getVertexCount() 204 195 * bisection.edgeCut() / 2; 205 196 else { 206 Iterator<Node> aIterator = bisection.get SmallerNotEmptySubgraph().iterator();197 Iterator<Node> aIterator = bisection.getLargerSubgraph().iterator(); 207 198 maxFlowThreshold = 0; 208 199 while(aIterator.hasNext()) … … 212 203 } 213 204 alg.evaluate(); 214 // 215 //System.out.println("MAX FLOW: " + alg.getMaxFlow() + " THRESHOLD: "216 //+ maxFlowThreshold);205 // Util.viewFlowGraph(directedGraph, edgeFlowMap); 206 System.out.println("MAX FLOW: " + alg.getMaxFlow() + " THRESHOLD: " 207 + maxFlowThreshold); 217 208 if (alg.getMaxFlow() < maxFlowThreshold) { 218 209 Set<Node> dfsResult = DFSReversed(sink, directedGraph, 219 210 edgeFlowMap, new HashSet<Node>()); 220 211 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; 212 cluster = dfsResult; 213 bisection = new Bisection(new Subgraph( 214 bisection.getGraph(), cluster)); 229 215 } else 230 216 finished = true; -
src/main/java/weka/clusterers/forMetisMQI/graph/Bisection.java
r18 r20 139 139 } 140 140 141 public Subgraph getLargerSubgraph() { 142 if(a.getVertexCount() < b.getVertexCount()) 143 return b; 144 else 145 return a; 146 } 147 141 148 /** 142 * Returns the smaller not emptysubgraph of this bisection, null otherwise.149 * Returns the smaller subgraph of this bisection, null otherwise. 143 150 * @return 144 151 */ 145 public Subgraph getSmallerNotEmptySubgraph() { 146 if(a.getVertexCount() > 0 && b.getVertexCount() == 0) 147 return a; 148 if(b.getVertexCount() > 0 && a.getVertexCount() == 0) 149 return b; 152 public Subgraph getSmallerSubgraph() { 150 153 if(a.getVertexCount() < b.getVertexCount()) 151 154 return a; -
src/main/java/weka/clusterers/forMetisMQI/graph/UndirectedGraph.java
r17 r20 1 1 package weka.clusterers.forMetisMQI.graph; 2 2 3 import java.io.PrintStream; 3 4 import java.util.ArrayList; 4 5 import java.util.Collection; 6 import java.util.HashMap; 5 7 import java.util.Iterator; 6 8 import java.util.List; 9 import java.util.TreeMap; 7 10 8 11 import weka.clusterers.forMetisMQI.Random; … … 109 112 } 110 113 114 public void printForMetis(PrintStream output) { 115 TreeMap<Integer,Node> map = new TreeMap<Integer,Node>(); 116 HashMap<Node,Integer> reverseMap = new HashMap<Node,Integer>(); 117 Iterator<Node> nodesIterator = getVertices().iterator(); 118 int id = 1; 119 while(nodesIterator.hasNext()) { 120 Node node = nodesIterator.next(); 121 map.put(id, node); 122 reverseMap.put(node,id); 123 id++; 124 } 125 output.println(getVertexCount() + " "+ getEdgeCount()); 126 Iterator<Integer> mappedIterator = map.keySet().iterator(); 127 while(mappedIterator.hasNext()) { 128 id = mappedIterator.next(); 129 Iterator<Node> neighbors = getNeighbors(map.get(id)).iterator(); 130 while(neighbors.hasNext()){ 131 output.print(reverseMap.get(neighbors.next())); 132 if(neighbors.hasNext()) output.print(" "); 133 } 134 output.println(); 135 } 136 } 137 111 138 public String toString() { 112 139 StringBuffer sb = new StringBuffer("Vertices:");
Note: See TracChangeset
for help on using the changeset viewer.