- Timestamp:
- Sep 14, 2010, 2:11:28 PM (14 years ago)
- Location:
- src/main/java/weka/clusterers
- Files:
-
- 1 added
- 1 deleted
- 10 edited
Legend:
- Unmodified
- Added
- Removed
-
src/main/java/weka/clusterers/SimpleClusterer.java
r7 r9 2 2 3 3 4 import weka.clusterers.forMetisMQI.Graph;5 4 import weka.clusterers.forMetisMQI.GraphAlgorithms; 5 import weka.clusterers.forMetisMQI.UndirectedGraph; 6 6 import weka.core.Capabilities; 7 7 import weka.core.Instance; … … 22 22 getCapabilities().testWithFail(data); 23 23 24 Graph g = new Graph(data); 24 UndirectedGraph g = new UndirectedGraph(); 25 g.loadFromInstance(data); 25 26 GraphAlgorithms ga = new GraphAlgorithms(); 26 27 ga.METIS(g); -
src/main/java/weka/clusterers/forMetisMQI/Coarse.java
r8 r9 2 2 3 3 import java.io.PrintStream; 4 import java.util. ArrayList;4 import java.util.HashMap; 5 5 import java.util.HashSet; 6 6 import java.util.Iterator; 7 import java.util. List;7 import java.util.Map; 8 8 import java.util.Set; 9 9 import java.util.Stack; 10 11 import edu.uci.ics.jung.graph.util.Pair; 10 12 11 13 public class Coarse { … … 23 25 * @return true if the vertex v is matched, false o.w. 24 26 */ 25 private static boolean isMatched(Graph g, List<Integer> match, int v) { 26 return match.get(g.getIndex(v)) != g.getIndex(v); 27 } 28 29 private static void RMMatch(Graph g, List<Integer> match, List<Integer> map) { 27 private static boolean isMatched(Map<Node,Node> match, Node v) { 28 if(match.containsKey(v)) 29 return !match.get(v).equals(v); 30 else 31 return false; 32 } 33 34 private static void RMMatch(UndirectedGraph g, Map<Node,Node> match, Map<Node,Node> map) { 30 35 int labelCounter = 0; 31 for (int i = 0; i < g.size(); i++) { 32 match.add(i); 33 map.add(i); 34 } 35 g.adjncyPermutation(); 36 Iterator<Integer> nodeIterator = g.vtxsPermutation().iterator(); 36 Iterator<Node> nodeIterator = g.vtxsPermutation().iterator(); 37 37 while (nodeIterator.hasNext()) { 38 intu = nodeIterator.next();38 Node u = nodeIterator.next(); 39 39 if (debug) 40 debugStream.println("Visiting node " + u + " Matched = " + isMatched( g,match,u));41 if (!isMatched( g,match,u)) {40 debugStream.println("Visiting node " + u + " Matched = " + isMatched(match,u)); 41 if (!isMatched(match,u)) { 42 42 boolean foundMatch = false; 43 int matchedNode = -1;44 Iterator< Integer> iterator = g.getNeighbors(u).iterator();43 Node matchedNode = null; 44 Iterator<Node> iterator = g.getNeighborsPermutation(u).iterator(); 45 45 while(iterator.hasNext() && !foundMatch){ 46 intv = iterator.next();47 if (!isMatched( g,match,v)) {46 Node v = iterator.next(); 47 if (!isMatched(match,v)) { 48 48 matchedNode = v; 49 49 foundMatch = true; … … 55 55 if (debug && !foundMatch) 56 56 debugStream.println("There aren't unmatched neighbors."); 57 Node newNode = new Node(Integer.toString(labelCounter)); 57 58 if(foundMatch) { 58 match. set(g.getIndex(u), g.getIndex(matchedNode));59 match. set(g.getIndex(matchedNode), g.getIndex(u));60 map. set(g.getIndex(u), labelCounter);61 map. set(g.getIndex(matchedNode), labelCounter);62 if(debug) debugStream.println("Contracting node " + u + " with " + matchedNode + ". Node id: " + getMappedNode( g,map, u));59 match.put(u, matchedNode); 60 match.put(matchedNode, u); 61 map.put(u, newNode); 62 map.put(matchedNode, newNode); 63 if(debug) debugStream.println("Contracting node " + u + " with " + matchedNode + ". Node id: " + getMappedNode(map, u)); 63 64 } else { 64 map.set(g.getIndex(u), labelCounter); 65 if(debug) debugStream.println("Node " + u + " with " + " new node id: " + getMappedNode(g, map, u)); 65 match.put(u, u); 66 map.put(u, newNode); 67 if(debug) debugStream.println("Node " + u + " with " + " new node id: " + getMappedNode(map, u)); 66 68 } 67 69 labelCounter++; … … 70 72 } 71 73 72 private static int getMatchedNode(Graph g, List<Integer> match, intu) {73 return g.getLabel(match.get(g.getIndex(u)));74 } 75 76 private static int getMappedNode(Graph g, List<Integer> map, intu) {77 return map.get( g.getIndex(u));74 private static Node getMatchedNode(Map<Node,Node> match, Node u) { 75 return match.get(u); 76 } 77 78 private static Node getMappedNode(Map<Node,Node> map, Node u) { 79 return map.get(u); 78 80 } 79 81 … … 81 83 * Return a new contracted graph. 82 84 */ 83 private static Graph contract(Graph g, List<Integer> match, List<Integer> map) { 84 Graph output = new Graph(); 85 Iterator<Integer> iterator = g.iterator(); 85 private static UndirectedGraph contract(UndirectedGraph g, Map<Node,Node> match, Map<Node,Node> map) { 86 UndirectedGraph output = new UndirectedGraph(); 87 Iterator<Node> iterator = g.getVertices().iterator(); 88 int i = 0; 86 89 while(iterator.hasNext()) { 87 int u = iterator.next(); 88 output.addNode(getMappedNode(g,map,u)); 89 Iterator<Integer> it = g.getNeighbors(u).iterator(); 90 Set<Integer> neighbors = new HashSet<Integer>(); 91 while(it.hasNext()) { 92 int v = it.next(); 93 neighbors.add(getMappedNode(g,map,v)); 94 } 95 it = g.getNeighbors(getMatchedNode(g,match,u)).iterator(); 96 while(it.hasNext()) { 97 int v = it.next(); 98 neighbors.add(getMappedNode(g,map,v)); 99 } 100 neighbors.remove(getMappedNode(g,map,u)); 90 Node u = iterator.next(); 91 output.addVertex(getMappedNode(map,u)); 92 93 Set<Node> neighbors = new HashSet<Node>(); 94 Iterator<Node> it = g.getNeighbors(u).iterator(); 95 while(it.hasNext()) 96 neighbors.add(getMappedNode(map, it.next())); 97 it = g.getNeighbors(getMatchedNode(match, u)).iterator(); 98 while(it.hasNext()) 99 neighbors.add(getMappedNode(map, it.next())); 100 101 // Set<Node> neighbors = new HashSet<Node>(); 102 // while(it.hasNext()) { 103 // Node v = it.next(); 104 // neighbors.add(getMappedNode(map,v)); 105 // } 106 // it = g.getNeighbors(getMappedNode(match,u)).iterator(); 107 // while(it.hasNext()) { 108 // Node v = it.next(); 109 // neighbors.add(getMappedNode(map,v)); 110 // } 111 neighbors.remove(getMappedNode(map,u)); 101 112 it = neighbors.iterator(); 102 113 while(it.hasNext()) { 103 int v = it.next(); 104 output.addNode(v); 105 output.addEdgeUndirected(getMappedNode(g,map,u), v, 0); 106 } 107 } 114 Node v = it.next(); 115 output.addVertex(v); 116 output.addEdge(new Edge(Integer.toString(i),0,0),getMappedNode(map,u), v); 117 i++; 118 } 119 } 120 108 121 //calcolo dei pesi del nuovo grafo: per ogni arco (u,v) && u < v. 109 //w(map(u),map(v)) += w(u,v). 110 for(int i=0; i < g.size(); i++) { 111 int u = g.getLabel(i); 112 Iterator<Integer> it = g.getNeighbors(u).iterator(); 113 while(it.hasNext()) { 114 int v = it.next(); 115 if(getMappedNode(g,map,u) != getMappedNode(g,map,v) && output.isEdge(getMappedNode(g,map,u), getMappedNode(g,map,v)) && u < v) { 116 output.setWeight(getMappedNode(g,map,u), getMappedNode(g,map,v), output.getWeight(getMappedNode(g,map,u), getMappedNode(g,map,v)) + g.getWeight(u, v)); 117 } 118 } 119 } 120 for(int i=0; i < g.size(); i++) { 121 int u = g.getLabel(i); 122 if(isMatched(g,match,u)) { 123 int v = getMatchedNode(g,match,u); 124 if(u < v) { 125 output.getNode(getMappedNode(g,map,u)).vwgt = g.getNode(u).vwgt + g.getNode(v).vwgt; 126 output.getNode(getMappedNode(g,map,u)).cewgt = g.getNode(u).cewgt + g.getNode(v).cewgt + 127 g.getWeight(u, v); 128 output.getNode(getMappedNode(g,map,u)).adjwgt = g.getNode(u).adjwgt + g.getNode(v).adjwgt - 2 * 129 g.getWeight(u, v); 122 //w(map(u),map(v)) += w(u,v). 123 124 Iterator<Edge> edgeIterator = g.getEdges().iterator(); 125 while(edgeIterator.hasNext()) { 126 Edge oldEdge = edgeIterator.next(); 127 Pair<Node> srcDst = g.getEndpoints(oldEdge); 128 Node src = srcDst.getFirst(); 129 Node dst = srcDst.getFirst(); 130 Node srcMapped = getMappedNode(map, src); 131 Node dstMapped = getMappedNode(map, dst); 132 if(!srcMapped.equals(dstMapped) && output.containsEdge(srcMapped, dstMapped)) { 133 Edge newEdge = output.findEdge(srcMapped, dstMapped); 134 newEdge.setWeight(newEdge.getWeight() + oldEdge.getWeight()); 135 } 136 } 137 138 139 // for(int i=0; i < g.size(); i++) { 140 // int u = g.getLabel(i); 141 // Iterator<Integer> it = g.getNeighbors(u).iterator(); 142 // while(it.hasNext()) { 143 // int v = it.next(); 144 // if(getMappedNode(g,map,u) != getMappedNode(g,map,v) && output.isEdge(getMappedNode(g,map,u), getMappedNode(g,map,v)) && u < v) { 145 // output.setWeight(getMappedNode(g,map,u), getMappedNode(g,map,v), output.getWeight(getMappedNode(g,map,u), getMappedNode(g,map,v)) + g.getWeight(u, v)); 146 // } 147 // } 148 // } 149 150 151 iterator = g.getVertices().iterator(); 152 Set<Node> nodesComplete = new HashSet<Node>(); 153 while(iterator.hasNext()) { 154 Node u = iterator.next(); 155 if(isMatched(match,u)) { 156 Node v = getMatchedNode(match,u); 157 if(!nodesComplete.contains(u)) { 158 getMappedNode(map,u).setVwgt(u.getVwgt() + v.getVwgt()); 159 getMappedNode(map,u).setCewgt(u.getCewgt() + v.getCewgt() + g.findEdge(u, v).getWeight()); 160 getMappedNode(map,u).setAdjwgt(u.getAdjwgt() + v.getAdjwgt() - 2 * g.findEdge(u, v).getWeight()); 161 nodesComplete.add(u); 162 nodesComplete.add(v); 130 163 } 131 164 } else { 132 output.getNode(getMappedNode(g,map,u)).vwgt = g.getNode(u).vwgt;133 output.getNode(getMappedNode(g,map,u)).cewgt = g.getNode(u).cewgt;134 output.getNode(getMappedNode(g,map,u)).adjwgt = g.getNode(u).adjwgt;165 getMappedNode(map,u).setVwgt(u.getVwgt()); 166 getMappedNode(map,u).setCewgt(u.getCewgt()); 167 getMappedNode(map,u).setAdjwgt(u.getAdjwgt()); 135 168 } 136 169 } … … 141 174 * Performs the first stage of the METIS algorithm, using RM. 142 175 */ 143 public static CoarserGraphElement coarseOneStep( Graph g) {144 Graph projected = g;145 Graph contracted = null;146 List<Integer> match = new ArrayList<Integer>();147 List<Integer> map = new ArrayList<Integer>();176 public static CoarserGraphElement coarseOneStep(UndirectedGraph g) { 177 UndirectedGraph projected = g; 178 UndirectedGraph contracted = null; 179 Map<Node,Node> match = new HashMap<Node,Node>(); 180 Map<Node,Node> map = new HashMap<Node,Node>(); 148 181 RMMatch(g,match,map); 149 182 contracted = contract(g,match,map); … … 151 184 } 152 185 153 public static Stack<CoarserGraphElement> coarse( Graph g) {186 public static Stack<CoarserGraphElement> coarse(UndirectedGraph g) { 154 187 Stack<CoarserGraphElement> stack = new Stack<CoarserGraphElement>(); 155 188 CoarserGraphElement e; 156 Graph curr = g;189 UndirectedGraph curr = g; 157 190 do { 158 191 if(debug) … … 163 196 if(debug) 164 197 debugStream.println("-----------------------------------------------------"); 165 } while(e.getProjected(). size() > e.getContracted().size() && e.getContracted().size() > finerSize);198 } while(e.getProjected().getVertexCount() > e.getContracted().getVertexCount() && e.getContracted().getVertexCount() > finerSize); 166 199 return stack; 167 200 } -
src/main/java/weka/clusterers/forMetisMQI/CoarserGraphElement.java
r7 r9 1 1 package weka.clusterers.forMetisMQI; 2 2 3 import java.util. List;3 import java.util.Map; 4 4 5 5 public class CoarserGraphElement { 6 6 7 private Graph contracted;8 private Graph projected;9 private List<Integer> match;10 private List<Integer> map;7 private UndirectedGraph contracted; 8 private UndirectedGraph projected; 9 private Map<Node,Node> match; 10 private Map<Node,Node> map; 11 11 12 public CoarserGraphElement( Graph contracted, Graph projected, List<Integer> match, List<Integer> map) {12 public CoarserGraphElement(UndirectedGraph contracted, UndirectedGraph projected, Map<Node,Node> match, Map<Node,Node> map) { 13 13 this.contracted = contracted; 14 14 this.projected = projected; … … 17 17 } 18 18 19 public List<Integer> getMatch() {19 public Map<Node,Node> getMatch() { 20 20 return match; 21 21 } 22 22 23 public List<Integer> getMap() {23 public Map<Node,Node> getMap() { 24 24 return map; 25 25 } 26 26 27 public Graph getContracted() {27 public UndirectedGraph getContracted() { 28 28 return contracted; 29 29 } 30 30 31 public Graph getProjected() {31 public UndirectedGraph getProjected() { 32 32 return projected; 33 33 } -
src/main/java/weka/clusterers/forMetisMQI/Edge.java
r8 r9 51 51 } 52 52 53 public void setWeight(int weight) { 54 this.weight = weight; 55 } 56 57 public void setCapacity(int capacity) { 58 this.capacity = capacity; 59 } 60 61 @Override 62 public Edge clone(){ 63 Edge e = new Edge(id, weight, capacity); 64 return e; 65 } 66 53 67 } -
src/main/java/weka/clusterers/forMetisMQI/GraphAlgorithms.java
r8 r9 5 5 public class GraphAlgorithms { 6 6 7 public KLPartition KL( Graph g) {7 public KLPartition KL(UndirectedGraph g) { 8 8 KLPartition partition = new KLPartition(g); 9 9 KLPartition result = partition; 10 10 int bestEdgeCut = Integer.MAX_VALUE; 11 intu = partition.getCandidate();12 while(u != -1) {11 Node u = partition.getCandidate(); 12 while(u != null) { 13 13 partition.swap(u); 14 14 if(partition.edgeCut() <= bestEdgeCut) { 15 15 bestEdgeCut = partition.edgeCut(); 16 result = partition.c lone();16 result = partition.copy(); 17 17 } 18 18 u = partition.getCandidate(); … … 21 21 } 22 22 23 public void METIS( Graph g) {23 public void METIS(UndirectedGraph g) { 24 24 KLPartition partition = null; 25 25 Coarse.setFinerSize(10); -
src/main/java/weka/clusterers/forMetisMQI/KLPartition.java
r8 r9 1 1 package weka.clusterers.forMetisMQI; 2 2 3 import java.util. ArrayList;3 import java.util.HashSet; 4 4 import java.util.Iterator; 5 import java.util. List;5 import java.util.Set; 6 6 7 7 … … 12 12 private Subgraph b = null; 13 13 14 private List<Integer> marked = null;14 private Set<Node> marked = null; 15 15 16 16 private KLPartition() { … … 18 18 19 19 public KLPartition(Subgraph s) { 20 Graph g = s.getGraph();20 UndirectedGraph g = s.getGraph(); 21 21 a = s; 22 22 b = new Subgraph(g); 23 Iterator< Integer> graphIterator = g.iterator();23 Iterator<Node> graphIterator = g.getVertices().iterator(); 24 24 while(graphIterator.hasNext()) { 25 intu = graphIterator.next();25 Node u = graphIterator.next(); 26 26 if(!s.contains(u)) 27 b.add Node(u);27 b.addVertex(u); 28 28 } 29 marked = new ArrayList<Integer>();29 marked = new HashSet<Node>(); 30 30 } 31 31 32 public KLPartition( Graph g){32 public KLPartition(UndirectedGraph g){ 33 33 a = new Subgraph(g); 34 34 b = new Subgraph(g); 35 Iterator< Integer> graph = g.vtxsPermutation().iterator();35 Iterator<Node> graph = g.vtxsPermutation().iterator(); 36 36 int i = 0; 37 37 while(graph.hasNext()) { 38 intu = graph.next();38 Node u = graph.next(); 39 39 if((i%2)==0) 40 a.add Node(u);40 a.addVertex(u); 41 41 else 42 b.add Node(u);42 b.addVertex(u); 43 43 i++; 44 44 } 45 marked = new ArrayList<Integer>();45 marked = new HashSet<Node>(); 46 46 } 47 47 48 48 /** 49 * Returns the node marked as candidate for swapping or -1if there aren't node available49 * Returns the node marked as candidate for swapping or <code>null</code> if there aren't node available 50 50 * for swapping. 51 51 * @return 52 52 */ 53 public intgetCandidate() {54 intu;55 if(a. size() > b.size()) {53 public Node getCandidate() { 54 Node u; 55 if(a.getVertexCount() > b.getVertexCount()) { 56 56 u = a.getCandidate(marked); 57 if(u == -1)57 if(u == null) 58 58 u = b.getCandidate(marked); 59 59 } else { 60 60 u = b.getCandidate(marked); 61 if(u == -1)61 if(u == null) 62 62 u = a.getCandidate(marked); 63 63 } 64 if(u != -1) {64 if(u != null) { 65 65 marked.add(u); 66 66 } … … 68 68 } 69 69 70 public void swap( intu) {70 public void swap(Node u) { 71 71 Subgraph from = fromSubgraph(u); 72 72 Subgraph to = toSubgraph(u); 73 from.remove (u);74 to.add Node(u);73 from.removeVertex(u); 74 to.addVertex(u); 75 75 } 76 76 77 private Subgraph fromSubgraph( intu) {77 private Subgraph fromSubgraph(Node u) { 78 78 Subgraph ret = null; 79 79 if(a.contains(u)) … … 84 84 } 85 85 86 private Subgraph toSubgraph( intu) {86 private Subgraph toSubgraph(Node u) { 87 87 Subgraph ret = null; 88 88 if(!a.contains(u)) … … 106 106 } 107 107 108 @Override 109 public KLPartition clone(){ 108 public KLPartition copy(){ 110 109 KLPartition clone = new KLPartition(); 111 110 clone.a = (Subgraph) a.clone(); 112 111 clone.b = (Subgraph) b.clone(); 113 clone.marked = new ArrayList<Integer>(); 114 for(int i = 0; i < marked.size(); i++) { 115 clone.marked.add(marked.get(i)); 116 } 112 clone.marked = new HashSet<Node>(); 117 113 return clone; 118 114 } -
src/main/java/weka/clusterers/forMetisMQI/MQI.java
r8 r9 6 6 import javax.swing.JFrame; 7 7 8 import edu.uci.ics.jung.algorithms.layout. CircleLayout;8 import edu.uci.ics.jung.algorithms.layout.KKLayout; 9 9 import edu.uci.ics.jung.algorithms.layout.Layout; 10 10 import edu.uci.ics.jung.graph.DirectedSparseGraph; … … 16 16 17 17 public static void viewGraph(Graph<Node, Edge> g){ 18 Layout<Node, Edge> layout = new CircleLayout<Node, Edge>(g);18 Layout<Node, Edge> layout = new KKLayout<Node, Edge>(g); 19 19 layout.setSize(new Dimension(300,300)); // sets the initial size of the space 20 20 // The BasicVisualizationServer<V,E> is parameterized by the edge types … … 33 33 Subgraph A = null; 34 34 Subgraph B = null; 35 if(partition.getSubgraph(). size() > partition.getComplement().size()) {35 if(partition.getSubgraph().getVertexCount() > partition.getComplement().getVertexCount()) { 36 36 A = partition.getSubgraph(); 37 37 B = partition.getComplement(); … … 41 41 B = partition.getSubgraph(); 42 42 } 43 int a = A. size();43 int a = A.getVertexCount(); 44 44 int c = partition.edgeCut(); 45 45 46 46 47 47 Graph<Node,Edge> g = new DirectedSparseGraph<Node, Edge>(); 48 Iterator< Integer> nodes = A.iterator();48 Iterator<Node> nodes = A.iterator(); 49 49 while(nodes.hasNext()) { 50 intu = nodes.next();51 g.addVertex( new Node(Integer.toString(u)));50 Node u = nodes.next(); 51 g.addVertex(u); 52 52 } 53 53 … … 55 55 int id = 0; 56 56 while(nodes.hasNext()) { 57 intu = nodes.next();58 Iterator< Integer> neighbors = A.getNeighbours(u).iterator();57 Node u = nodes.next(); 58 Iterator<Node> neighbors = A.getNeighbors(u).iterator(); 59 59 while(neighbors.hasNext()) { 60 intv = neighbors.next();61 g.addEdge(new Edge(Integer.toString(id),A.getWeight(u, v),a), new Node(Integer.toString(u)),new Node(Integer.toString(v)));60 Node v = neighbors.next(); 61 g.addEdge(new Edge(Integer.toString(id),A.getWeight(u, v),a),u,v); 62 62 id++; 63 63 } … … 72 72 nodes = B.iterator(); 73 73 while(nodes.hasNext()) { 74 intu = nodes.next();75 Iterator< Integer> neighbors = B.getGraph().getNeighbors(u).iterator();74 Node u = nodes.next(); 75 Iterator<Node> neighbors = B.getGraph().getNeighbors(u).iterator(); 76 76 while(neighbors.hasNext()) { 77 intv = neighbors.next();77 Node v = neighbors.next(); 78 78 if(A.contains(v)) { 79 g.addEdge(new Edge(Integer.toString(id),1,a),source, new Node(Integer.toString(v)));79 g.addEdge(new Edge(Integer.toString(id),1,a),source,v); 80 80 id++; 81 81 } … … 85 85 nodes = A.iterator(); 86 86 while(nodes.hasNext()) { 87 intu = nodes.next();88 g.addEdge(new Edge(Integer.toString(id),1,c), new Node(Integer.toString(u)),sink);87 Node u = nodes.next(); 88 g.addEdge(new Edge(Integer.toString(id),1,c),u,sink); 89 89 id++; 90 90 } -
src/main/java/weka/clusterers/forMetisMQI/Node.java
r8 r9 1 1 package weka.clusterers.forMetisMQI; 2 2 3 3 4 public class Node { 4 5 5 6 private String id; 6 7 8 /** The weight of the node */ 9 private int vwgt; 10 /** The size of the adjacency list of the node */ 11 private int nedges; 12 /** 13 * The index into the adjacency list that is the beginning of the adjacency 14 * list of v 15 */ 16 private int iedges; 17 /** The weight of the edges that have been contracted to create the node */ 18 private int cewgt; 19 /** The sum of the weight of the edges adjacent to v */ 20 private int adjwgt; 21 7 22 public Node(String id) { 8 23 this.id = id; 24 this.vwgt = 1; 25 this.cewgt = 0; 26 this.iedges = 0; 27 this.nedges = 0; 28 this.adjwgt = 0; 9 29 } 10 30 11 31 @Override 12 32 public boolean equals(Object o) { 13 return (o instanceof Node) && (((Node) o).getId().equals(id));33 return (o instanceof Node) && (((Node) o).getId().equals(id)); 14 34 } 15 35 16 36 @Override 17 37 public int hashCode() { … … 24 44 return id; 25 45 } 26 46 27 47 @Override 28 48 public String toString() { … … 30 50 } 31 51 52 public int getVwgt() { 53 return vwgt; 54 } 55 56 public void setVwgt(int vwgt) { 57 this.vwgt = vwgt; 58 } 59 60 public int getNedges() { 61 return nedges; 62 } 63 64 public void setNedges(int nedges) { 65 this.nedges = nedges; 66 } 67 68 public int getIedges() { 69 return iedges; 70 } 71 72 public void setIedges(int iedges) { 73 this.iedges = iedges; 74 } 75 76 public int getCewgt() { 77 return cewgt; 78 } 79 80 public void setCewgt(int cewgt) { 81 this.cewgt = cewgt; 82 } 83 84 public int getAdjwgt() { 85 return adjwgt; 86 } 87 88 public void setAdjwgt(int adjwgt) { 89 this.adjwgt = adjwgt; 90 } 91 92 @Override 93 public Node clone() { 94 Node n = new Node(id); 95 n.adjwgt = adjwgt; 96 n.cewgt = cewgt; 97 n.iedges = iedges; 98 n.nedges = nedges; 99 n.vwgt = vwgt; 100 return n; 101 } 102 32 103 } -
src/main/java/weka/clusterers/forMetisMQI/Subgraph.java
r8 r9 2 2 3 3 import java.util.ArrayList; 4 import java.util.BitSet;5 4 import java.util.HashMap; 5 import java.util.HashSet; 6 6 import java.util.Iterator; 7 7 import java.util.List; 8 import java.util.Set; 8 9 import java.util.SortedSet; 9 10 import java.util.TreeSet; … … 12 13 public class Subgraph { 13 14 14 private Graph g = null; 15 private BitSet nodes = null; 16 private List<Integer> listOfNodes = null; 17 private HashMap<Integer,Integer> ID = null; 18 private HashMap<Integer,Integer> ED = null; 19 private HashMap<Integer,List<Integer>> bucketGain = null; 15 private UndirectedGraph g = null; 16 17 private Set<Node> nodes = null; 18 19 // private BitSet nodes = null; 20 // private List<Integer> listOfNodes = null; 21 private HashMap<Node,Integer> ID = null; 22 private HashMap<Node,Integer> ED = null; 23 private HashMap<Integer,List<Node>> bucketGain = null; 20 24 private SortedSet<Integer> gainSet = null; 21 25 private boolean recomputeGain = true; 22 26 23 public Subgraph( Graph g){27 public Subgraph(UndirectedGraph g){ 24 28 this.g = g; 25 nodes = new BitSet(g.size()); 26 listOfNodes = new ArrayList<Integer>(); 27 ID = new HashMap<Integer,Integer>(); 28 ED = new HashMap<Integer,Integer>(); 29 bucketGain = new HashMap<Integer, List<Integer>>(); 29 nodes = new HashSet<Node>(); 30 ID = new HashMap<Node,Integer>(); 31 ED = new HashMap<Node,Integer>(); 32 bucketGain = new HashMap<Integer, List<Node>>(); 30 33 gainSet = new TreeSet<Integer>(); 31 34 } 32 35 33 public Graph getGraph() {36 public UndirectedGraph getGraph() { 34 37 return g; 35 38 } 36 39 37 public void addNode(int u) { 38 nodes.set(g.getIndex(u)); 39 listOfNodes.add(u); 40 public void addVertex(Node u) { 41 nodes.add(u); 40 42 ID.put(u, 0); 41 43 ED.put(u, 0); … … 44 46 45 47 private void computeDegree() { 46 for(int i = 0; i < size(); i++) { 47 int u = listOfNodes.get(i); 48 Iterator<Integer> it = g.getNeighbors(u).iterator(); 48 Iterator<Node> subgraphIterator = nodes.iterator(); 49 while(subgraphIterator.hasNext()) { 50 Node u = subgraphIterator.next(); 51 Iterator<Node> nborsIterator = g.getNeighbors(u).iterator(); 49 52 int newID = 0; 50 53 int newED = 0; 51 while( it.hasNext()) {52 int v = it.next();54 while(nborsIterator.hasNext()) { 55 Node v = nborsIterator.next(); 53 56 if(contains(v)) 54 newID = newID + g. getWeight(u, v);57 newID = newID + g.findEdge(u, v).getWeight(); 55 58 else 56 newED = newED + g. getWeight(u, v);59 newED = newED + g.findEdge(u, v).getWeight(); 57 60 ID.put(u, newID); 58 61 ED.put(u, newED); … … 67 70 ED.clear(); 68 71 computeDegree(); 69 for(int i = 0; i < size(); i++) { 70 int u = listOfNodes.get(i); 72 Iterator<Node> subgraphIterator = nodes.iterator(); 73 while(subgraphIterator.hasNext()) { 74 Node u = subgraphIterator.next(); 71 75 int gainU = ED.get(u) - ID.get(u); 72 76 if(!bucketGain.containsKey(gainU)) { 73 bucketGain.put(gainU, new ArrayList< Integer>());77 bucketGain.put(gainU, new ArrayList<Node>()); 74 78 } 75 79 bucketGain.get(gainU).add(u); … … 79 83 } 80 84 81 public intgetCandidate() {82 return getCandidate(new ArrayList<Integer>());85 public Node getCandidate() { 86 return getCandidate(new HashSet<Node>()); 83 87 } 84 88 … … 86 90 * 87 91 * @param marked 88 * @return the candidate node for swap or -1if there aren't available nodes.92 * @return the candidate node for swap or <code>null</code> if there aren't available nodes. 89 93 */ 90 public int getCandidate(List<Integer> marked) {91 if(recomputeGain) 92 computeGain(); 93 int candidate = -1;94 public Node getCandidate(Set<Node> marked) { 95 if(recomputeGain) 96 computeGain(); 97 Node candidate = null; 94 98 Iterator<Integer> iterator = ((TreeSet<Integer>)gainSet).descendingIterator(); 95 while(iterator.hasNext() && (candidate == -1)) {99 while(iterator.hasNext() && (candidate == null)) { 96 100 int gain = iterator.next(); 97 Iterator< Integer> nodes = bucketGain.get(gain).iterator();98 while(nodes.hasNext() && (candidate == -1)) {99 intu = nodes.next();101 Iterator<Node> nodes = bucketGain.get(gain).iterator(); 102 while(nodes.hasNext() && (candidate == null)) { 103 Node u = nodes.next(); 100 104 if(!marked.contains(u)) 101 105 candidate = u; … … 105 109 } 106 110 107 public int gain( intu){111 public int gain(Node u){ 108 112 if(recomputeGain) 109 113 computeGain(); … … 111 115 } 112 116 113 public void remove (intu) {117 public void removeVertex(Node u) { 114 118 if(recomputeGain) 115 119 computeGain(); 116 120 int gainU = gain(u); 117 nodes.set(g.getIndex(u), false); 118 listOfNodes.remove(listOfNodes.indexOf(u)); 121 nodes.remove(u); 119 122 ID.remove(u); 120 123 ED.remove(u); 121 List< Integer> l = bucketGain.get(gainU);124 List<Node> l = bucketGain.get(gainU); 122 125 l.remove(l.indexOf(u)); 123 126 if(l.size() == 0) { … … 128 131 } 129 132 130 public int size() { 131 return listOfNodes.size(); 132 } 133 134 public int getWeight(int u, int v) { 133 public int getVertexCount() { 134 return nodes.size(); 135 } 136 137 public Edge findEdge(Node v1, Node v2) { 138 Edge e = null; 139 if(contains(v1) && contains(v2)) 140 e = g.findEdge(v1, v2); 141 return e; 142 } 143 144 public int getWeight(Node u, Node v) { 135 145 int ret = -1; 136 if( isEdge(u,v))137 ret = g. getWeight(u, v);146 if(containsEdge(u,v)) 147 ret = g.findEdge(u, v).getWeight(); 138 148 return ret; 139 149 } 140 150 141 public Iterator< Integer> iterator() {142 return listOfNodes.iterator();143 } 144 145 public boolean isEdge(int u, intv) {146 return nodes.get(g.getIndex(u)) && nodes.get(g.getIndex(v)) && g.isEdge(u, v);147 } 148 149 public boolean contains( intu) {150 return nodes. get(g.getIndex(u));151 } 152 153 public List< Integer> getNeighbours(intu) {154 List< Integer> neighbors = new ArrayList<Integer>();155 Iterator< Integer> iterator = g.getNeighbors(u).iterator();151 public Iterator<Node> iterator() { 152 return nodes.iterator(); 153 } 154 155 public boolean containsEdge(Node u, Node v) { 156 return contains(u) && contains(v) && g.containsEdge(u, v); 157 } 158 159 public boolean contains(Node u) { 160 return nodes.contains(u); 161 } 162 163 public List<Node> getNeighbors(Node u) { 164 List<Node> neighbors = new ArrayList<Node>(); 165 Iterator<Node> iterator = g.getNeighbors(u).iterator(); 156 166 while(iterator.hasNext()) { 157 intv = iterator.next();158 if(contains(v) && isEdge(u, v))167 Node v = iterator.next(); 168 if(contains(v) && containsEdge(u, v)) 159 169 neighbors.add(v); 160 170 } … … 175 185 public String toString() { 176 186 String out = "["; 177 Iterator< Integer> it = listOfNodes.iterator();187 Iterator<Node> it = nodes.iterator(); 178 188 while(it.hasNext()) { 179 intu = it.next();189 Node u = it.next(); 180 190 out = out + u + ","; 181 191 } … … 184 194 } 185 195 186 public List< Integer> getBoundary() {187 if(recomputeGain) 188 computeGain(); 189 Iterator<Entry< Integer,Integer>> EDIterator = ED.entrySet().iterator();190 List< Integer> boundary = new ArrayList<Integer>();196 public List<Node> getBoundary() { 197 if(recomputeGain) 198 computeGain(); 199 Iterator<Entry<Node,Integer>> EDIterator = ED.entrySet().iterator(); 200 List<Node> boundary = new ArrayList<Node>(); 191 201 while(EDIterator.hasNext()) { 192 Entry< Integer,Integer> entry = EDIterator.next();202 Entry<Node,Integer> entry = EDIterator.next(); 193 203 if(entry.getValue() > 0) 194 204 boundary.add(entry.getKey()); … … 206 216 clone.g = g.clone(); 207 217 208 clone.nodes = (BitSet)nodes.clone(); 209 210 clone.listOfNodes = new ArrayList<Integer>(); 211 for(int i = 0; i < listOfNodes.size(); i++) { 212 clone.listOfNodes.add(listOfNodes.get(i)); 213 } 214 215 clone.ID = new HashMap<Integer, Integer>(); 216 Iterator<Entry<Integer,Integer>> i = ID.entrySet().iterator(); 217 while(i.hasNext()) { 218 Entry<Integer,Integer> entry = i.next(); 219 clone.ID.put(entry.getKey(), entry.getValue()); 220 } 221 222 clone.ED = new HashMap<Integer, Integer>(); 223 i = ED.entrySet().iterator(); 224 while(i.hasNext()) { 225 Entry<Integer,Integer> entry = i.next(); 226 clone.ED.put(entry.getKey(), entry.getValue()); 227 } 228 229 clone.bucketGain = new HashMap<Integer, List<Integer>>(); 230 Iterator<Entry<Integer,List<Integer>>>it = bucketGain.entrySet().iterator(); 231 while(it.hasNext()) { 232 Entry<Integer,List<Integer>> entry = it.next(); 233 List<Integer> bucketClone = new ArrayList<Integer>(); 234 List<Integer> bucket = entry.getValue(); 235 for(int j = 0; j < bucket.size(); j++) { 236 bucketClone.add(bucket.get(j)); 237 } 238 clone.bucketGain.put(entry.getKey(), bucketClone); 239 } 240 218 clone.nodes = new HashSet<Node>(); 219 Iterator<Node> graphIterator =clone.g.getVertices().iterator(); 220 while(graphIterator.hasNext()) { 221 Node u = graphIterator.next(); 222 if(contains(u)) 223 clone.nodes.add(u); 224 } 225 226 clone.bucketGain = new HashMap<Integer, List<Node>>(); 241 227 clone.gainSet = new TreeSet<Integer>(); 242 Iterator<Integer> gainIt = gainSet.iterator(); 243 while(gainIt.hasNext()) { 244 gainSet.add(gainIt.next()); 245 } 246 247 clone.recomputeGain = recomputeGain; 228 clone.ID = new HashMap<Node, Integer>(); 229 clone.ED = new HashMap<Node, Integer>(); 230 231 clone.computeGain(); 248 232 249 233 return clone; -
src/main/java/weka/clusterers/forMetisMQI/Uncoarse.java
r7 r9 6 6 public class Uncoarse { 7 7 8 private boolean projectedBelongs( intu, KLPartition partition, CoarserGraphElement cge) {8 private boolean projectedBelongs(Node u, KLPartition partition, CoarserGraphElement cge) { 9 9 Subgraph s = partition.getSubgraph(); 10 int index = cge.getProjected().getIndex(u); 11 int mappedNode = cge.getMap().get(index); 10 Node mappedNode = cge.getMap().get(u); 12 11 return s.contains(mappedNode); 13 12 } … … 20 19 */ 21 20 public KLPartition uncoarseOneStep(KLPartition partition, CoarserGraphElement cge) { 22 Graph projected = cge.getProjected();21 UndirectedGraph projected = cge.getProjected(); 23 22 Subgraph part = new Subgraph(projected); 24 Iterator< Integer> projectedIterator = projected.iterator();23 Iterator<Node> projectedIterator = projected.getVertices().iterator(); 25 24 while(projectedIterator.hasNext()) { 26 intu = projectedIterator.next();25 Node u = projectedIterator.next(); 27 26 if(projectedBelongs(u,partition,cge)) 28 part.add Node(u);27 part.addVertex(u); 29 28 } 30 29 return new KLPartition(part);
Note: See TracChangeset
for help on using the changeset viewer.