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