Index: src/main/java/weka/clusterers/SimpleClusterer.java =================================================================== --- src/main/java/weka/clusterers/SimpleClusterer.java (revision 6) +++ src/main/java/weka/clusterers/SimpleClusterer.java (revision 7) @@ -1,6 +1,4 @@ package weka.clusterers; - -import java.util.Iterator; import weka.clusterers.forMetisMQI.Graph; @@ -26,5 +24,5 @@ Graph g = new Graph(data); GraphAlgorithms ga = new GraphAlgorithms(); - ga.coarse(g); + ga.METIS(g); numberOfClusters = 1; } Index: src/main/java/weka/clusterers/forMetisMQI/Coarse.java =================================================================== --- src/main/java/weka/clusterers/forMetisMQI/Coarse.java (revision 7) +++ src/main/java/weka/clusterers/forMetisMQI/Coarse.java (revision 7) @@ -0,0 +1,164 @@ +package weka.clusterers.forMetisMQI; + +import java.io.PrintStream; +import java.util.ArrayList; +import java.util.HashSet; +import java.util.Iterator; +import java.util.List; +import java.util.Set; +import java.util.Stack; + +public class Coarse { + + private static boolean debug = true; + private static PrintStream debugStream = System.err; + private static int nodesContracted = 5; + + /** + * Return true if the vertex v is matched + * + * @param g graph + * @param v + * the index of the vertex + * @return true if the vertex v is matched, false o.w. + */ + private static boolean isMatched(Graph g, List match, int v) { + return match.get(g.getIndex(v)) != g.getIndex(v); + } + + private static void RMMatch(Graph g, List match, List map) { + int labelCounter = 0; + for (int i = 0; i < g.size(); i++) { + match.add(i); + map.add(i); + } + g.adjncyPermutation(); + Iterator nodeIterator = g.vtxsPermutation().iterator(); + while (nodeIterator.hasNext()) { + int u = nodeIterator.next(); + if (debug) + debugStream.println("Visiting node " + u + " Matched = " + isMatched(g,match,u)); + if (!isMatched(g,match,u)) { + boolean foundMatch = false; + int matchedNode = -1; + Iterator iterator = g.getNeighbors(u).iterator(); + while(iterator.hasNext() && !foundMatch){ + int v = iterator.next(); + if (!isMatched(g,match,v)) { + matchedNode = v; + foundMatch = true; + if (debug) + debugStream.println("Found a match with node " + + matchedNode); + } + } + if (debug && !foundMatch) + debugStream.println("There aren't unmatched neighbors."); + if(foundMatch) { + match.set(g.getIndex(u), g.getIndex(matchedNode)); + match.set(g.getIndex(matchedNode), g.getIndex(u)); + map.set(g.getIndex(u), labelCounter); + map.set(g.getIndex(matchedNode), labelCounter); + if(debug) debugStream.println("Contracting node " + u + " with " + matchedNode + ". Node id: " + getMappedNode(g, map, u)); + } else + map.set(g.getIndex(u), labelCounter); + labelCounter++; + } + } + } + + private static int getMatchedNode(Graph g, List match, int u) { + return g.getLabel(match.get(g.getIndex(u))); + } + + private static int getMappedNode(Graph g, List map, int u) { + return map.get(g.getIndex(u)); + } + + /** + * Return a new contracted graph. + */ + private static Graph contract(Graph g, List match, List map) { + Graph output = new Graph(); + Iterator iterator = g.iterator(); + while(iterator.hasNext()) { + int u = iterator.next(); + output.addNode(getMappedNode(g,map,u)); + Iterator it = g.getNeighbors(u).iterator(); + Set neighbors = new HashSet(); + while(it.hasNext()) { + int v = it.next(); + neighbors.add(getMappedNode(g,map,v)); + } + it = g.getNeighbors(getMatchedNode(g,match,u)).iterator(); + while(it.hasNext()) { + int v = it.next(); + neighbors.add(getMappedNode(g,map,v)); + } + neighbors.remove(getMappedNode(g,map,u)); + it = neighbors.iterator(); + while(it.hasNext()) { + int v = it.next(); + output.addNode(v); + output.addEdgeUndirected(getMappedNode(g,map,u), v, 0); + } + } + //calcolo dei pesi del nuovo grafo: per ogni arco (u,v) && u < v. + //w(map(u),map(v)) += w(u,v). + for(int u=0; u < g.size(); u++) { + Iterator it = g.getNeighbors(u).iterator(); + while(it.hasNext()) { + int v = it.next(); + if(getMappedNode(g,map,u) != getMappedNode(g,map,v) && output.isEdge(getMappedNode(g,map,u), getMappedNode(g,map,v)) && u < v) { + output.setWeight(getMappedNode(g,map,u), getMappedNode(g,map,v), output.getWeight(getMappedNode(g,map,u), getMappedNode(g,map,v)) + g.getWeight(u, v)); + } + } + } + for(int u = 0; u < g.size(); u++) { + if(isMatched(g,match,u)) { + int v = getMatchedNode(g,match,u); + if(u < v) { + output.getNode(getMappedNode(g,map,u)).vwgt = g.getNode(u).vwgt + g.getNode(v).vwgt; + output.getNode(getMappedNode(g,map,u)).cewgt = g.getNode(u).cewgt + g.getNode(v).cewgt + + g.getWeight(u, v); + output.getNode(getMappedNode(g,map,u)).adjwgt = g.getNode(u).adjwgt + g.getNode(v).adjwgt - 2 * + g.getWeight(u, v); + } + } else { + output.getNode(getMappedNode(g,map,u)).vwgt = g.getNode(u).vwgt; + output.getNode(getMappedNode(g,map,u)).cewgt = g.getNode(u).cewgt; + output.getNode(getMappedNode(g,map,u)).adjwgt = g.getNode(u).adjwgt; + } + } + return output; + } + + /** + * Performs the first stage of the METIS algorithm, using RM. + */ + public static CoarserGraphElement coarseOneStep(Graph g) { + Graph projected = g; + Graph contracted = null; + List match = new ArrayList(); + List map = new ArrayList(); + RMMatch(g,match,map); + contracted = contract(g,match,map); + return new CoarserGraphElement(contracted, projected, match, map); + } + + public static Stack coarse(Graph g) { + Stack stack = new Stack(); + CoarserGraphElement e; + Graph curr = g; + do { + if(debug) + debugStream.println("-----------------------------------------------------"); + e = coarseOneStep(curr); + stack.push(e); + curr = e.getContracted(); + if(debug) + debugStream.println("-----------------------------------------------------"); + } while(e.getProjected().size() > e.getContracted().size() && e.getContracted().size() > nodesContracted); + return stack; + } +} Index: src/main/java/weka/clusterers/forMetisMQI/CoarserGraphElement.java =================================================================== --- src/main/java/weka/clusterers/forMetisMQI/CoarserGraphElement.java (revision 6) +++ src/main/java/weka/clusterers/forMetisMQI/CoarserGraphElement.java (revision 7) @@ -5,10 +5,12 @@ public class CoarserGraphElement { - private Graph g; + private Graph contracted; + private Graph projected; private List match; private List map; - public CoarserGraphElement(Graph g, List match, List map) { - this.g = g; + public CoarserGraphElement(Graph contracted, Graph projected, List match, List map) { + this.contracted = contracted; + this.projected = projected; this.match = match; this.map = map; @@ -23,6 +25,10 @@ } - public Graph getGraph() { - return g; + public Graph getContracted() { + return contracted; + } + + public Graph getProjected() { + return projected; } Index: src/main/java/weka/clusterers/forMetisMQI/Graph.java =================================================================== --- src/main/java/weka/clusterers/forMetisMQI/Graph.java (revision 6) +++ src/main/java/weka/clusterers/forMetisMQI/Graph.java (revision 7) @@ -6,4 +6,5 @@ import java.util.Iterator; import java.util.List; +import java.util.Map.Entry; import weka.core.Attribute; @@ -41,4 +42,15 @@ return "Vwgt: " + vwgt + " Cewgt: " + cewgt + " Iedges: " + iedges + " Nedges: " + nedges + " Adjwgt: " + adjwgt; + } + + @Override + public NodeInfo clone() { + NodeInfo ni = new NodeInfo(); + ni.adjwgt = adjwgt; + ni.cewgt = cewgt; + ni.iedges = iedges; + ni.nedges = nedges; + ni.vwgt = vwgt; + return ni; } } @@ -107,5 +119,5 @@ * @return */ - private int getLabel(int index) { + public int getLabel(int index) { return this.index.get(index); } @@ -116,5 +128,5 @@ * @return */ - private int getIndex(int label) { + public int getIndex(int label) { return this.label.get(label); } @@ -307,3 +319,40 @@ } } + + + @Override + public Graph clone() { + Graph g = new Graph(); + g.adjncy = new ArrayList(); + for(int i = 0; i < adjncy.size(); i++) { + g.adjncy.add(adjncy.get(i)); + } + + g.weights = new ArrayList(); + for(int i = 0; i < weights.size(); i++) { + g.weights.add(weights.get(i)); + } + + g.vtxs = new ArrayList(); + for(int i = 0; i < vtxs.size(); i++) { + g.vtxs.add(vtxs.get(i).clone()); + } + + g.index = new HashMap(); + Iterator> i = index.entrySet().iterator(); + while(i.hasNext()) { + Entry entry = i.next(); + g.index.put(entry.getKey(), entry.getValue()); + } + + g.label = new HashMap(); + i = label.entrySet().iterator(); + while(i.hasNext()) { + Entry entry = i.next(); + g.label.put(entry.getKey(), entry.getValue()); + } + + + return g; + } } Index: src/main/java/weka/clusterers/forMetisMQI/GraphAlgorithms.java =================================================================== --- src/main/java/weka/clusterers/forMetisMQI/GraphAlgorithms.java (revision 6) +++ src/main/java/weka/clusterers/forMetisMQI/GraphAlgorithms.java (revision 7) @@ -1,148 +1,35 @@ package weka.clusterers.forMetisMQI; -import java.io.PrintStream; -import java.util.ArrayList; -import java.util.HashSet; -import java.util.Iterator; -import java.util.List; -import java.util.Set; +import java.util.Stack; public class GraphAlgorithms { - boolean debug = true; - PrintStream debugStream = System.err; - - /** - * Return true if the vertex v is matched - * - * @param v - * the index of the vertex - * @return true if the vertex v is matched, false o.w. - */ - private boolean isMatched(List match, int v) { - return match.get(v) != v; - } - - private void RMMatch(Graph g, List match, List map) { - int labelCounter = 0; - for (int i = 0; i < g.size(); i++) { - match.add(i); - map.add(i); + public KLPartition KL(Graph g) { + KLPartition partition = new KLPartition(g); + KLPartition result = partition; + int bestEdgeCut = Integer.MAX_VALUE; + int u = partition.getCandidate(); + while(u != -1) { + partition.swap(u); + if(partition.edgeCut() <= bestEdgeCut) { + bestEdgeCut = partition.edgeCut(); + result = partition.clone(); + } + u = partition.getCandidate(); } - g.adjncyPermutation(); - Iterator nodeIterator = g.vtxsPermutation().iterator(); - while (nodeIterator.hasNext()) { - int u = nodeIterator.next(); - if (debug) - debugStream.println("Visiting node " + u + " Matched = " + isMatched(match,u)); - if (!isMatched(match,u)) { - boolean foundMatch = false; - int matchedNode = -1; - Iterator iterator = g.getNeighbors(u).iterator(); - while(iterator.hasNext() && !foundMatch){ - int v = iterator.next(); - if (!isMatched(match,v)) { - matchedNode = v; - foundMatch = true; - if (debug) - debugStream.println("Found a match with node " - + matchedNode); - } - } - if (debug && !foundMatch) - debugStream.println("There aren't unmatched neighbors."); - if(foundMatch) { - match.set(u, matchedNode); - match.set(matchedNode, u); - map.set(u, labelCounter); - map.set(matchedNode, labelCounter); - if(debug) debugStream.println("Contracting node " + u + " with " + matchedNode + ". Node id: " + map.get(u)); - } else - map.set(u, labelCounter); - labelCounter++; - } - } + return result; } - /** - * Return a new contracted graph. - */ - private Graph contract(Graph g, List match, List map) { - Graph output = new Graph(); - Iterator iterator = g.iterator(); - while(iterator.hasNext()) { - int u = iterator.next(); - output.addNode(map.get(u)); - Iterator it = g.getNeighbors(u).iterator(); - Set neighbors = new HashSet(); - while(it.hasNext()) { - int v = it.next(); - neighbors.add(map.get(v)); - } - it = g.getNeighbors(match.get(u)).iterator(); - while(it.hasNext()) { - int v = it.next(); - neighbors.add(map.get(v)); - } - neighbors.remove(map.get(u)); - it = neighbors.iterator(); - while(it.hasNext()) { - int v = it.next(); - output.addNode(v); - output.addEdgeUndirected(map.get(u), v, 0); - } - } - //calcolo dei pesi del nuovo grafo: per ogni arco (u,v) && u < v. - //w(map(u),map(v)) += w(u,v). - for(int u=0; u < g.size(); u++) { - Iterator it = g.getNeighbors(u).iterator(); - while(it.hasNext()) { - int v = it.next(); - if(map.get(u) != map.get(v) && output.isEdge(map.get(u), map.get(v)) && u < v) { - output.setWeight(map.get(u), map.get(v), output.getWeight(map.get(u), map.get(v)) + g.getWeight(u, v)); - } - } + public void METIS(Graph g) { + KLPartition partition = null; + Stack stack = Coarse.coarse(g); + + if(stack.size() > 0) { + partition = KL(stack.peek().getContracted()); + System.out.println(partition.toString()); + partition = new Uncoarse().uncoarse(stack, partition); + System.out.println(partition.toString()); } - for(int u = 0; u < g.size(); u++) { - if(isMatched(match,u)) { - int v = match.get(u); - if(u < v) { - output.getNode(map.get(u)).vwgt = g.getNode(u).vwgt + g.getNode(v).vwgt; - output.getNode(map.get(u)).cewgt = g.getNode(u).cewgt + g.getNode(v).cewgt + - g.getWeight(u, v); - output.getNode(map.get(u)).adjwgt = g.getNode(u).adjwgt + g.getNode(v).adjwgt - 2 * - g.getWeight(u, v); - } - } else { - output.getNode(map.get(u)).vwgt = g.getNode(u).vwgt; - output.getNode(map.get(u)).cewgt = g.getNode(u).cewgt; - output.getNode(map.get(u)).adjwgt = g.getNode(u).adjwgt; - } - } - return output; - } - - /** - * Performs the first stage of the METIS algorithm, using RM. - */ - private CoarserGraphElement coarseOneStep(Graph g) { - List match = new ArrayList(); - List map = new ArrayList(); - RMMatch(g,match,map); - g = contract(g,match,map); - return new CoarserGraphElement(g, match, map); - } - - public void coarse(Graph g) { - int n = 1; - Graph prev = g; - CoarserGraphElement e; - g.printGraph(System.out); - do { - e = coarseOneStep(g); - prev = g; - g = e.getGraph(); - g.printGraph(System.out); - } while(prev.size() > g.size() && g.size() > n); + } Index: src/main/java/weka/clusterers/forMetisMQI/KLPartition.java =================================================================== --- src/main/java/weka/clusterers/forMetisMQI/KLPartition.java (revision 7) +++ src/main/java/weka/clusterers/forMetisMQI/KLPartition.java (revision 7) @@ -0,0 +1,124 @@ +package weka.clusterers.forMetisMQI; + +import java.util.ArrayList; +import java.util.Iterator; +import java.util.List; + + +public class KLPartition { + + private Subgraph a = null; + + private Subgraph b = null; + + private List marked = null; + + private KLPartition() { + } + + public KLPartition(Subgraph s) { + Graph g = s.getGraph(); + a = s; + b = new Subgraph(g); + Iterator graphIterator = g.iterator(); + while(graphIterator.hasNext()) { + int u = graphIterator.next(); + if(!s.contains(u)) + b.addNode(u); + } + marked = new ArrayList(); + } + + public KLPartition(Graph g){ + a = new Subgraph(g); + b = new Subgraph(g); + Random r = Random.instance(); + for(int i=0;i(); + } + + /** + * Returns the node marked as candidate for swapping or -1 if there aren't node available + * for swapping. + * @return + */ + public int getCandidate() { + int u; + if(a.size() > b.size()) { + u = a.getCandidate(marked); + if(u == -1) + u = b.getCandidate(marked); + } else { + u = b.getCandidate(marked); + if(u == -1) + u = a.getCandidate(marked); + } + if(u != -1) { + marked.add(u); + } + return u; + } + + public void swap(int u) { + Subgraph from = fromSubgraph(u); + Subgraph to = toSubgraph(u); + from.remove(u); + to.addNode(u); + } + + private Subgraph fromSubgraph(int u) { + Subgraph ret = null; + if(a.contains(u)) + ret = a; + if(b.contains(u)) + ret = b; + return ret; + } + + private Subgraph toSubgraph(int u) { + Subgraph ret = null; + if(!a.contains(u)) + ret = a; + if(!b.contains(u)) + ret = b; + return ret; + } + + public int edgeCut() { + int acc = a.getExternalDegree() + b.getExternalDegree(); + return (int)Math.round(0.5 * acc); + } + + public Subgraph getSubgraph() { + return a; + } + + public Subgraph getComplement() { + return b; + } + + @Override + public KLPartition clone(){ + KLPartition clone = new KLPartition(); + clone.a = (Subgraph) a.clone(); + clone.b = (Subgraph) b.clone(); + clone.marked = new ArrayList(); + for(int i = 0; i < marked.size(); i++) { + clone.marked.add(marked.get(i)); + } + return clone; + } + + @Override + public String toString(){ + String out = a.toString(); + out = out + "\n"; + out = out + b.toString(); + return out; + } +} Index: src/main/java/weka/clusterers/forMetisMQI/Subgraph.java =================================================================== --- src/main/java/weka/clusterers/forMetisMQI/Subgraph.java (revision 7) +++ src/main/java/weka/clusterers/forMetisMQI/Subgraph.java (revision 7) @@ -0,0 +1,246 @@ +package weka.clusterers.forMetisMQI; + +import java.util.ArrayList; +import java.util.BitSet; +import java.util.HashMap; +import java.util.Iterator; +import java.util.List; +import java.util.SortedSet; +import java.util.TreeSet; +import java.util.Map.Entry; + +import weka.clusterers.forMetisMQI.Graph.NodeInfo; + +public class Subgraph { + + private Graph g = null; + private BitSet nodes = null; + private List listOfNodes = null; + private HashMap ID = null; + private HashMap ED = null; + private HashMap> bucketGain = null; + private SortedSet gainSet = null; + private boolean recomputeGain = true; + + public Subgraph(Graph g){ + this.g = g; + nodes = new BitSet(g.size()); + listOfNodes = new ArrayList(); + ID = new HashMap(); + ED = new HashMap(); + bucketGain = new HashMap>(); + gainSet = new TreeSet(); + } + + public Graph getGraph() { + return g; + } + + public void addNode(int u) { + nodes.set(g.getIndex(u)); + listOfNodes.add(u); + ID.put(u, 0); + ED.put(u, 0); + recomputeGain = true; + } + + private void computeDegree() { + for(int i = 0; i < size(); i++) { + int u = listOfNodes.get(i); + Iterator it = g.getNeighbors(u).iterator(); + int newID = 0; + int newED = 0; + while(it.hasNext()) { + int v = it.next(); + if(contains(v)) + newID = newID + g.getWeight(u, v); + else + newED = newED + g.getWeight(u, v); + ID.put(u, newID); + ED.put(u, newED); + } + } + } + + private void computeGain() { + bucketGain.clear(); + gainSet.clear(); + ID.clear(); + ED.clear(); + computeDegree(); + for(int i = 0; i < size(); i++) { + int u = listOfNodes.get(i); + int gainU = ED.get(u) - ID.get(u); + if(!bucketGain.containsKey(gainU)) { + bucketGain.put(gainU, new ArrayList()); + } + bucketGain.get(gainU).add(u); + gainSet.add(gainU); + } + recomputeGain = false; + } + + public int getCandidate() { + return getCandidate(new ArrayList()); + } + + /** + * + * @param marked + * @return the candidate node for swap or -1 if there aren't available nodes. + */ + public int getCandidate(List marked) { + if(recomputeGain) + computeGain(); + int candidate = -1; + Iterator iterator = ((TreeSet)gainSet).descendingIterator(); + while(iterator.hasNext() && (candidate == -1)) { + int gain = iterator.next(); + Iterator nodes = bucketGain.get(gain).iterator(); + while(nodes.hasNext() && (candidate == -1)) { + int u = nodes.next(); + if(!marked.contains(u)) + candidate = u; + } + } + return candidate; + } + + public int gain(int u){ + if(recomputeGain) + computeGain(); + return ED.get(u) - ID.get(u); + } + + public void remove(int u) { + if(recomputeGain) + computeGain(); + int gainU = gain(u); + nodes.set(g.getIndex(u), false); + listOfNodes.remove(listOfNodes.indexOf(u)); + ID.remove(u); + ED.remove(u); + List l = bucketGain.get(gainU); + l.remove(l.indexOf(u)); + if(l.size() == 0) { + bucketGain.remove(gainU); + gainSet.remove(gainU); + } + recomputeGain = true; + } + + public int size() { + return listOfNodes.size(); + } + + public Iterator iterator() { + return listOfNodes.iterator(); + } + + public boolean isEdge(int u, int v) { + return nodes.get(g.getIndex(u)) && nodes.get(g.getIndex(v)) && g.isEdge(u, v); + } + + public boolean contains(int u) { + return nodes.get(g.getIndex(u)); + } + + public List getNeighbours(int u) { + List neighbors = new ArrayList(); + Iterator iterator = g.getNeighbors(u).iterator(); + while(iterator.hasNext()) { + int v = iterator.next(); + if(contains(v) && isEdge(u, v)) + neighbors.add(v); + } + return neighbors; + } + + public int getExternalDegree() { + if(recomputeGain) + computeGain(); + int acc = 0; + Iterator it = ED.values().iterator(); + while(it.hasNext()) + acc = acc + it.next(); + return acc; + } + + @Override + public String toString() { + String out = "["; + Iterator it = listOfNodes.iterator(); + while(it.hasNext()) { + int u = it.next(); + out = out + u + ","; + } + out = out + "]"; + return out; + } + + public List getBoundary() { + if(recomputeGain) + computeGain(); + Iterator> EDIterator = ED.entrySet().iterator(); + List boundary = new ArrayList(); + while(EDIterator.hasNext()) { + Entry entry = EDIterator.next(); + if(entry.getValue() > 0) + boundary.add(entry.getKey()); + } + return boundary; + } + + private Subgraph() { + + } + + @Override + public Subgraph clone() { + Subgraph clone = new Subgraph(); + clone.g = g.clone(); + + clone.nodes = (BitSet)nodes.clone(); + + clone.listOfNodes = new ArrayList(); + for(int i = 0; i < listOfNodes.size(); i++) { + clone.listOfNodes.add(listOfNodes.get(i)); + } + + clone.ID = new HashMap(); + Iterator> i = ID.entrySet().iterator(); + while(i.hasNext()) { + Entry entry = i.next(); + clone.ID.put(entry.getKey(), entry.getValue()); + } + + clone.ED = new HashMap(); + i = ED.entrySet().iterator(); + while(i.hasNext()) { + Entry entry = i.next(); + clone.ED.put(entry.getKey(), entry.getValue()); + } + + clone.bucketGain = new HashMap>(); + Iterator>>it = bucketGain.entrySet().iterator(); + while(it.hasNext()) { + Entry> entry = it.next(); + List bucketClone = new ArrayList(); + List bucket = entry.getValue(); + for(int j = 0; j < bucket.size(); j++) { + bucketClone.add(bucket.get(j)); + } + clone.bucketGain.put(entry.getKey(), bucketClone); + } + + clone.gainSet = new TreeSet(); + Iterator gainIt = gainSet.iterator(); + while(gainIt.hasNext()) { + gainSet.add(gainIt.next()); + } + + clone.recomputeGain = recomputeGain; + + return clone; + } +} Index: src/main/java/weka/clusterers/forMetisMQI/Uncoarse.java =================================================================== --- src/main/java/weka/clusterers/forMetisMQI/Uncoarse.java (revision 7) +++ src/main/java/weka/clusterers/forMetisMQI/Uncoarse.java (revision 7) @@ -0,0 +1,44 @@ +package weka.clusterers.forMetisMQI; + +import java.util.Iterator; +import java.util.Stack; + +public class Uncoarse { + + private boolean projectedBelongs(int u, KLPartition partition, CoarserGraphElement cge) { + Subgraph s = partition.getSubgraph(); + int index = cge.getProjected().getIndex(u); + int mappedNode = cge.getMap().get(index); + return s.contains(mappedNode); + } + + /** + * Given the projected graph and the partition of the coarser graph, it builds + * the projected partition. + * @param partition + * @param cge + */ + public KLPartition uncoarseOneStep(KLPartition partition, CoarserGraphElement cge) { + Graph projected = cge.getProjected(); + Subgraph part = new Subgraph(projected); + Iterator projectedIterator = projected.iterator(); + while(projectedIterator.hasNext()) { + int u = projectedIterator.next(); + if(projectedBelongs(u,partition,cge)) + part.addNode(u); + } + return new KLPartition(part); + } + + public KLPartition uncoarse(Stack stack, KLPartition partition) { + while(stack.size() > 0) { + CoarserGraphElement element = stack.pop(); + partition = uncoarseOneStep(partition,element); + } + return partition; + } + + public Uncoarse() { + } + +}