Ignore:
Timestamp:
Sep 16, 2010, 10:44:40 AM (14 years ago)
Author:
gnappo
Message:

Un po' di refactoring e implementazione dell'algoritmo di raffinamento.

Location:
src/main/java/weka/clusterers/forMetisMQI
Files:
2 added
3 edited
7 moved

Legend:

Unmodified
Added
Removed

  • src/main/java/weka/clusterers/forMetisMQI/GraphAlgorithms.java

    r10 r11  
    33import java.util.Stack;
    44
     5import weka.clusterers.forMetisMQI.coarse.Coarse;
     6import weka.clusterers.forMetisMQI.coarse.CoarserGraphElement;
     7import weka.clusterers.forMetisMQI.graph.Bisection;
     8import weka.clusterers.forMetisMQI.graph.Node;
     9import weka.clusterers.forMetisMQI.graph.UndirectedGraph;
     10
    511public class GraphAlgorithms {
    612       
    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;
    1016                int bestEdgeCut = Integer.MAX_VALUE;
    1117                Node u = partition.getCandidate();
    … …  
    2228       
    2329        public void METIS(UndirectedGraph g) {
    24                 KLPartition partition = null;
     30                MQI.viewGraph(g);
     31                Bisection partition = null;
    2532                Coarse.setFinerSize(8);
    2633                Stack<CoarserGraphElement> stack = Coarse.coarse(g);
    27                
    2834                if(stack.size() > 0) {
    2935                        partition = KL(stack.peek().getContracted());
    … …  
    3238                        System.out.println(partition.toString());
    3339                }
    34                
    35                 MQI.start(partition);
     40                System.out.println("AAAAAA");
     41                System.out.println(MQI.mqi(partition).toString());
    3642               
    3743        }

  • src/main/java/weka/clusterers/forMetisMQI/MQI.java

    r10 r11  
    22
    33import java.awt.Dimension;
     4import java.util.HashMap;
    45import java.util.Iterator;
     6import java.util.Map;
     7import java.util.Set;
    58
    69import javax.swing.JFrame;
    710
     11import org.apache.commons.collections15.Factory;
     12import org.apache.commons.collections15.Transformer;
     13
     14import weka.clusterers.forMetisMQI.graph.Bisection;
     15import weka.clusterers.forMetisMQI.graph.Edge;
     16import weka.clusterers.forMetisMQI.graph.Node;
     17import weka.clusterers.forMetisMQI.graph.Subgraph;
     18import weka.clusterers.forMetisMQI.graph.UndirectedGraph;
     19import edu.uci.ics.jung.algorithms.flows.EdmondsKarpMaxFlow;
    820import edu.uci.ics.jung.algorithms.layout.KKLayout;
    921import edu.uci.ics.jung.algorithms.layout.Layout;
     22import edu.uci.ics.jung.graph.DirectedGraph;
    1023import edu.uci.ics.jung.graph.DirectedSparseGraph;
    1124import edu.uci.ics.jung.graph.Graph;
    … …  
    1528public class MQI {
    1629       
     30        static int i = -1;
     31       
    1732        public static void viewGraph(Graph<Node, Edge> g){
    1833                Layout<Node, Edge> layout = new KKLayout<Node, Edge>(g);
    19                 layout.setSize(new Dimension(300,300)); // sets the initial size of the space
     34                layout.setSize(new Dimension(800,600)); // sets the initial size of the space
    2035                // The BasicVisualizationServer<V,E> is parameterized by the edge types
    2136                BasicVisualizationServer<Node,Edge> vv =
    2237                new BasicVisualizationServer<Node,Edge>(layout);
    23                 vv.setPreferredSize(new Dimension(350,350)); //Sets the viewing area size
     38                vv.setPreferredSize(new Dimension(800,600)); //Sets the viewing area size
    2439                vv.getRenderContext().setVertexLabelTransformer(new ToStringLabeller<Node>());
    2540                vv.getRenderContext().setEdgeLabelTransformer(new ToStringLabeller<Edge>());
    … …  
    3146                frame.setVisible(true);
    3247        }
     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        }
    3364       
    34         static public void start(KLPartition partition) {
     65        static private DirectedGraph<Node,       Edge> prepareDirectedGraph(Bisection partition, Node source, Node sink) {
    3566                Subgraph A = null;
    3667                Subgraph B = null;
    … …  
    4475                }
    4576                int a = A.getVertexCount();
    46                 int c = partition.edgeCut();
     77                int c = partition.edgeCut() / 2;
    4778               
    4879               
    49                 Graph<Node,Edge> g = new DirectedSparseGraph<Node, Edge>();
     80                DirectedGraph<Node,Edge> g = new DirectedSparseGraph<Node, Edge>();
    5081                Iterator<Node> nodes =  A.iterator();
    5182                while(nodes.hasNext()) {
    … …  
    6697                }
    6798               
    68                 Node source = new Node("S");
    69                 Node sink = new Node("T");
    7099                g.addVertex(source);
    71100                g.addVertex(sink);
    … …  
    91120                        id++;
    92121                }
    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;
    97174        }
    98175       

  • src/main/java/weka/clusterers/forMetisMQI/Uncoarse.java

    r9 r11  
    44import java.util.Stack;
    55
     6import weka.clusterers.forMetisMQI.coarse.CoarserGraphElement;
     7import weka.clusterers.forMetisMQI.graph.Bisection;
     8import weka.clusterers.forMetisMQI.graph.Node;
     9import weka.clusterers.forMetisMQI.graph.Subgraph;
     10import weka.clusterers.forMetisMQI.graph.UndirectedGraph;
     11
    612public class Uncoarse {
    713       
    8         private boolean projectedBelongs(Node u, KLPartition partition, CoarserGraphElement cge) {
     14        private boolean projectedBelongs(Node u, Bisection partition, CoarserGraphElement cge) {
    915                Subgraph s = partition.getSubgraph();
    1016                Node mappedNode = cge.getMap().get(u);
    … …  
    1824         * @param cge
    1925         */
    20         public KLPartition uncoarseOneStep(KLPartition partition, CoarserGraphElement cge) {
     26        public Bisection uncoarseOneStep(Bisection partition, CoarserGraphElement cge) {
    2127                UndirectedGraph projected = cge.getProjected();
    2228                Subgraph part = new Subgraph(projected);
    … …  
    2733                                part.addVertex(u);
    2834                }
    29                 return new KLPartition(part);
     35                return new Bisection(part);
    3036        }
    3137       
    32         public KLPartition uncoarse(Stack<CoarserGraphElement> stack, KLPartition partition) {
     38        public Bisection uncoarse(Stack<CoarserGraphElement> stack, Bisection partition) {
    3339                while(stack.size() > 0) {
    3440                        CoarserGraphElement element = stack.pop();

  • src/main/java/weka/clusterers/forMetisMQI/coarse/Coarse.java

    r10 r11  
    1 package weka.clusterers.forMetisMQI;
     1package weka.clusterers.forMetisMQI.coarse;
    22
    33import java.io.PrintStream;
    … …  
    88import java.util.Set;
    99import java.util.Stack;
     10
     11import weka.clusterers.forMetisMQI.graph.Edge;
     12import weka.clusterers.forMetisMQI.graph.Node;
     13import weka.clusterers.forMetisMQI.graph.UndirectedGraph;
    1014
    1115import edu.uci.ics.jung.graph.util.Pair;

  • src/main/java/weka/clusterers/forMetisMQI/coarse/CoarserGraphElement.java

    r9 r11  
    1 package weka.clusterers.forMetisMQI;
     1package weka.clusterers.forMetisMQI.coarse;
    22
    33import java.util.Map;
     4
     5import weka.clusterers.forMetisMQI.graph.Node;
     6import weka.clusterers.forMetisMQI.graph.UndirectedGraph;
    47
    58public class CoarserGraphElement {

  • src/main/java/weka/clusterers/forMetisMQI/graph/Bisection.java

    r10 r11  
    1 package weka.clusterers.forMetisMQI;
     1package weka.clusterers.forMetisMQI.graph;
    22
    33import java.util.HashSet;
    … …  
    66
    77
    8 public class KLPartition {
     8
     9public class Bisection {
    910       
    1011        private Subgraph a = null;
    … …  
    1314       
    1415        private Set<Node> marked = null;
     16       
     17        private UndirectedGraph g = null;
    1518
    16         private KLPartition() {
     19        private Bisection() {
    1720        }
    1821       
    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();
    2128                a = s;
    2229                b = new Subgraph(g);
    … …  
    3037        }
    3138       
    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;
    3345                a = new Subgraph(g);
    3446                b = new Subgraph(g);
    … …  
    4456                }
    4557                marked = new HashSet<Node>();
     58        }
     59       
     60        public UndirectedGraph getGraph() {
     61                return g;
    4662        }
    4763       
    … …  
    106122        }
    107123       
    108         public KLPartition copy(){
    109                 KLPartition clone = new KLPartition();
     124        public Bisection copy(){
     125                Bisection clone = new Bisection();
    110126                clone.a = (Subgraph) a.clone();
    111127                clone.b = (Subgraph) b.clone();

  • src/main/java/weka/clusterers/forMetisMQI/graph/Edge.java

    r10 r11  
    1 package weka.clusterers.forMetisMQI;
     1package weka.clusterers.forMetisMQI.graph;
    22
    33public class Edge {
    … …  
    4848        @Override
    4949        public String toString() {
    50                 return "E" + id + " w:" + weight;
     50                return Integer.toString(capacity);
    5151        }
    5252

  • src/main/java/weka/clusterers/forMetisMQI/graph/Node.java

    r10 r11  
    1 package weka.clusterers.forMetisMQI;
     1package weka.clusterers.forMetisMQI.graph;
    22
    33

  • src/main/java/weka/clusterers/forMetisMQI/graph/Subgraph.java

    r9 r11  
    1 package weka.clusterers.forMetisMQI;
     1package weka.clusterers.forMetisMQI.graph;
    22
    33import java.util.ArrayList;
    … …  
    1111import java.util.Map.Entry;
    1212
     13import edu.uci.ics.jung.algorithms.filters.FilterUtils;
     14
     15
    1316public class Subgraph {
    1417       
    … …  
    1720        private Set<Node> nodes = null;
    1821       
    19 //      private BitSet nodes = null;
    20 //      private List<Integer> listOfNodes = null;
    2122        private HashMap<Node,Integer> ID = null;
    2223        private HashMap<Node,Integer> ED = null;
    … …  
    3435        }
    3536       
     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       
    3650        public UndirectedGraph getGraph() {
    3751                return g;
    3852        }
    3953       
     54        /**
     55         * Adds to the subgraph the node u iff u belongs to the graph.
     56         * @param u
     57         */
    4058        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                }
    4565        }
    4666       
    … …  
    233253                return clone;
    234254        }
     255       
     256        public UndirectedGraph createInducedSubgraph() {
     257                return FilterUtils.createInducedSubgraph(nodes,g);
     258        }
    235259}

  • src/main/java/weka/clusterers/forMetisMQI/graph/UndirectedGraph.java

    r10 r11  
    1 package weka.clusterers.forMetisMQI;
     1package weka.clusterers.forMetisMQI.graph;
    22
    33import java.util.ArrayList;
    … …  
    66import java.util.List;
    77
     8import weka.clusterers.forMetisMQI.Random;
    89import weka.core.Attribute;
    910import weka.core.Instance;
    … …  
    8990                        g.addVertex(nodesIterator.next().clone());
    9091                }
    91                
    9292                Iterator<Edge> edgesIterator = getEdges().iterator();
    9393                while(edgesIterator.hasNext()) {
Note: See TracChangeset for help on using the changeset viewer.