]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | //-*-c++-*- |
2 | //======================================================================= | |
3 | // Copyright 1997-2001 University of Notre Dame. | |
4 | // Authors: Lie-Quan Lee, Jeremy Siek | |
5 | // | |
6 | // Distributed under the Boost Software License, Version 1.0. (See | |
7 | // accompanying file LICENSE_1_0.txt or copy at | |
8 | // http://www.boost.org/LICENSE_1_0.txt) | |
9 | //======================================================================= | |
10 | // | |
11 | #ifndef MINIMUM_DEGREE_ORDERING_HPP | |
12 | #define MINIMUM_DEGREE_ORDERING_HPP | |
13 | ||
14 | #include <vector> | |
15 | #include <boost/assert.hpp> | |
16 | #include <boost/config.hpp> | |
17 | #include <boost/pending/bucket_sorter.hpp> | |
18 | #include <boost/detail/numeric_traits.hpp> // for integer_traits | |
19 | #include <boost/graph/graph_traits.hpp> | |
20 | #include <boost/property_map/property_map.hpp> | |
21 | ||
22 | namespace boost { | |
23 | ||
24 | namespace detail { | |
25 | ||
26 | // | |
27 | // Given a set of n integers (where the integer values range from | |
28 | // zero to n-1), we want to keep track of a collection of stacks | |
29 | // of integers. It so happens that an integer will appear in at | |
30 | // most one stack at a time, so the stacks form disjoint sets. | |
31 | // Because of these restrictions, we can use one big array to | |
32 | // store all the stacks, intertwined with one another. | |
33 | // No allocation/deallocation happens in the push()/pop() methods | |
34 | // so this is faster than using std::stack's. | |
35 | // | |
36 | template <class SignedInteger> | |
37 | class Stacks { | |
38 | typedef SignedInteger value_type; | |
39 | typedef typename std::vector<value_type>::size_type size_type; | |
40 | public: | |
41 | Stacks(size_type n) : data(n) {} | |
42 | ||
43 | //: stack | |
44 | class stack { | |
45 | typedef typename std::vector<value_type>::iterator Iterator; | |
46 | public: | |
47 | stack(Iterator _data, const value_type& head) | |
48 | : data(_data), current(head) {} | |
49 | ||
50 | // did not use default argument here to avoid internal compiler error | |
51 | // in g++. | |
52 | stack(Iterator _data) | |
53 | : data(_data), current(-(std::numeric_limits<value_type>::max)()) {} | |
54 | ||
55 | void pop() { | |
56 | BOOST_ASSERT(! empty()); | |
57 | current = data[current]; | |
58 | } | |
59 | void push(value_type v) { | |
60 | data[v] = current; | |
61 | current = v; | |
62 | } | |
63 | bool empty() { | |
64 | return current == -(std::numeric_limits<value_type>::max)(); | |
65 | } | |
66 | value_type& top() { return current; } | |
67 | private: | |
68 | Iterator data; | |
69 | value_type current; | |
70 | }; | |
71 | ||
72 | // To return a stack object | |
73 | stack make_stack() | |
74 | { return stack(data.begin()); } | |
75 | protected: | |
76 | std::vector<value_type> data; | |
77 | }; | |
78 | ||
79 | ||
80 | // marker class, a generalization of coloring. | |
81 | // | |
82 | // This class is to provide a generalization of coloring which has | |
83 | // complexity of amortized constant time to set all vertices' color | |
84 | // back to be untagged. It implemented by increasing a tag. | |
85 | // | |
86 | // The colors are: | |
87 | // not tagged | |
88 | // tagged | |
89 | // multiple_tagged | |
90 | // done | |
91 | // | |
92 | template <class SignedInteger, class Vertex, class VertexIndexMap> | |
93 | class Marker { | |
94 | typedef SignedInteger value_type; | |
95 | typedef typename std::vector<value_type>::size_type size_type; | |
96 | ||
97 | static value_type done() | |
98 | { return (std::numeric_limits<value_type>::max)()/2; } | |
99 | public: | |
100 | Marker(size_type _num, VertexIndexMap index_map) | |
101 | : tag(1 - (std::numeric_limits<value_type>::max)()), | |
102 | data(_num, - (std::numeric_limits<value_type>::max)()), | |
103 | id(index_map) {} | |
104 | ||
105 | void mark_done(Vertex node) { data[get(id, node)] = done(); } | |
106 | ||
107 | bool is_done(Vertex node) { return data[get(id, node)] == done(); } | |
108 | ||
109 | void mark_tagged(Vertex node) { data[get(id, node)] = tag; } | |
110 | ||
111 | void mark_multiple_tagged(Vertex node) { data[get(id, node)] = multiple_tag; } | |
112 | ||
113 | bool is_tagged(Vertex node) const { return data[get(id, node)] >= tag; } | |
114 | ||
115 | bool is_not_tagged(Vertex node) const { return data[get(id, node)] < tag; } | |
116 | ||
117 | bool is_multiple_tagged(Vertex node) const | |
118 | { return data[get(id, node)] >= multiple_tag; } | |
119 | ||
120 | void increment_tag() { | |
121 | const size_type num = data.size(); | |
122 | ++tag; | |
123 | if ( tag >= done() ) { | |
124 | tag = 1 - (std::numeric_limits<value_type>::max)(); | |
125 | for (size_type i = 0; i < num; ++i) | |
126 | if ( data[i] < done() ) | |
127 | data[i] = - (std::numeric_limits<value_type>::max)(); | |
128 | } | |
129 | } | |
130 | ||
131 | void set_multiple_tag(value_type mdeg0) | |
132 | { | |
133 | const size_type num = data.size(); | |
134 | multiple_tag = tag + mdeg0; | |
135 | ||
136 | if ( multiple_tag >= done() ) { | |
137 | tag = 1-(std::numeric_limits<value_type>::max)(); | |
138 | ||
139 | for (size_type i=0; i<num; i++) | |
140 | if ( data[i] < done() ) | |
141 | data[i] = -(std::numeric_limits<value_type>::max)(); | |
142 | ||
143 | multiple_tag = tag + mdeg0; | |
144 | } | |
145 | } | |
146 | ||
147 | void set_tag_as_multiple_tag() { tag = multiple_tag; } | |
148 | ||
149 | protected: | |
150 | value_type tag; | |
151 | value_type multiple_tag; | |
152 | std::vector<value_type> data; | |
153 | VertexIndexMap id; | |
154 | }; | |
155 | ||
156 | template< class Iterator, class SignedInteger, | |
157 | class Vertex, class VertexIndexMap, int offset = 1 > | |
158 | class Numbering { | |
159 | typedef SignedInteger number_type; | |
160 | number_type num; //start from 1 instead of zero | |
161 | Iterator data; | |
162 | number_type max_num; | |
163 | VertexIndexMap id; | |
164 | public: | |
165 | Numbering(Iterator _data, number_type _max_num, VertexIndexMap id) | |
166 | : num(1), data(_data), max_num(_max_num), id(id) {} | |
167 | void operator()(Vertex node) { data[get(id, node)] = -num; } | |
168 | bool all_done(number_type i = 0) const { return num + i > max_num; } | |
169 | void increment(number_type i = 1) { num += i; } | |
170 | bool is_numbered(Vertex node) const { | |
171 | return data[get(id, node)] < 0; | |
172 | } | |
173 | void indistinguishable(Vertex i, Vertex j) { | |
174 | data[get(id, i)] = - (get(id, j) + offset); | |
175 | } | |
176 | }; | |
177 | ||
178 | template <class SignedInteger, class Vertex, class VertexIndexMap> | |
179 | class degreelists_marker { | |
180 | public: | |
181 | typedef SignedInteger value_type; | |
182 | typedef typename std::vector<value_type>::size_type size_type; | |
183 | degreelists_marker(size_type n, VertexIndexMap id) | |
184 | : marks(n, 0), id(id) {} | |
185 | void mark_need_update(Vertex i) { marks[get(id, i)] = 1; } | |
186 | bool need_update(Vertex i) { return marks[get(id, i)] == 1; } | |
187 | bool outmatched_or_done (Vertex i) { return marks[get(id, i)] == -1; } | |
188 | void mark(Vertex i) { marks[get(id, i)] = -1; } | |
189 | void unmark(Vertex i) { marks[get(id, i)] = 0; } | |
190 | private: | |
191 | std::vector<value_type> marks; | |
192 | VertexIndexMap id; | |
193 | }; | |
194 | ||
195 | // Helper function object for edge removal | |
196 | template <class Graph, class MarkerP, class NumberD, class Stack, | |
197 | class VertexIndexMap> | |
198 | class predicateRemoveEdge1 { | |
199 | typedef typename graph_traits<Graph>::vertex_descriptor vertex_t; | |
200 | typedef typename graph_traits<Graph>::edge_descriptor edge_t; | |
201 | public: | |
202 | predicateRemoveEdge1(Graph& _g, MarkerP& _marker, | |
203 | NumberD _numbering, Stack& n_e, VertexIndexMap id) | |
204 | : g(&_g), marker(&_marker), numbering(_numbering), | |
205 | neighbor_elements(&n_e), id(id) {} | |
206 | ||
207 | bool operator()(edge_t e) { | |
208 | vertex_t dist = target(e, *g); | |
209 | if ( marker->is_tagged(dist) ) | |
210 | return true; | |
211 | marker->mark_tagged(dist); | |
212 | if (numbering.is_numbered(dist)) { | |
213 | neighbor_elements->push(get(id, dist)); | |
214 | return true; | |
215 | } | |
216 | return false; | |
217 | } | |
218 | private: | |
219 | Graph* g; | |
220 | MarkerP* marker; | |
221 | NumberD numbering; | |
222 | Stack* neighbor_elements; | |
223 | VertexIndexMap id; | |
224 | }; | |
225 | ||
226 | // Helper function object for edge removal | |
227 | template <class Graph, class MarkerP> | |
228 | class predicate_remove_tagged_edges | |
229 | { | |
230 | typedef typename graph_traits<Graph>::vertex_descriptor vertex_t; | |
231 | typedef typename graph_traits<Graph>::edge_descriptor edge_t; | |
232 | public: | |
233 | predicate_remove_tagged_edges(Graph& _g, MarkerP& _marker) | |
234 | : g(&_g), marker(&_marker) {} | |
235 | ||
236 | bool operator()(edge_t e) { | |
237 | vertex_t dist = target(e, *g); | |
238 | if ( marker->is_tagged(dist) ) | |
239 | return true; | |
240 | return false; | |
241 | } | |
242 | private: | |
243 | Graph* g; | |
244 | MarkerP* marker; | |
245 | }; | |
246 | ||
247 | template<class Graph, class DegreeMap, | |
248 | class InversePermutationMap, | |
249 | class PermutationMap, | |
250 | class SuperNodeMap, | |
251 | class VertexIndexMap> | |
252 | class mmd_impl | |
253 | { | |
254 | // Typedefs | |
255 | typedef graph_traits<Graph> Traits; | |
256 | typedef typename Traits::vertices_size_type size_type; | |
257 | typedef typename detail::integer_traits<size_type>::difference_type | |
258 | diff_t; | |
259 | typedef typename Traits::vertex_descriptor vertex_t; | |
260 | typedef typename Traits::adjacency_iterator adj_iter; | |
261 | typedef iterator_property_map<vertex_t*, | |
262 | identity_property_map, vertex_t, vertex_t&> IndexVertexMap; | |
263 | typedef detail::Stacks<diff_t> Workspace; | |
264 | typedef bucket_sorter<size_type, vertex_t, DegreeMap, VertexIndexMap> | |
265 | DegreeLists; | |
266 | typedef Numbering<InversePermutationMap, diff_t, vertex_t,VertexIndexMap> | |
267 | NumberingD; | |
268 | typedef degreelists_marker<diff_t, vertex_t, VertexIndexMap> | |
269 | DegreeListsMarker; | |
270 | typedef Marker<diff_t, vertex_t, VertexIndexMap> MarkerP; | |
271 | ||
272 | // Data Members | |
92f5a8d4 | 273 | bool has_no_edges; |
7c673cae FG |
274 | |
275 | // input parameters | |
276 | Graph& G; | |
277 | int delta; | |
278 | DegreeMap degree; | |
279 | InversePermutationMap inverse_perm; | |
280 | PermutationMap perm; | |
281 | SuperNodeMap supernode_size; | |
282 | VertexIndexMap vertex_index_map; | |
283 | ||
284 | // internal data-structures | |
285 | std::vector<vertex_t> index_vertex_vec; | |
286 | size_type n; | |
287 | IndexVertexMap index_vertex_map; | |
288 | DegreeLists degreelists; | |
289 | NumberingD numbering; | |
290 | DegreeListsMarker degree_lists_marker; | |
291 | MarkerP marker; | |
292 | Workspace work_space; | |
293 | public: | |
294 | mmd_impl(Graph& g, size_type n_, int delta, DegreeMap degree, | |
295 | InversePermutationMap inverse_perm, | |
296 | PermutationMap perm, | |
297 | SuperNodeMap supernode_size, | |
298 | VertexIndexMap id) | |
92f5a8d4 | 299 | : has_no_edges(true), G(g), delta(delta), degree(degree), |
7c673cae FG |
300 | inverse_perm(inverse_perm), |
301 | perm(perm), | |
302 | supernode_size(supernode_size), | |
303 | vertex_index_map(id), | |
304 | index_vertex_vec(n_), | |
305 | n(n_), | |
306 | degreelists(n_ + 1, n_, degree, id), | |
307 | numbering(inverse_perm, n_, vertex_index_map), | |
308 | degree_lists_marker(n_, vertex_index_map), | |
309 | marker(n_, vertex_index_map), | |
310 | work_space(n_) | |
311 | { | |
312 | typename graph_traits<Graph>::vertex_iterator v, vend; | |
313 | size_type vid = 0; | |
314 | for (boost::tie(v, vend) = vertices(G); v != vend; ++v, ++vid) | |
315 | index_vertex_vec[vid] = *v; | |
316 | index_vertex_map = IndexVertexMap(&index_vertex_vec[0]); | |
317 | ||
318 | // Initialize degreelists. Degreelists organizes the nodes | |
319 | // according to their degree. | |
320 | for (boost::tie(v, vend) = vertices(G); v != vend; ++v) { | |
92f5a8d4 TL |
321 | typename Traits::degree_size_type d = out_degree(*v, G); |
322 | put(degree, *v, d); | |
323 | if (0 < d) has_no_edges = false; | |
7c673cae FG |
324 | degreelists.push(*v); |
325 | } | |
326 | } | |
327 | ||
328 | void do_mmd() | |
329 | { | |
330 | // Eliminate the isolated nodes -- these are simply the nodes | |
331 | // with no neighbors, which are accessible as a list (really, a | |
332 | // stack) at location 0. Since these don't affect any other | |
333 | // nodes, we can eliminate them without doing degree updates. | |
334 | typename DegreeLists::stack list_isolated = degreelists[0]; | |
335 | while (!list_isolated.empty()) { | |
336 | vertex_t node = list_isolated.top(); | |
337 | marker.mark_done(node); | |
338 | numbering(node); | |
339 | numbering.increment(); | |
340 | list_isolated.pop(); | |
341 | } | |
92f5a8d4 TL |
342 | |
343 | if (has_no_edges) | |
344 | { | |
345 | return; | |
346 | } | |
347 | ||
7c673cae FG |
348 | size_type min_degree = 1; |
349 | typename DegreeLists::stack list_min_degree = degreelists[min_degree]; | |
350 | ||
351 | while (list_min_degree.empty()) { | |
352 | ++min_degree; | |
353 | list_min_degree = degreelists[min_degree]; | |
354 | } | |
355 | ||
356 | // check if the whole eliminating process is done | |
357 | while (!numbering.all_done()) { | |
358 | ||
359 | size_type min_degree_limit = min_degree + delta; // WARNING | |
360 | typename Workspace::stack llist = work_space.make_stack(); | |
361 | ||
362 | // multiple elimination | |
363 | while (delta >= 0) { | |
364 | ||
365 | // Find the next non-empty degree | |
366 | for (list_min_degree = degreelists[min_degree]; | |
367 | list_min_degree.empty() && min_degree <= min_degree_limit; | |
368 | ++min_degree, list_min_degree = degreelists[min_degree]) | |
369 | ; | |
370 | if (min_degree > min_degree_limit) | |
371 | break; | |
372 | ||
373 | const vertex_t node = list_min_degree.top(); | |
374 | const size_type node_id = get(vertex_index_map, node); | |
375 | list_min_degree.pop(); | |
376 | numbering(node); | |
377 | ||
378 | // check if node is the last one | |
379 | if (numbering.all_done(supernode_size[node])) { | |
380 | numbering.increment(supernode_size[node]); | |
381 | break; | |
382 | } | |
383 | marker.increment_tag(); | |
384 | marker.mark_tagged(node); | |
385 | ||
386 | this->eliminate(node); | |
387 | ||
388 | numbering.increment(supernode_size[node]); | |
389 | llist.push(node_id); | |
390 | } // multiple elimination | |
391 | ||
392 | if (numbering.all_done()) | |
393 | break; | |
394 | ||
395 | this->update( llist, min_degree); | |
396 | } | |
397 | ||
398 | } // do_mmd() | |
399 | ||
400 | void eliminate(vertex_t node) | |
401 | { | |
402 | typename Workspace::stack element_neighbor = work_space.make_stack(); | |
403 | ||
404 | // Create two function objects for edge removal | |
405 | typedef typename Workspace::stack WorkStack; | |
406 | predicateRemoveEdge1<Graph, MarkerP, NumberingD, | |
407 | WorkStack, VertexIndexMap> | |
408 | p(G, marker, numbering, element_neighbor, vertex_index_map); | |
409 | ||
410 | predicate_remove_tagged_edges<Graph, MarkerP> p2(G, marker); | |
411 | ||
412 | // Reconstruct the adjacent node list, push element neighbor in a List. | |
413 | remove_out_edge_if(node, p, G); | |
414 | //during removal element neighbors are collected. | |
415 | ||
416 | while (!element_neighbor.empty()) { | |
417 | // element absorb | |
418 | size_type e_id = element_neighbor.top(); | |
419 | vertex_t element = get(index_vertex_map, e_id); | |
420 | adj_iter i, i_end; | |
421 | for (boost::tie(i, i_end) = adjacent_vertices(element, G); i != i_end; ++i){ | |
422 | vertex_t i_node = *i; | |
423 | if (!marker.is_tagged(i_node) && !numbering.is_numbered(i_node)) { | |
424 | marker.mark_tagged(i_node); | |
425 | add_edge(node, i_node, G); | |
426 | } | |
427 | } | |
428 | element_neighbor.pop(); | |
429 | } | |
430 | adj_iter v, ve; | |
431 | for (boost::tie(v, ve) = adjacent_vertices(node, G); v != ve; ++v) { | |
432 | vertex_t v_node = *v; | |
433 | if (!degree_lists_marker.need_update(v_node) | |
434 | && !degree_lists_marker.outmatched_or_done(v_node)) { | |
435 | degreelists.remove(v_node); | |
436 | } | |
437 | //update out edges of v_node | |
438 | remove_out_edge_if(v_node, p2, G); | |
439 | ||
440 | if ( out_degree(v_node, G) == 0 ) { // indistinguishable nodes | |
441 | supernode_size[node] += supernode_size[v_node]; | |
442 | supernode_size[v_node] = 0; | |
443 | numbering.indistinguishable(v_node, node); | |
444 | marker.mark_done(v_node); | |
445 | degree_lists_marker.mark(v_node); | |
446 | } else { // not indistinguishable nodes | |
447 | add_edge(v_node, node, G); | |
448 | degree_lists_marker.mark_need_update(v_node); | |
449 | } | |
450 | } | |
451 | } // eliminate() | |
452 | ||
453 | ||
454 | template <class Stack> | |
455 | void update(Stack llist, size_type& min_degree) | |
456 | { | |
457 | size_type min_degree0 = min_degree + delta + 1; | |
458 | ||
459 | while (! llist.empty()) { | |
460 | size_type deg, deg0 = 0; | |
461 | ||
462 | marker.set_multiple_tag(min_degree0); | |
463 | typename Workspace::stack q2list = work_space.make_stack(); | |
464 | typename Workspace::stack qxlist = work_space.make_stack(); | |
465 | ||
466 | vertex_t current = get(index_vertex_map, llist.top()); | |
467 | adj_iter i, ie; | |
468 | for (boost::tie(i,ie) = adjacent_vertices(current, G); i != ie; ++i) { | |
469 | vertex_t i_node = *i; | |
470 | const size_type i_id = get(vertex_index_map, i_node); | |
471 | if (supernode_size[i_node] != 0) { | |
472 | deg0 += supernode_size[i_node]; | |
473 | marker.mark_multiple_tagged(i_node); | |
474 | if (degree_lists_marker.need_update(i_node)) { | |
475 | if (out_degree(i_node, G) == 2) | |
476 | q2list.push(i_id); | |
477 | else | |
478 | qxlist.push(i_id); | |
479 | } | |
480 | } | |
481 | } | |
482 | ||
483 | while (!q2list.empty()) { | |
484 | const size_type u_id = q2list.top(); | |
485 | vertex_t u_node = get(index_vertex_map, u_id); | |
486 | // if u_id is outmatched by others, no need to update degree | |
487 | if (degree_lists_marker.outmatched_or_done(u_node)) { | |
488 | q2list.pop(); | |
489 | continue; | |
490 | } | |
491 | marker.increment_tag(); | |
492 | deg = deg0; | |
493 | ||
494 | adj_iter nu = adjacent_vertices(u_node, G).first; | |
495 | vertex_t neighbor = *nu; | |
496 | if (neighbor == u_node) { | |
497 | ++nu; | |
498 | neighbor = *nu; | |
499 | } | |
500 | if (numbering.is_numbered(neighbor)) { | |
501 | adj_iter i, ie; | |
502 | for (boost::tie(i,ie) = adjacent_vertices(neighbor, G); | |
503 | i != ie; ++i) { | |
504 | const vertex_t i_node = *i; | |
505 | if (i_node == u_node || supernode_size[i_node] == 0) | |
506 | continue; | |
507 | if (marker.is_tagged(i_node)) { | |
508 | if (degree_lists_marker.need_update(i_node)) { | |
509 | if ( out_degree(i_node, G) == 2 ) { // is indistinguishable | |
510 | supernode_size[u_node] += supernode_size[i_node]; | |
511 | supernode_size[i_node] = 0; | |
512 | numbering.indistinguishable(i_node, u_node); | |
513 | marker.mark_done(i_node); | |
514 | degree_lists_marker.mark(i_node); | |
515 | } else // is outmatched | |
516 | degree_lists_marker.mark(i_node); | |
517 | } | |
518 | } else { | |
519 | marker.mark_tagged(i_node); | |
520 | deg += supernode_size[i_node]; | |
521 | } | |
522 | } | |
523 | } else | |
524 | deg += supernode_size[neighbor]; | |
525 | ||
526 | deg -= supernode_size[u_node]; | |
527 | degree[u_node] = deg; //update degree | |
528 | degreelists[deg].push(u_node); | |
529 | //u_id has been pushed back into degreelists | |
530 | degree_lists_marker.unmark(u_node); | |
531 | if (min_degree > deg) | |
532 | min_degree = deg; | |
533 | q2list.pop(); | |
534 | } // while (!q2list.empty()) | |
535 | ||
536 | while (!qxlist.empty()) { | |
537 | const size_type u_id = qxlist.top(); | |
538 | const vertex_t u_node = get(index_vertex_map, u_id); | |
539 | ||
540 | // if u_id is outmatched by others, no need to update degree | |
541 | if (degree_lists_marker.outmatched_or_done(u_node)) { | |
542 | qxlist.pop(); | |
543 | continue; | |
544 | } | |
545 | marker.increment_tag(); | |
546 | deg = deg0; | |
547 | adj_iter i, ie; | |
548 | for (boost::tie(i, ie) = adjacent_vertices(u_node, G); i != ie; ++i) { | |
549 | vertex_t i_node = *i; | |
550 | if (marker.is_tagged(i_node)) | |
551 | continue; | |
552 | marker.mark_tagged(i_node); | |
553 | ||
554 | if (numbering.is_numbered(i_node)) { | |
555 | adj_iter j, je; | |
556 | for (boost::tie(j, je) = adjacent_vertices(i_node, G); j != je; ++j) { | |
557 | const vertex_t j_node = *j; | |
558 | if (marker.is_not_tagged(j_node)) { | |
559 | marker.mark_tagged(j_node); | |
560 | deg += supernode_size[j_node]; | |
561 | } | |
562 | } | |
563 | } else | |
564 | deg += supernode_size[i_node]; | |
565 | } // for adjacent vertices of u_node | |
566 | deg -= supernode_size[u_node]; | |
567 | degree[u_node] = deg; | |
568 | degreelists[deg].push(u_node); | |
569 | // u_id has been pushed back into degreelists | |
570 | degree_lists_marker.unmark(u_node); | |
571 | if (min_degree > deg) | |
572 | min_degree = deg; | |
573 | qxlist.pop(); | |
574 | } // while (!qxlist.empty()) { | |
575 | ||
576 | marker.set_tag_as_multiple_tag(); | |
577 | llist.pop(); | |
578 | } // while (! llist.empty()) | |
579 | ||
580 | } // update() | |
581 | ||
582 | ||
583 | void build_permutation(InversePermutationMap next, | |
584 | PermutationMap prev) | |
585 | { | |
586 | // collect the permutation info | |
587 | size_type i; | |
588 | for (i = 0; i < n; ++i) { | |
589 | diff_t size = supernode_size[get(index_vertex_map, i)]; | |
590 | if ( size <= 0 ) { | |
591 | prev[i] = next[i]; | |
592 | supernode_size[get(index_vertex_map, i)] | |
593 | = next[i] + 1; // record the supernode info | |
594 | } else | |
595 | prev[i] = - next[i]; | |
596 | } | |
597 | for (i = 1; i < n + 1; ++i) { | |
598 | if ( prev[i-1] > 0 ) | |
599 | continue; | |
600 | diff_t parent = i; | |
601 | while ( prev[parent - 1] < 0 ) { | |
602 | parent = - prev[parent - 1]; | |
603 | } | |
604 | ||
605 | diff_t root = parent; | |
606 | diff_t num = prev[root - 1] + 1; | |
607 | next[i-1] = - num; | |
608 | prev[root-1] = num; | |
609 | ||
610 | parent = i; | |
611 | diff_t next_node = - prev[parent - 1]; | |
612 | while (next_node > 0) { | |
613 | prev[parent-1] = - root; | |
614 | parent = next_node; | |
615 | next_node = - prev[parent - 1]; | |
616 | } | |
617 | } | |
618 | for (i = 0; i < n; i++) { | |
619 | diff_t num = - next[i] - 1; | |
620 | next[i] = num; | |
621 | prev[num] = i; | |
622 | } | |
623 | } // build_permutation() | |
624 | }; | |
625 | ||
626 | } //namespace detail | |
627 | ||
628 | ||
629 | // MMD algorithm | |
630 | // | |
631 | //The implementation presently includes the enhancements for mass | |
632 | //elimination, incomplete degree update, multiple elimination, and | |
633 | //external degree. | |
634 | // | |
635 | //Important Note: This implementation requires the BGL graph to be | |
636 | //directed. Therefore, nonzero entry (i, j) in a symmetrical matrix | |
637 | //A coresponds to two directed edges (i->j and j->i). | |
638 | // | |
639 | //see Alan George and Joseph W. H. Liu, The Evolution of the Minimum | |
640 | //Degree Ordering Algorithm, SIAM Review, 31, 1989, Page 1-19 | |
641 | template<class Graph, class DegreeMap, | |
642 | class InversePermutationMap, | |
643 | class PermutationMap, | |
644 | class SuperNodeMap, class VertexIndexMap> | |
645 | void minimum_degree_ordering | |
646 | (Graph& G, | |
647 | DegreeMap degree, | |
648 | InversePermutationMap inverse_perm, | |
649 | PermutationMap perm, | |
650 | SuperNodeMap supernode_size, | |
651 | int delta, | |
652 | VertexIndexMap vertex_index_map) | |
653 | { | |
654 | detail::mmd_impl<Graph,DegreeMap,InversePermutationMap, | |
655 | PermutationMap, SuperNodeMap, VertexIndexMap> | |
656 | impl(G, num_vertices(G), delta, degree, inverse_perm, | |
657 | perm, supernode_size, vertex_index_map); | |
658 | impl.do_mmd(); | |
659 | impl.build_permutation(inverse_perm, perm); | |
660 | } | |
661 | ||
662 | } // namespace boost | |
663 | ||
664 | #endif // MINIMUM_DEGREE_ORDERING_HPP |