source: src/main/java/weka/clusterers/forMetisMQI/Coarse.java @ 10

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

Corretti alcuni bachi inseriti con la migrazione a Jung.
File size: 6.0 KB
Line 
1package weka.clusterers.forMetisMQI;
2
3import java.io.PrintStream;
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 edu.uci.ics.jung.graph.util.Pair;
12
13public class Coarse {
14       
15        private static boolean debug = false;
16        private static PrintStream debugStream = System.err;
17        private static int finerSize = 5;
18
19        /**
20         * Return true if the vertex v is matched
21         *
22         * @param g graph
23         * @param v
24         *            the index of the vertex
25         * @return true if the vertex v is matched, false o.w.
26         */
27        private static boolean isMatched(Map<Node,Node> match, Node v) {
28                if(match.containsKey(v))
29                        return !match.get(v).equals(v);
30                else
31                        return false;
32        }
33
34        private static void RMMatch(UndirectedGraph g, Map<Node,Node> match, Map<Node,Node> map) {
35                int labelCounter = 0;
36                Iterator<Node> nodeIterator = g.vtxsPermutation().iterator();
37                while (nodeIterator.hasNext()) {
38                        Node u = nodeIterator.next();
39                        if (debug)
40                                debugStream.println("Visiting node " + u + " Matched = " + isMatched(match,u));
41                        if (!isMatched(match,u)) {
42                                boolean foundMatch = false;
43                                Node matchedNode = null;
44                                Iterator<Node> iterator = g.getNeighborsPermutation(u).iterator();
45                                while(iterator.hasNext() && !foundMatch){
46                                        Node v = iterator.next();
47                                        if (!isMatched(match,v)) {
48                                                matchedNode = v;
49                                                foundMatch = true;
50                                                if (debug)
51                                                        debugStream.println("Found a match with node "
52                                                                        + matchedNode);
53                                        }
54                                }
55                                if (debug && !foundMatch)
56                                        debugStream.println("There aren't unmatched neighbors.");
57                                Node newNode = new Node(Integer.toString(labelCounter));
58                                if(foundMatch) {
59                                        match.put(u, matchedNode);
60                                        match.put(matchedNode, u);
61                                        map.put(u, newNode);
62                                        map.put(matchedNode, newNode);
63                                        if(debug) debugStream.println("Contracting node " + u + " with " + matchedNode + ". Node id: " + getMappedNode(map, u));
64                                } else {
65                                        match.put(u, u);
66                                        map.put(u, newNode);
67                                        if(debug) debugStream.println("Node " + u + " with " + " new node id: " + getMappedNode(map, u));
68                                }
69                                labelCounter++;
70                        }
71                }
72        }
73       
74        private static Node getMatchedNode(Map<Node,Node> match, Node u) {
75                return match.get(u);
76        }
77       
78        private static Node getMappedNode(Map<Node,Node> map, Node u) {
79                return map.get(u);
80        }
81       
82        /**
83         * Return a new contracted graph.
84         */
85        private static UndirectedGraph contract(UndirectedGraph g, Map<Node,Node> match, Map<Node,Node> map) {
86                UndirectedGraph output = new UndirectedGraph();
87                Iterator<Node> iterator = g.getVertices().iterator();
88                int i = 0;
89                while(iterator.hasNext()) {
90                        Node u = iterator.next();
91                        output.addVertex(getMappedNode(map,u));
92                       
93                        Set<Node> neighbors = new HashSet<Node>();
94                        Iterator<Node> it = g.getNeighbors(u).iterator();
95                        while(it.hasNext())
96                                neighbors.add(getMappedNode(map, it.next()));
97                        it = g.getNeighbors(getMatchedNode(match, u)).iterator();
98                        while(it.hasNext())
99                                neighbors.add(getMappedNode(map, it.next()));
100                        neighbors.remove(getMappedNode(map,u));
101                        it = neighbors.iterator();
102                        while(it.hasNext()) {
103                                Node v = it.next();
104                                output.addVertex(v);
105                                output.addEdge(new Edge(Integer.toString(i),0,0),getMappedNode(map,u), v);
106                                i++;
107                        }
108                }
109               
110                //calcolo dei pesi del nuovo grafo: per ogni arco (u,v) && u < v.
111                //w(map(u),map(v)) += w(u,v).
112               
113                Iterator<Edge> edgeIterator = g.getEdges().iterator();
114                while(edgeIterator.hasNext()) {
115                        Edge oldEdge = edgeIterator.next();
116                        Pair<Node> srcDst = g.getEndpoints(oldEdge);
117                        Node src = srcDst.getFirst();
118                        Node dst = srcDst.getSecond();
119                        Node srcMapped = getMappedNode(map, src);
120                        Node dstMapped = getMappedNode(map, dst);
121                        if(!srcMapped.equals(dstMapped) && output.containsEdge(srcMapped, dstMapped)) {
122                                Edge newEdge = output.findEdge(srcMapped, dstMapped);
123                                newEdge.setWeight(newEdge.getWeight() + oldEdge.getWeight());
124                        }
125                }
126                iterator = g.getVertices().iterator();
127                Set<Node> nodesComplete = new HashSet<Node>();
128                while(iterator.hasNext()) {
129                        Node u = iterator.next();
130                        if(isMatched(match,u)) {
131                                Node v = getMatchedNode(match,u);
132                                if(!nodesComplete.contains(u)) {
133                                        getMappedNode(map,u).setVwgt(u.getVwgt() + v.getVwgt());
134                                        getMappedNode(map,u).setCewgt(u.getCewgt() + v.getCewgt() + g.findEdge(u, v).getWeight());
135                                        nodesComplete.add(u);
136                                        nodesComplete.add(v);
137                                }
138                        } else {
139                                getMappedNode(map,u).setVwgt(u.getVwgt());
140                                getMappedNode(map,u).setCewgt(u.getCewgt());
141                        }
142                }
143                return output;
144        }
145
146        /**
147         * Performs the first stage of the METIS algorithm, using RM.
148         */
149        private static CoarserGraphElement coarseOneStep(UndirectedGraph g) {
150                UndirectedGraph projected = g;
151                UndirectedGraph contracted = null;
152                Map<Node,Node> match = new HashMap<Node,Node>();
153                Map<Node,Node> map = new HashMap<Node,Node>();
154                RMMatch(g,match,map);
155                contracted = contract(g,match,map);
156                return new CoarserGraphElement(contracted, projected, match, map);
157        }
158
159       
160        /**
161         * Performs at least one contraction of the given the graph, and goes on until the graph
162         * is under the desidered size (see setFinerSize()).
163         * @param g
164         * @return the stack of contracted graphs
165         */
166        public static Stack<CoarserGraphElement> coarse(UndirectedGraph g) {
167                Stack<CoarserGraphElement> stack = new Stack<CoarserGraphElement>();
168                CoarserGraphElement e = null;
169                UndirectedGraph curr = g;
170                int i = 0;
171               
172            do {
173                if(debug)
174                        debugStream.println("--------CONTRACTION-nr" + i +"------------------------------");
175                e = coarseOneStep(curr);
176                stack.push(e);
177                curr = e.getContracted();
178                if(debug) {
179                        debugStream.println("-----------EXPANDED----------------------------------");
180                        debugStream.println(e.getProjected().toString());
181                        debugStream.println("-----------CONTRACTED--------------------------------");
182                        debugStream.println(e.getContracted().toString());
183                }
184                i++;
185            } while(e.getProjected().getVertexCount() > e.getContracted().getVertexCount() && e.getContracted().getVertexCount() > finerSize);
186            return stack;
187        }
188
189        public static void setFinerSize(int i) {
190                finerSize = i;
191        }
192}
Note: See TracBrowser for help on using the repository browser.