Changeset 12 for src/main


Ignore:
Timestamp:
Sep 16, 2010, 7:01:57 PM (14 years ago)
Author:
gnappo
Message:

Visualizzazione dei cluster. (da spostare)

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

Legend:

Unmodified
Added
Removed
  • src/main/java/weka/clusterers/forMetisMQI/GraphAlgorithms.java

    r11 r12  
    11package weka.clusterers.forMetisMQI;
    22
     3import java.util.HashSet;
     4import java.util.Set;
    35import java.util.Stack;
    46
     
    1012
    1113public class GraphAlgorithms {
    12        
     14
    1315        public Bisection KL(UndirectedGraph g) {
    1416                Bisection partition = new Bisection(g);
     
    1618                int bestEdgeCut = Integer.MAX_VALUE;
    1719                Node u = partition.getCandidate();
    18                 while(u != null) {
     20                while (u != null) {
    1921                        partition.swap(u);
    20                         if(partition.edgeCut() <= bestEdgeCut) {
     22                        if (partition.edgeCut() <= bestEdgeCut) {
    2123                                bestEdgeCut = partition.edgeCut();
    2224                                result = partition.copy();
     
    2628                return result;
    2729        }
    28        
     30
    2931        public void METIS(UndirectedGraph g) {
    30                 MQI.viewGraph(g);
    31                 Bisection partition = null;
    32                 Coarse.setFinerSize(8);
    33                 Stack<CoarserGraphElement> stack = Coarse.coarse(g);
    34                 if(stack.size() > 0) {
    35                         partition = KL(stack.peek().getContracted());
    36                         System.out.println(partition.toString());
    37                         partition = new Uncoarse().uncoarse(stack, partition);
    38                         System.out.println(partition.toString());
     32//              MQI.viewGraph(g);
     33                Set<Set<Node>> clusters = new HashSet<Set<Node>>();
     34                for (int i = 0; i < 8; i++) {
     35                        Coarse.setFinerSize(8);
     36                        Stack<CoarserGraphElement> stack = Coarse.coarse(g);
     37                        Bisection partition = null;
     38                        if (stack.size() > 0) {
     39                                partition = KL(stack.peek().getContracted());
     40//                              System.out.println(partition.toString());
     41                                partition = new Uncoarse().uncoarse(stack, partition);
     42//                              System.out.println(partition.toString());
     43                                Set<Node> cluster = MQI.mqi(partition);
     44                                clusters.add(cluster);
     45//                              Set<Set<Node>> foundCluster = new HashSet<Set<Node>>();
     46//                              foundCluster.add(cluster);
     47//                              MQI.viewClusters(g, foundCluster);
     48                        }
    3949                }
    40                 System.out.println("AAAAAA");
    41                 System.out.println(MQI.mqi(partition).toString());
    42                
     50                MQI.viewClusters(g, clusters);
    4351        }
    4452
  • src/main/java/weka/clusterers/forMetisMQI/MQI.java

    r11 r12  
    11package weka.clusterers.forMetisMQI;
    22
     3import java.awt.Color;
    34import java.awt.Dimension;
     5import java.awt.Paint;
     6import java.util.Collection;
    47import java.util.HashMap;
     8import java.util.HashSet;
    59import java.util.Iterator;
    610import java.util.Map;
    711import java.util.Set;
     12import java.util.Stack;
    813
    914import javax.swing.JFrame;
     
    3035        static int i = -1;
    3136       
     37        public static void viewClusters(Graph<Node, Edge> g, Set<Set<Node>> clusters) {
     38                Layout<Node, Edge> layout = new KKLayout<Node, Edge>(g);
     39                layout.setSize(new Dimension(800, 600)); // sets the initial size of the space
     40                // The BasicVisualizationServer<V,E> is parameterized by the edge types
     41                BasicVisualizationServer<Node, Edge> vv = new BasicVisualizationServer<Node, Edge>(
     42                                layout);
     43
     44                class VertexPaintTransformer implements Transformer<Node, Paint> {
     45                        Set<Set<Node>> clusters = null;
     46                        Map<Set<Node>, Color> clustersColor = null;
     47
     48                        public Set<Node> getCluster(Node node) {
     49                                Iterator<Set<Node>> clusterIterator = clusters.iterator();
     50                                while (clusterIterator.hasNext()) {
     51                                        Set<Node> cluster = clusterIterator.next();
     52                                        if (cluster.contains(node))
     53                                                return cluster;
     54                                }
     55                                return null;
     56                        }
     57
     58                        public VertexPaintTransformer(Set<Set<Node>> clusters) {
     59                                this.clusters = clusters;
     60                                clustersColor = new HashMap<Set<Node>, Color>(clusters.size());
     61                                Iterator<Set<Node>> clusterIterator = clusters.iterator();
     62                                while (clusterIterator.hasNext()) {
     63                                        Set<Node> cluster = clusterIterator.next();
     64                                        clustersColor.put(cluster, new Color(Random.instance()
     65                                                        .nextInt(256), Random.instance().nextInt(256),
     66                                                        Random.instance().nextInt(256)));
     67                                }
     68                        }
     69
     70                        public Paint transform(Node i) {
     71                                Set<Node> cluster = getCluster(i);
     72                                if (cluster == null)
     73                                        return Color.RED;
     74                                else
     75                                        return clustersColor.get(getCluster(i));
     76                        }
     77                }
     78
     79                Transformer<Node, Paint> vertexPaint = new VertexPaintTransformer(
     80                                clusters);
     81                vv.setPreferredSize(new Dimension(800, 600)); // Sets the viewing area
     82                                                                                                                // size
     83                vv.getRenderContext().setVertexLabelTransformer(
     84                                new ToStringLabeller<Node>());
     85                vv.getRenderContext().setEdgeLabelTransformer(
     86                                new ToStringLabeller<Edge>());
     87                vv.getRenderContext().setVertexFillPaintTransformer(vertexPaint);
     88                JFrame frame = new JFrame("Graph View");
     89                frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
     90                frame.getContentPane().add(vv);
     91                frame.pack();
     92                frame.setVisible(true);
     93        }
     94       
    3295        public static void viewGraph(Graph<Node, Edge> g){
    3396                Layout<Node, Edge> layout = new KKLayout<Node, Edge>(g);
     
    47110        }
    48111
    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();
     112        static private Set<Node> BFSReversed(Node sink, DirectedGraph<Node, Edge> g, Map<Edge, Number> edgeFlowMap) {
     113                Set<Node> result = new HashSet<Node>();
     114                Set<Node> visitedNodes = new HashSet<Node>();
     115                Stack<Node> nodesToVisit = new Stack<Node>();
     116                result.add(sink);
     117                nodesToVisit.push(sink);
     118                while(!nodesToVisit.empty()) {
     119                        Node currentNode = nodesToVisit.pop();
     120                        visitedNodes.add(currentNode);
     121                        Collection<Edge> inEdges = g.getInEdges(currentNode);
     122                        Iterator<Edge> inEdgesIterator = inEdges.iterator();
     123                        while(inEdgesIterator.hasNext()) {
     124                                Edge edge = inEdgesIterator.next();
     125                                Node src = g.getSource(edge);
     126                                Edge reverseEdge = g.findEdge(src, currentNode);
     127                                if((reverseEdge != null) && ((Integer)edgeFlowMap.get(reverseEdge) < reverseEdge.getCapacity())) {
     128                                        if(!nodesToVisit.contains(src) && !visitedNodes.contains(src)) {
     129                                                nodesToVisit.push(src);
     130                                        }
     131                                        result.add(src);
     132                                }
     133                        }
     134                }
     135                return result;
    63136        }
    64137       
     
    66139                Subgraph A = null;
    67140                Subgraph B = null;
    68                 if(partition.getSubgraph().getVertexCount() > partition.getComplement().getVertexCount()) {
     141                if(partition.getSubgraph().getVertexCount() < partition.getComplement().getVertexCount()) {
    69142                        A = partition.getSubgraph();
    70143                        B = partition.getComplement();
     
    123196        }
    124197       
    125         static public Bisection mqi(Bisection partition) {
     198        /**
     199         * Given a partion of a graph, execute the Max-Flow Quotient-cut Improvement algorithm,
     200         * to find an improved cut and then returns the cluster which yields the best quotient cut.
     201         * @param partition
     202         * @return
     203         */
     204        static public Set<Node> mqi(Bisection partition) {
     205                System.out.println("INITIAL BISECTION: " + partition.toString());
    126206                boolean finished = false;
    127207                Bisection bisection = partition;
     208                Set<Node> cluster = new HashSet<Node>(partition.getSubgraph().createInducedSubgraph().getVertices());
    128209                int maxFlowThreshold = Integer.MAX_VALUE;
    129210                while (!finished) {
    130                         UndirectedGraph startingGraph = partition.getGraph();
    131211                        Node source = new Node("S");
    132212                        Node sink = new Node("T");
    133                         DirectedGraph<Node, Edge> g = prepareDirectedGraph(bisection, source, sink);
     213                        DirectedGraph<Node, Edge> directedGraph = prepareDirectedGraph(bisection, source, sink);
    134214                        Transformer<Edge, Number> capTransformer = new Transformer<Edge, Number>() {
    135215                                public Double transform(Edge e) {
     
    147227                        };
    148228                        EdmondsKarpMaxFlow<Node, Edge> alg = new EdmondsKarpMaxFlow<Node, Edge>(
    149                                         g, source, sink, capTransformer, edgeFlowMap, edgeFactory);
     229                                        directedGraph, source, sink, capTransformer, edgeFlowMap, edgeFactory);
    150230                       
    151                         maxFlowThreshold = getMaxCardinality(bisection) * bisection.edgeCut() / 2;
     231                        maxFlowThreshold = bisection.getSmallerSubgraph().getVertexCount() * bisection.edgeCut() / 2;
    152232                        alg.evaluate();
     233                        System.out.println("MAX FLOW: " + alg.getMaxFlow() + " THRESHOLD: " + maxFlowThreshold);
    153234                        if(alg.getMaxFlow() < maxFlowThreshold) {
    154235                                Set<Node> sinkPartition = alg.getNodesInSinkPartition();
     236                                System.out.println(sinkPartition);
    155237                                Set<Node> sourcePartition = alg.getNodesInSourcePartition();
    156                                 bisection = prepareBisection(startingGraph, sourcePartition, sinkPartition);
     238                                System.out.println(sourcePartition);
     239                                bisection = prepareBisection(bisection.getSmallerSubgraph().createInducedSubgraph(), sourcePartition, sinkPartition);
     240//                              bisection = new Bisection(new Subgraph(bisection.getSmallerSubgraph().createInducedSubgraph(), BFSReversed(sink, directedGraph, edgeFlowMap)));
     241                                System.out.println("NEW BISECTION: " + bisection.toString());
     242                                cluster = sinkPartition;
    157243                        } else
    158244                                finished = true;
    159245                }
    160                 return bisection;
     246                return cluster;
    161247        }
    162248       
  • src/main/java/weka/clusterers/forMetisMQI/graph/Bisection.java

    r11 r12  
    137137                return out;
    138138        }
     139       
     140        /**
     141         * Returns the smaller subgraph of this bisection.
     142         * @return
     143         */
     144        public Subgraph getSmallerSubgraph() {
     145                if(a.getVertexCount() < b.getVertexCount())
     146                        return a;
     147                else
     148                        return b;
     149        }
    139150}
Note: See TracChangeset for help on using the changeset viewer.