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