source: src/main/java/weka/clusterers/forMetisMQI/GraphAlgorithms.java @ 24

Last change on this file since 24 was 24, checked in by gnappo, 14 years ago

Inserita gestione pannelli per la visualizzazione grafi.

File size: 5.0 KB
Line 
1package weka.clusterers.forMetisMQI;
2
3import java.util.HashSet;
4import java.util.Iterator;
5import java.util.Set;
6import java.util.Stack;
7
8import weka.clusterers.forMetisMQI.graph.Bisection;
9import weka.clusterers.forMetisMQI.graph.Node;
10import weka.clusterers.forMetisMQI.graph.Subgraph;
11import weka.clusterers.forMetisMQI.graph.UndirectedGraph;
12import weka.clusterers.forMetisMQI.util.CoarserGraphElement;
13import weka.clusterers.forMetisMQI.util.Configuration;
14import weka.clusterers.forMetisMQI.util.GraphsFrame;
15import weka.clusterers.forMetisMQI.util.Util;
16
17public class GraphAlgorithms {
18
19       
20        static public Bisection KLRefinement(Bisection b) {
21                int remainingNumberOfSwap = 50;
22                Bisection partition = b;
23                Bisection result = partition;
24                int bestEdgeCut = partition.edgeCut();
25                Node u = partition.getCandidate();
26                while (u != null && remainingNumberOfSwap > 0) {
27                        partition.swap(u);
28                        if (partition.edgeCut() <= bestEdgeCut) {
29                                bestEdgeCut = partition.edgeCut();
30                                result = partition.clone();
31                                remainingNumberOfSwap = 50;
32                        } else
33                                remainingNumberOfSwap--;
34                        u = partition.getCandidate();
35                }
36                return result;
37        }
38       
39       
40        /**
41         * Given an undirected graph, performs the Kernighan-Li algorithm to find a bisection and
42         * then returns it.
43         * @param g
44         * @return
45         */
46        static public Bisection KL(UndirectedGraph g) {
47                int remainingNumberOfSwap = 50;
48                Bisection partition = new Bisection(g);
49                Bisection result = partition;
50                int bestEdgeCut = partition.edgeCut();
51                Node u = partition.getCandidate();
52                while (u != null && remainingNumberOfSwap > 0) {
53                        partition.swap(u);
54                        if (partition.edgeCut() <= bestEdgeCut) {
55                                bestEdgeCut = partition.edgeCut();
56                                result = partition.clone();
57                                remainingNumberOfSwap = 50;
58                        } else
59                                remainingNumberOfSwap--;
60                        u = partition.getCandidate();
61                }
62                return result;
63        }
64       
65        static public Bisection metis(UndirectedGraph g, int sizeFinerGraph) {
66                Coarse.setFinerSize(sizeFinerGraph);
67                Stack<CoarserGraphElement> stack = Coarse.coarse(g);
68                Bisection partition = null;
69                if (stack.size() > 0) {
70                        partition = KL(stack.peek().getContracted());
71                        if(Configuration.instance().getVerboseLevel() > 1) {
72                                GraphsFrame.instance().addPanel(Util.panelContractedGraph(stack.peek()));
73                                GraphsFrame.instance().addPanel(Util.panelContractedGraph(stack.peek(),partition.getSmallerSubgraph().createInducedSubgraph().getVertices()));
74                        }
75                        partition = Uncoarse.uncoarse(stack, partition);
76                }
77                return partition;
78        }
79
80        /**
81         * Given an UndirectedGraph, runs metis+mqi for <code>numberOfCluster</code> times and
82         * returns a set of clusters. With the third parameter you can control the maximum size of the finer
83         * graph during the coarsening phase. 
84         * @param g
85         * @param numberOfCluster
86         * @param sizeFinerGraph
87         */
88        static public Set<Set<Node>> metisMqi(UndirectedGraph g) {
89                int numberOfCluster = Configuration.instance().getNumberOfClusters();
90                boolean randomBisection = Configuration.instance().isRandomBisection();
91                int sizeFinerGraph = Configuration.instance().getSizeFinerGraph();
92                int verboseLevel = Configuration.instance().getVerboseLevel();
93                GraphsFrame gf = GraphsFrame.instance();
94                System.out.println("Vertex count: " + g.getVertexCount());
95                System.out.println("Edges count: " + g.getEdgeCount());
96                Set<Set<Node>> clusters = new HashSet<Set<Node>>();
97                UndirectedGraph gclone = g.clone();
98                for (int i = 0; i < numberOfCluster; i++) {
99                        Bisection bisection = null;
100                        if(verboseLevel > 1)
101                                gf.addPanel(Util.panelGraph(g.clone()));
102                        if(!randomBisection)
103                                bisection = metis(g,sizeFinerGraph);
104                        else
105                                bisection = new Bisection(g);
106                       
107                        if(verboseLevel > 1)
108                                gf.addPanel(Util.panelCluster(g.clone(),bisection.getSmallerSubgraph().createInducedSubgraph().getVertices()));
109                       
110                        System.out.print("Partizione iniziale: ");
111                        System.out.print("V1: " + bisection.getSubgraph().getVertexCount());
112                        System.out.print(" V2: " + bisection.getComplement().getVertexCount());
113                        System.out.println(" EC: " + bisection.edgeCut() * 0.5);
114                        System.out.println("Conductance: " + 
115                                        ((double)bisection.edgeCut() / 2) / Math.min(bisection.getSubgraph().totalDegree(),bisection.getComplement().totalDegree()));
116                        Set<Node> cluster = MQI.mqi(bisection,true);
117                       
118                        UndirectedGraph clusterGraph = new Subgraph(gclone,cluster).createInducedSubgraph();
119                       
120//                      System.out.println(cluster);
121                        Bisection mqiBisection = new Bisection(new Subgraph(g,cluster));
122                        System.out.println("Partizione raffinata (MQI)");
123                        double newConductance = ((double)mqiBisection.edgeCut() / 2) / Math.min(mqiBisection.getSubgraph().totalDegree(),mqiBisection.getComplement().totalDegree());
124                        System.out.println("Conductance: " + newConductance);
125                       
126                        System.out.println("CLUSTER "+ i + ":  V=" + clusterGraph.getVertexCount() + ", E=" + clusterGraph.getEdgeCount()+".");
127                        clusters.add(cluster);
128                       
129                        System.out.println();
130                        Iterator<Node> clustersNode = cluster.iterator();
131                        while(clustersNode.hasNext()){
132                                g.removeVertex(clustersNode.next());
133                        }
134                }
135                if(verboseLevel > 0)
136                        gf.addPanel(Util.panelClusters(gclone, clusters));
137                gf.setVisible(true);
138                return clusters;
139        }
140
141}
Note: See TracBrowser for help on using the repository browser.