source: branches/MetisMQI/src/main/java/weka/clusterers/forMetisMQI/MQI.java

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

Taggata versione per la demo e aggiunto branch.
File size: 7.2 KB
Line 
1package weka.clusterers.forMetisMQI;
2
3import java.util.Collection;
4import java.util.HashMap;
5import java.util.HashSet;
6import java.util.Iterator;
7import java.util.Map;
8import java.util.Set;
9import java.util.Stack;
10
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;
20import edu.uci.ics.jung.graph.DirectedGraph;
21import edu.uci.ics.jung.graph.DirectedSparseGraph;
22import weka.clusterers.forMetisMQI.util.Configuration;
23import weka.clusterers.forMetisMQI.util.GraphsFrame;
24import weka.clusterers.forMetisMQI.util.Util;
25
26public class MQI {
27
28        static int i = -1;
29
30        static private Set<Node> DFSReversed(Node currentNode,
31                        DirectedGraph<Node, Edge> g, Map<Edge, Number> edgeFlowMap,
32                        Set<Node> marked) {
33                Collection<Edge> inEdges = g.getInEdges(currentNode);
34                Set<Node> result = new HashSet<Node>();
35                result.add(currentNode);
36                Iterator<Edge> inEdgesIterator = inEdges.iterator();
37                while (inEdgesIterator.hasNext()) {
38                        Edge edge = inEdgesIterator.next();
39                        Node src = g.getSource(edge);
40                        Edge reverseEdge = g.findEdge(src, currentNode);
41                        if (reverseEdge != null && !marked.contains(src)) {
42                                int flow = (Integer) edgeFlowMap.get(reverseEdge);
43                                int capacity = reverseEdge.getCapacity();
44                                if (flow < capacity) {
45                                        marked.add(src);
46                                        result.addAll(DFSReversed(src, g, edgeFlowMap, marked));
47                                }
48                        }
49                }
50                return result;
51        }
52
53        static private Set<Node> BFSReversed(Node sink,
54                        DirectedGraph<Node, Edge> g, Map<Edge, Number> edgeFlowMap) {
55                Set<Node> result = new HashSet<Node>();
56                Set<Node> visitedNodes = new HashSet<Node>();
57                Stack<Node> nodesToVisit = new Stack<Node>();
58                result.add(sink);
59                nodesToVisit.push(sink);
60                while (!nodesToVisit.empty()) {
61                        Node currentNode = nodesToVisit.pop();
62                        visitedNodes.add(currentNode);
63                        Collection<Edge> inEdges = g.getInEdges(currentNode);
64                        Iterator<Edge> inEdgesIterator = inEdges.iterator();
65                        while (inEdgesIterator.hasNext()) {
66                                Edge edge = inEdgesIterator.next();
67                                Node src = g.getSource(edge);
68                                Edge reverseEdge = g.findEdge(src, currentNode);
69                                if (reverseEdge != null) {
70                                        int flow = (Integer) edgeFlowMap.get(reverseEdge);
71                                        int capacity = reverseEdge.getCapacity();
72                                        if (flow < capacity) {
73                                                if (!nodesToVisit.contains(src)
74                                                                && !visitedNodes.contains(src)) {
75                                                        nodesToVisit.push(src);
76                                                }
77                                                result.add(src);
78                                        }
79                                }
80                        }
81                }
82                return result;
83        }
84
85        static private DirectedGraph<Node, Edge> prepareDirectedGraph(
86                        Subgraph A, Node source, Node sink, boolean forConductance) {
87                Bisection bisection = new Bisection(A);
88                Subgraph B = bisection.getComplement();
89                int a = 0;
90                if (!forConductance)
91                        a = A.getVertexCount();
92                else {
93//                      a = Math.min(B.totalDegree(),A.totalDegree());
94                        a = A.totalDegree();
95                }
96                int c = bisection.edgeCut() / 2;
97
98                DirectedGraph<Node, Edge> g = new DirectedSparseGraph<Node, Edge>();
99                Iterator<Node> nodes = A.iterator();
100                while (nodes.hasNext()) {
101                        Node u = nodes.next();
102                        g.addVertex(u);
103                }
104                nodes = A.iterator();
105                int id = 0;
106                while (nodes.hasNext()) {
107                        Node u = nodes.next();
108                        Iterator<Node> neighbors = A.getNeighbors(u).iterator();
109                        while (neighbors.hasNext()) {
110                                Node v = neighbors.next();
111                                g.addEdge(new Edge(Integer.toString(id), A.getWeight(u, v), a),
112                                                u, v);
113                                id++;
114                        }
115                }
116
117                g.addVertex(source);
118                g.addVertex(sink);
119
120                // build the edges from source to each node of A which previously was
121                // connected
122                // with a node of B.
123                nodes = B.iterator();
124                while (nodes.hasNext()) {
125                        Node u = nodes.next();
126                        Iterator<Node> neighbors = B.getGraph().getNeighbors(u).iterator();
127                        while (neighbors.hasNext()) {
128                                Node v = neighbors.next();
129                                if (A.contains(v)) {
130                                        Edge e = g.findEdge(source, v);
131                                        if (e != null) {
132                                                e.setCapacity(e.getCapacity() + a);
133                                        } else {
134                                                g.addEdge(new Edge(Integer.toString(id), 1, a), source,
135                                                                v);
136                                                id++;
137                                        }
138                                }
139                        }
140                }
141
142                nodes = A.iterator();
143                while (nodes.hasNext()) {
144                        Node u = nodes.next();
145                        if(forConductance)
146                                g.addEdge(new Edge(Integer.toString(id), 1, c * bisection.getGraph().degree(u)), u, sink);
147                        else
148                                g.addEdge(new Edge(Integer.toString(id), 1, c), u, sink);
149                        id++;
150                }
151                return g;
152        }
153
154        /**
155         * Given a partion of a graph, execute the Max-Flow Quotient-cut Improvement
156         * algorithm, to find an improved cut and then returns the cluster which
157         * yields the best quotient cut.
158         *
159         * @param partition
160         * @return
161         */
162        static public Set<Node> mqi(Bisection partition, boolean forConductance) {
163//              System.out.println("INITIAL BISECTION: " + partition.toString());
164                UndirectedGraph startingGraph = partition.getGraph();
165                boolean finished = false;
166                Bisection bisection = partition;
167                Set<Node> cluster = new HashSet<Node>(partition.getSmallerSubgraph()
168                                .createInducedSubgraph().getVertices());
169//              System.out.println("IMPROVING SUBGRAPH: " + cluster);
170                int maxFlowThreshold = Integer.MAX_VALUE;
171                while (!finished) {
172                        Node source = new Node("$$$$S");
173                        Node sink = new Node("$$$$T");
174                        Subgraph A = new Subgraph(startingGraph,cluster);
175                        DirectedGraph<Node, Edge> directedGraph = prepareDirectedGraph(A, source, sink, true);
176                        Transformer<Edge, Number> capTransformer = new Transformer<Edge, Number>() {
177                                public Double transform(Edge e) {
178                                        return (double) e.getCapacity();
179                                }
180                        };
181                        Map<Edge, Number> edgeFlowMap = new HashMap<Edge, Number>();
182                        i = -1;
183                        // This Factory produces new edges for use by the algorithm
184                        Factory<Edge> edgeFactory = new Factory<Edge>() {
185                                public Edge create() {
186                                        i++;
187                                        return new Edge("$$$$" + Integer.toString(i), 1, 1);
188                                }
189                        };
190                        EdmondsKarpMaxFlow<Node, Edge> alg = new EdmondsKarpMaxFlow<Node, Edge>(
191                                        directedGraph, source, sink, capTransformer, edgeFlowMap,
192                                        edgeFactory);
193
194                        if (!forConductance)
195                                maxFlowThreshold = A.getVertexCount()
196                                                * bisection.edgeCut() / 2;
197                        else {
198//                              maxFlowThreshold = Math.min(bisection.getLargerSubgraph().totalDegree(), bisection.getSmallerSubgraph().totalDegree());
199                                maxFlowThreshold = A.totalDegree();
200                                maxFlowThreshold = maxFlowThreshold
201                                                * (bisection.edgeCut() / 2);
202                        }
203                        System.out.print(".");
204                        alg.evaluate();
205                        System.out.print(".");
206                        if(Configuration.instance().getVerboseLevel() > 1)
207                                GraphsFrame.instance().addPanel(Util.panelFlowGraph(directedGraph, edgeFlowMap));
208                        System.out.println("MAX FLOW: " + alg.getMaxFlow() + " THRESHOLD: "
209                                        + maxFlowThreshold);
210                        if (alg.getMaxFlow() < maxFlowThreshold) {
211                                Set<Node> dfsResult = DFSReversed(sink, directedGraph,
212                                                edgeFlowMap, new HashSet<Node>());
213                                dfsResult.remove(sink);
214                                cluster = dfsResult;
215                                bisection = new Bisection(new Subgraph(
216                                        bisection.getGraph(), cluster));
217//                              System.out.println("REFINED BISECTION: " + bisection.toString());
218                                if(Configuration.instance().getVerboseLevel() > 1)
219                                        GraphsFrame.instance().addPanel(Util.panelCluster(bisection.getGraph().clone(), cluster));
220                        } else
221                                finished = true;
222                }
223                return cluster;
224        }
225
226}
Note: See TracBrowser for help on using the repository browser.