Changeset 18 for src/main/java


Ignore:
Timestamp:
Sep 29, 2010, 9:13:19 AM (14 years ago)
Author:
gnappo
Message:

Implementato raffinamento KL in metis; implementata ottimizzazione di mqi sulla conduttanza.

Location:
src/main/java/weka/clusterers/forMetisMQI
Files:
6 edited

Legend:

Unmodified
Added
Removed

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

    r17 r18  
    88import weka.clusterers.forMetisMQI.graph.Bisection;
    99import weka.clusterers.forMetisMQI.graph.Node;
     10import weka.clusterers.forMetisMQI.graph.Subgraph;
    1011import weka.clusterers.forMetisMQI.graph.UndirectedGraph;
    1112import weka.clusterers.forMetisMQI.util.CoarserGraphElement;
    … …  
    1415public class GraphAlgorithms {
    1516
     17       
     18        static public Bisection KLRefinement(Bisection b) {
     19                int remainingNumberOfSwap = 50;
     20                Bisection partition = b;
     21                Bisection result = partition;
     22                int bestEdgeCut = partition.edgeCut();
     23                Node u = partition.getCandidate();
     24                while (u != null && remainingNumberOfSwap > 0) {
     25                        partition.swap(u);
     26                        if (partition.edgeCut() <= bestEdgeCut) {
     27                                bestEdgeCut = partition.edgeCut();
     28                                result = partition.clone();
     29                                remainingNumberOfSwap = 50;
     30                        } else
     31                                remainingNumberOfSwap--;
     32                        u = partition.getCandidate();
     33                }
     34                return result;
     35        }
     36       
    1637       
    1738        /**
    … …  
    2243         */
    2344        static public Bisection KL(UndirectedGraph g) {
     45                int remainingNumberOfSwap = 50;
    2446                Bisection partition = new Bisection(g);
    2547                Bisection result = partition;
    26                 int bestEdgeCut = Integer.MAX_VALUE;
     48                int bestEdgeCut = partition.edgeCut();
    2749                Node u = partition.getCandidate();
    28                 while (u != null) {
     50                while (u != null && remainingNumberOfSwap > 0) {
    2951                        partition.swap(u);
    3052                        if (partition.edgeCut() <= bestEdgeCut) {
    3153                                bestEdgeCut = partition.edgeCut();
    32                                 result = partition.copy();
    33                         }
     54                                result = partition.clone();
     55                                remainingNumberOfSwap = 50;
     56                        } else
     57                                remainingNumberOfSwap--;
    3458                        u = partition.getCandidate();
    3559                }
    … …  
    5781         */
    5882        static public Set<Set<Node>> metisMqi(UndirectedGraph g, int numberOfCluster, int sizeFinerGraph) {
     83                System.out.println("VERTEX: " + g.getVertexCount());
     84                System.out.println("EDGE: " + g.getEdgeCount());
     85                Iterator<Node> iNodes = g.getVertices().iterator();
     86                int degreeCounter = 0;
     87                while(iNodes.hasNext()) {
     88                        Node node = iNodes.next();
     89                        if(g.degree(node) == 1) {
     90                                degreeCounter++;
     91                        }
     92                }
    5993                Set<Set<Node>> clusters = new HashSet<Set<Node>>();
    6094                UndirectedGraph gclone = g.clone();
    … …  
    6296                for (int i = 0; i < numberOfCluster; i++) {
    6397                        Bisection partition = metis(g,sizeFinerGraph);
    64                         Set<Node> cluster = MQI.mqi(partition);
     98                        System.out.println("Partizione iniziale (Metis)");
     99//                      System.out.println("Edge-cut: " + partition.edgeCut() / 2);
     100                        System.out.println("Conductance: " +
     101                                        ((double)partition.edgeCut() / 2) / Math.min(partition.getSubgraph().totalDegree(),partition.getComplement().totalDegree()));
     102                        Set<Node> cluster = MQI.mqi(partition,true);
     103                       
     104                        UndirectedGraph clusterGraph = new Subgraph(gclone,cluster).createInducedSubgraph();
     105                       
     106//                      System.out.println(cluster);
     107                        Bisection mqiBisection = new Bisection(new Subgraph(g,cluster));
     108                        System.out.println("Partizione raffinata (MQI)");
     109//                      System.out.println("Edge-cut: " + mqiBisection.edgeCut() / 2);
     110                        double newConductance = ((double)mqiBisection.edgeCut() / 2) / Math.min(mqiBisection.getSubgraph().totalDegree(),mqiBisection.getComplement().totalDegree());
     111                        System.out.println("Conductance: " + newConductance);
     112                       
     113                       
     114                        if(newConductance < 1) {
     115                                System.out.println("CLUSTER "+ i + ":  V=" + clusterGraph.getVertexCount() + ", E=" + clusterGraph.getEdgeCount()+".");
     116                                clusters.add(cluster);
     117                        }
     118                       
    65119                        Iterator<Node> clustersNode = cluster.iterator();
    66120                        while(clustersNode.hasNext()){
    67121                                g.removeVertex(clustersNode.next());
    68122                        }
    69                        
    70                        
    71                         if(cluster.size()>10) {
    72                                 clusters.add(cluster);
    73                         }
    74                         System.out.println("CLUSTER "+ i + ": " + cluster);
    75123                }
    76124                Util.viewClusters(gclone, clusters);

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

    r17 r18  
    1616import weka.clusterers.forMetisMQI.graph.Node;
    1717import weka.clusterers.forMetisMQI.graph.Subgraph;
    18 import weka.clusterers.forMetisMQI.graph.UndirectedGraph;
    1918import weka.clusterers.forMetisMQI.util.Util;
    2019import edu.uci.ics.jung.algorithms.flows.EdmondsKarpMaxFlow;
    … …  
    2726
    2827        static private Set<Node> DFSReversed(Node currentNode,
    29                         DirectedGraph<Node, Edge> g, Map<Edge, Number> edgeFlowMap, Set<Node> marked) {
     28                        DirectedGraph<Node, Edge> g, Map<Edge, Number> edgeFlowMap,
     29                        Set<Node> marked) {
    3030                Collection<Edge> inEdges = g.getInEdges(currentNode);
    3131                Set<Node> result = new HashSet<Node>();
    … …  
    4747                return result;
    4848        }
    49 
    50 
    5149
    5250        static private Set<Node> BFSReversed(Node sink,
    … …  
    8381
    8482        static private DirectedGraph<Node, Edge> prepareDirectedGraph(
    85                         Bisection partition, Node source, Node sink) {
     83                        Bisection partition, Node source, Node sink, boolean forConductance) {
    8684                Subgraph A = null;
    8785                Subgraph B = null;
    … …  
    9492                        B = partition.getSubgraph();
    9593                }
    96                 int a = A.getVertexCount();
     94                int a = 0;
     95                if (!forConductance)
     96                        a = A.getVertexCount();
     97                else {
     98                        Iterator<Node> aIterator = A.iterator();
     99                        while(aIterator.hasNext()) {
     100                                a += partition.getGraph().degree(aIterator.next());
     101                        }
     102                }
    97103                int c = partition.edgeCut() / 2;
    98104
    … …  
    120126                g.addVertex(sink);
    121127
    122                
    123                 //build the edges from source to each node of A which previously was connected
    124                 //with a node of B.
     128                // build the edges from source to each node of A which previously was
     129                // connected
     130                // with a node of B.
    125131                nodes = B.iterator();
    126132                while (nodes.hasNext()) {
    … …  
    131137                                if (A.contains(v)) {
    132138                                        Edge e = g.findEdge(source, v);
    133                                         if(e != null) {
     139                                        if (e != null) {
    134140                                                e.setCapacity(e.getCapacity() + a);
    135141                                        } else {
    136                                                 g.addEdge(new Edge(Integer.toString(id), 1, a), source, v);
     142                                                g.addEdge(new Edge(Integer.toString(id), 1, a), source,
     143                                                                v);
    137144                                                id++;
    138145                                        }
    … …  
    144151                while (nodes.hasNext()) {
    145152                        Node u = nodes.next();
    146                         g.addEdge(new Edge(Integer.toString(id), 1, c), u, sink);
     153                        if(forConductance)
     154                                //FIXME: CONTROLLAMI
     155                                g.addEdge(new Edge(Integer.toString(id), 1, c * partition.getGraph().degree(u)), u, sink);
     156                        else
     157                                g.addEdge(new Edge(Integer.toString(id), 1, c), u, sink);
    147158                        id++;
    148159                }
    … …  
    158169         * @return
    159170         */
    160         static public Set<Node> mqi(Bisection partition) {
     171        static public Set<Node> mqi(Bisection partition, boolean forConductance) {
    161172//              System.out.println("INITIAL BISECTION: " + partition.toString());
    162173                boolean finished = false;
    163174                Bisection bisection = partition;
    164                 Set<Node> cluster = new HashSet<Node>(partition
    165                                 .getSmallerNotEmptySubgraph().createInducedSubgraph()
    166                                 .getVertices());
     175                Set<Node> cluster = new HashSet<Node>(partition.getSmallerNotEmptySubgraph()
     176                                .createInducedSubgraph().getVertices());
    167177                int maxFlowThreshold = Integer.MAX_VALUE;
    168178                while (!finished) {
    … …  
    170180                        Node sink = new Node("$$$$T");
    171181                        DirectedGraph<Node, Edge> directedGraph = prepareDirectedGraph(
    172                                         bisection, source, sink);
     182                                        bisection, source, sink, true);
    173183                        Transformer<Edge, Number> capTransformer = new Transformer<Edge, Number>() {
    174184                                public Double transform(Edge e) {
    … …  
    189199                                        edgeFactory);
    190200
    191                         maxFlowThreshold = bisection.getSmallerNotEmptySubgraph()
    192                                         .getVertexCount()
    193                                         * bisection.edgeCut() / 2;
     201                        if (!forConductance)
     202                                maxFlowThreshold = bisection.getSmallerNotEmptySubgraph()
     203                                                .getVertexCount()
     204                                                * bisection.edgeCut() / 2;
     205                        else {
     206                                Iterator<Node> aIterator = bisection.getSmallerNotEmptySubgraph().iterator();
     207                                maxFlowThreshold = 0;
     208                                while(aIterator.hasNext())
     209                                        maxFlowThreshold += partition.getGraph().degree(aIterator.next());
     210                                maxFlowThreshold = maxFlowThreshold
     211                                                * (bisection.edgeCut() / 2);
     212                        }
    194213                        alg.evaluate();
    195 //                      Util.viewFlowGraph(directedGraph, edgeFlowMap);
     214//                       Util.viewFlowGraph(directedGraph, edgeFlowMap);
    196215//                      System.out.println("MAX FLOW: " + alg.getMaxFlow() + " THRESHOLD: "
    197216//                                      + maxFlowThreshold);
    198217                        if (alg.getMaxFlow() < maxFlowThreshold) {
    199                                 cluster = DFSReversed(sink, directedGraph, edgeFlowMap, new HashSet<Node>());
    200                                 cluster.remove(sink);
    201                                  bisection = new Bisection(new Subgraph(bisection.getGraph(),
    202                                  cluster));
    203 //                              System.out.println("NEW BISECTION: " + bisection.toString());
     218                                Set<Node> dfsResult = DFSReversed(sink, directedGraph,
     219                                                edgeFlowMap, new HashSet<Node>());
     220                                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;
    204229                        } else
    205230                                finished = true;

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

    r14 r18  
    3838        /**
    3939         * Given a bisection of the finer graph and the stack of graphs which yielded the finer graph,
    40          * it returns the bisection projected into the coarser graph. 
     40         * it returns the bisection projected into the coarser graph.
    4141         * @param stack
    4242         * @param partition
    … …  
    4747                        CoarserGraphElement element = stack.pop();
    4848                        partition = uncoarseOneStep(partition,element);
     49                        partition = GraphAlgorithms.KLRefinement(partition);
    4950                }
    5051                return partition;

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

    r15 r18  
    122122        }
    123123       
    124         public Bisection copy(){
     124        public Bisection clone(){
    125125                Bisection clone = new Bisection();
    126126                clone.a = (Subgraph) a.clone();
    127127                clone.b = (Subgraph) b.clone();
     128                clone.g = g.clone();
    128129                clone.marked = new HashSet<Node>();
    129130                return clone;

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

    r15 r18  
    260260                return FilterUtils.createInducedSubgraph(nodes,g);
    261261        }
     262       
     263        public int totalDegree() {
     264                int result = 0;
     265                Iterator<Node> nodeIterator = iterator();
     266                while(nodeIterator.hasNext()) {
     267                        int degree = g.degree(nodeIterator.next());
     268                        result += degree;
     269                }
     270                return result;
     271        }
    262272}

  • src/main/java/weka/clusterers/forMetisMQI/util/Util.java

    r15 r18  
    55import java.awt.Paint;
    66import java.util.HashMap;
     7import java.util.HashSet;
    78import java.util.Iterator;
    89import java.util.Map;
    … …  
    1819import weka.clusterers.forMetisMQI.graph.UndirectedGraph;
    1920import edu.uci.ics.jung.algorithms.layout.FRLayout;
     21import edu.uci.ics.jung.algorithms.layout.ISOMLayout;
    2022import edu.uci.ics.jung.algorithms.layout.Layout;
    2123import edu.uci.ics.jung.graph.Graph;
    … …  
    2426
    2527public class Util {
     28       
     29        public static void viewCluster(Graph<Node, Edge> g, Set<Node> cluster) {
     30                Set<Set<Node>> clusters = new HashSet<Set<Node>>();
     31                clusters.add(cluster);
     32                viewClusters(g, clusters);
     33        }
     34       
     35       
    2636        public static void viewClusters(Graph<Node, Edge> g, Set<Set<Node>> clusters) {
    2737                Layout<Node, Edge> layout = new FRLayout<Node, Edge>(g);
Note: See TracChangeset for help on using the changeset viewer.