source: src/main/java/weka/clusterers/forMetisMQI/MQI.java @ 21

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

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