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: Stacks(size_type n)41 Stacks(size_type n) : data(n) {} 42 43 //: stack 44 class stack { 45 typedef typename std::vector<value_type>::iterator Iterator; 46 public: stack(Iterator _data,const value_type & head)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++. stack(Iterator _data)52 stack(Iterator _data) 53 : data(_data), current(-(std::numeric_limits<value_type>::max)()) {} 54 pop()55 void pop() { 56 BOOST_ASSERT(! empty()); 57 current = data[current]; 58 } push(value_type v)59 void push(value_type v) { 60 data[v] = current; 61 current = v; 62 } empty()63 bool empty() { 64 return current == -(std::numeric_limits<value_type>::max)(); 65 } top()66 value_type& top() { return current; } 67 private: 68 Iterator data; 69 value_type current; 70 }; 71 72 // To return a stack object make_stack()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 done()97 static value_type done() 98 { return (std::numeric_limits<value_type>::max)()/2; } 99 public: Marker(size_type _num,VertexIndexMap index_map)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 mark_done(Vertex node)105 void mark_done(Vertex node) { data[get(id, node)] = done(); } 106 is_done(Vertex node)107 bool is_done(Vertex node) { return data[get(id, node)] == done(); } 108 mark_tagged(Vertex node)109 void mark_tagged(Vertex node) { data[get(id, node)] = tag; } 110 mark_multiple_tagged(Vertex node)111 void mark_multiple_tagged(Vertex node) { data[get(id, node)] = multiple_tag; } 112 is_tagged(Vertex node) const113 bool is_tagged(Vertex node) const { return data[get(id, node)] >= tag; } 114 is_not_tagged(Vertex node) const115 bool is_not_tagged(Vertex node) const { return data[get(id, node)] < tag; } 116 is_multiple_tagged(Vertex node) const117 bool is_multiple_tagged(Vertex node) const 118 { return data[get(id, node)] >= multiple_tag; } 119 increment_tag()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 set_multiple_tag(value_type mdeg0)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 set_tag_as_multiple_tag()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: Numbering(Iterator _data,number_type _max_num,VertexIndexMap id)165 Numbering(Iterator _data, number_type _max_num, VertexIndexMap id) 166 : num(1), data(_data), max_num(_max_num), id(id) {} operator ()(Vertex node)167 void operator()(Vertex node) { data[get(id, node)] = -num; } all_done(number_type i=0) const168 bool all_done(number_type i = 0) const { return num + i > max_num; } increment(number_type i=1)169 void increment(number_type i = 1) { num += i; } is_numbered(Vertex node) const170 bool is_numbered(Vertex node) const { 171 return data[get(id, node)] < 0; 172 } indistinguishable(Vertex i,Vertex j)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; degreelists_marker(size_type n,VertexIndexMap id)183 degreelists_marker(size_type n, VertexIndexMap id) 184 : marks(n, 0), id(id) {} mark_need_update(Vertex i)185 void mark_need_update(Vertex i) { marks[get(id, i)] = 1; } need_update(Vertex i)186 bool need_update(Vertex i) { return marks[get(id, i)] == 1; } outmatched_or_done(Vertex i)187 bool outmatched_or_done (Vertex i) { return marks[get(id, i)] == -1; } mark(Vertex i)188 void mark(Vertex i) { marks[get(id, i)] = -1; } unmark(Vertex i)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: predicateRemoveEdge1(Graph & _g,MarkerP & _marker,NumberD _numbering,Stack & n_e,VertexIndexMap id)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 operator ()(edge_t e)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: predicate_remove_tagged_edges(Graph & _g,MarkerP & _marker)233 predicate_remove_tagged_edges(Graph& _g, MarkerP& _marker) 234 : g(&_g), marker(&_marker) {} 235 operator ()(edge_t e)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 273 274 // input parameters 275 Graph& G; 276 int delta; 277 DegreeMap degree; 278 InversePermutationMap inverse_perm; 279 PermutationMap perm; 280 SuperNodeMap supernode_size; 281 VertexIndexMap vertex_index_map; 282 283 // internal data-structures 284 std::vector<vertex_t> index_vertex_vec; 285 size_type n; 286 IndexVertexMap index_vertex_map; 287 DegreeLists degreelists; 288 NumberingD numbering; 289 DegreeListsMarker degree_lists_marker; 290 MarkerP marker; 291 Workspace work_space; 292 public: mmd_impl(Graph & g,size_type n_,int delta,DegreeMap degree,InversePermutationMap inverse_perm,PermutationMap perm,SuperNodeMap supernode_size,VertexIndexMap id)293 mmd_impl(Graph& g, size_type n_, int delta, DegreeMap degree, 294 InversePermutationMap inverse_perm, 295 PermutationMap perm, 296 SuperNodeMap supernode_size, 297 VertexIndexMap id) 298 : G(g), delta(delta), degree(degree), 299 inverse_perm(inverse_perm), 300 perm(perm), 301 supernode_size(supernode_size), 302 vertex_index_map(id), 303 index_vertex_vec(n_), 304 n(n_), 305 degreelists(n_ + 1, n_, degree, id), 306 numbering(inverse_perm, n_, vertex_index_map), 307 degree_lists_marker(n_, vertex_index_map), 308 marker(n_, vertex_index_map), 309 work_space(n_) 310 { 311 typename graph_traits<Graph>::vertex_iterator v, vend; 312 size_type vid = 0; 313 for (boost::tie(v, vend) = vertices(G); v != vend; ++v, ++vid) 314 index_vertex_vec[vid] = *v; 315 index_vertex_map = IndexVertexMap(&index_vertex_vec[0]); 316 317 // Initialize degreelists. Degreelists organizes the nodes 318 // according to their degree. 319 for (boost::tie(v, vend) = vertices(G); v != vend; ++v) { 320 put(degree, *v, out_degree(*v, G)); 321 degreelists.push(*v); 322 } 323 } 324 do_mmd()325 void do_mmd() 326 { 327 // Eliminate the isolated nodes -- these are simply the nodes 328 // with no neighbors, which are accessible as a list (really, a 329 // stack) at location 0. Since these don't affect any other 330 // nodes, we can eliminate them without doing degree updates. 331 typename DegreeLists::stack list_isolated = degreelists[0]; 332 while (!list_isolated.empty()) { 333 vertex_t node = list_isolated.top(); 334 marker.mark_done(node); 335 numbering(node); 336 numbering.increment(); 337 list_isolated.pop(); 338 } 339 size_type min_degree = 1; 340 typename DegreeLists::stack list_min_degree = degreelists[min_degree]; 341 342 while (list_min_degree.empty()) { 343 ++min_degree; 344 list_min_degree = degreelists[min_degree]; 345 } 346 347 // check if the whole eliminating process is done 348 while (!numbering.all_done()) { 349 350 size_type min_degree_limit = min_degree + delta; // WARNING 351 typename Workspace::stack llist = work_space.make_stack(); 352 353 // multiple elimination 354 while (delta >= 0) { 355 356 // Find the next non-empty degree 357 for (list_min_degree = degreelists[min_degree]; 358 list_min_degree.empty() && min_degree <= min_degree_limit; 359 ++min_degree, list_min_degree = degreelists[min_degree]) 360 ; 361 if (min_degree > min_degree_limit) 362 break; 363 364 const vertex_t node = list_min_degree.top(); 365 const size_type node_id = get(vertex_index_map, node); 366 list_min_degree.pop(); 367 numbering(node); 368 369 // check if node is the last one 370 if (numbering.all_done(supernode_size[node])) { 371 numbering.increment(supernode_size[node]); 372 break; 373 } 374 marker.increment_tag(); 375 marker.mark_tagged(node); 376 377 this->eliminate(node); 378 379 numbering.increment(supernode_size[node]); 380 llist.push(node_id); 381 } // multiple elimination 382 383 if (numbering.all_done()) 384 break; 385 386 this->update( llist, min_degree); 387 } 388 389 } // do_mmd() 390 eliminate(vertex_t node)391 void eliminate(vertex_t node) 392 { 393 typename Workspace::stack element_neighbor = work_space.make_stack(); 394 395 // Create two function objects for edge removal 396 typedef typename Workspace::stack WorkStack; 397 predicateRemoveEdge1<Graph, MarkerP, NumberingD, 398 WorkStack, VertexIndexMap> 399 p(G, marker, numbering, element_neighbor, vertex_index_map); 400 401 predicate_remove_tagged_edges<Graph, MarkerP> p2(G, marker); 402 403 // Reconstruct the adjacent node list, push element neighbor in a List. 404 remove_out_edge_if(node, p, G); 405 //during removal element neighbors are collected. 406 407 while (!element_neighbor.empty()) { 408 // element absorb 409 size_type e_id = element_neighbor.top(); 410 vertex_t element = get(index_vertex_map, e_id); 411 adj_iter i, i_end; 412 for (boost::tie(i, i_end) = adjacent_vertices(element, G); i != i_end; ++i){ 413 vertex_t i_node = *i; 414 if (!marker.is_tagged(i_node) && !numbering.is_numbered(i_node)) { 415 marker.mark_tagged(i_node); 416 add_edge(node, i_node, G); 417 } 418 } 419 element_neighbor.pop(); 420 } 421 adj_iter v, ve; 422 for (boost::tie(v, ve) = adjacent_vertices(node, G); v != ve; ++v) { 423 vertex_t v_node = *v; 424 if (!degree_lists_marker.need_update(v_node) 425 && !degree_lists_marker.outmatched_or_done(v_node)) { 426 degreelists.remove(v_node); 427 } 428 //update out edges of v_node 429 remove_out_edge_if(v_node, p2, G); 430 431 if ( out_degree(v_node, G) == 0 ) { // indistinguishable nodes 432 supernode_size[node] += supernode_size[v_node]; 433 supernode_size[v_node] = 0; 434 numbering.indistinguishable(v_node, node); 435 marker.mark_done(v_node); 436 degree_lists_marker.mark(v_node); 437 } else { // not indistinguishable nodes 438 add_edge(v_node, node, G); 439 degree_lists_marker.mark_need_update(v_node); 440 } 441 } 442 } // eliminate() 443 444 445 template <class Stack> update(Stack llist,size_type & min_degree)446 void update(Stack llist, size_type& min_degree) 447 { 448 size_type min_degree0 = min_degree + delta + 1; 449 450 while (! llist.empty()) { 451 size_type deg, deg0 = 0; 452 453 marker.set_multiple_tag(min_degree0); 454 typename Workspace::stack q2list = work_space.make_stack(); 455 typename Workspace::stack qxlist = work_space.make_stack(); 456 457 vertex_t current = get(index_vertex_map, llist.top()); 458 adj_iter i, ie; 459 for (boost::tie(i,ie) = adjacent_vertices(current, G); i != ie; ++i) { 460 vertex_t i_node = *i; 461 const size_type i_id = get(vertex_index_map, i_node); 462 if (supernode_size[i_node] != 0) { 463 deg0 += supernode_size[i_node]; 464 marker.mark_multiple_tagged(i_node); 465 if (degree_lists_marker.need_update(i_node)) { 466 if (out_degree(i_node, G) == 2) 467 q2list.push(i_id); 468 else 469 qxlist.push(i_id); 470 } 471 } 472 } 473 474 while (!q2list.empty()) { 475 const size_type u_id = q2list.top(); 476 vertex_t u_node = get(index_vertex_map, u_id); 477 // if u_id is outmatched by others, no need to update degree 478 if (degree_lists_marker.outmatched_or_done(u_node)) { 479 q2list.pop(); 480 continue; 481 } 482 marker.increment_tag(); 483 deg = deg0; 484 485 adj_iter nu = adjacent_vertices(u_node, G).first; 486 vertex_t neighbor = *nu; 487 if (neighbor == u_node) { 488 ++nu; 489 neighbor = *nu; 490 } 491 if (numbering.is_numbered(neighbor)) { 492 adj_iter i, ie; 493 for (boost::tie(i,ie) = adjacent_vertices(neighbor, G); 494 i != ie; ++i) { 495 const vertex_t i_node = *i; 496 if (i_node == u_node || supernode_size[i_node] == 0) 497 continue; 498 if (marker.is_tagged(i_node)) { 499 if (degree_lists_marker.need_update(i_node)) { 500 if ( out_degree(i_node, G) == 2 ) { // is indistinguishable 501 supernode_size[u_node] += supernode_size[i_node]; 502 supernode_size[i_node] = 0; 503 numbering.indistinguishable(i_node, u_node); 504 marker.mark_done(i_node); 505 degree_lists_marker.mark(i_node); 506 } else // is outmatched 507 degree_lists_marker.mark(i_node); 508 } 509 } else { 510 marker.mark_tagged(i_node); 511 deg += supernode_size[i_node]; 512 } 513 } 514 } else 515 deg += supernode_size[neighbor]; 516 517 deg -= supernode_size[u_node]; 518 degree[u_node] = deg; //update degree 519 degreelists[deg].push(u_node); 520 //u_id has been pushed back into degreelists 521 degree_lists_marker.unmark(u_node); 522 if (min_degree > deg) 523 min_degree = deg; 524 q2list.pop(); 525 } // while (!q2list.empty()) 526 527 while (!qxlist.empty()) { 528 const size_type u_id = qxlist.top(); 529 const vertex_t u_node = get(index_vertex_map, u_id); 530 531 // if u_id is outmatched by others, no need to update degree 532 if (degree_lists_marker.outmatched_or_done(u_node)) { 533 qxlist.pop(); 534 continue; 535 } 536 marker.increment_tag(); 537 deg = deg0; 538 adj_iter i, ie; 539 for (boost::tie(i, ie) = adjacent_vertices(u_node, G); i != ie; ++i) { 540 vertex_t i_node = *i; 541 if (marker.is_tagged(i_node)) 542 continue; 543 marker.mark_tagged(i_node); 544 545 if (numbering.is_numbered(i_node)) { 546 adj_iter j, je; 547 for (boost::tie(j, je) = adjacent_vertices(i_node, G); j != je; ++j) { 548 const vertex_t j_node = *j; 549 if (marker.is_not_tagged(j_node)) { 550 marker.mark_tagged(j_node); 551 deg += supernode_size[j_node]; 552 } 553 } 554 } else 555 deg += supernode_size[i_node]; 556 } // for adjacent vertices of u_node 557 deg -= supernode_size[u_node]; 558 degree[u_node] = deg; 559 degreelists[deg].push(u_node); 560 // u_id has been pushed back into degreelists 561 degree_lists_marker.unmark(u_node); 562 if (min_degree > deg) 563 min_degree = deg; 564 qxlist.pop(); 565 } // while (!qxlist.empty()) { 566 567 marker.set_tag_as_multiple_tag(); 568 llist.pop(); 569 } // while (! llist.empty()) 570 571 } // update() 572 573 build_permutation(InversePermutationMap next,PermutationMap prev)574 void build_permutation(InversePermutationMap next, 575 PermutationMap prev) 576 { 577 // collect the permutation info 578 size_type i; 579 for (i = 0; i < n; ++i) { 580 diff_t size = supernode_size[get(index_vertex_map, i)]; 581 if ( size <= 0 ) { 582 prev[i] = next[i]; 583 supernode_size[get(index_vertex_map, i)] 584 = next[i] + 1; // record the supernode info 585 } else 586 prev[i] = - next[i]; 587 } 588 for (i = 1; i < n + 1; ++i) { 589 if ( prev[i-1] > 0 ) 590 continue; 591 diff_t parent = i; 592 while ( prev[parent - 1] < 0 ) { 593 parent = - prev[parent - 1]; 594 } 595 596 diff_t root = parent; 597 diff_t num = prev[root - 1] + 1; 598 next[i-1] = - num; 599 prev[root-1] = num; 600 601 parent = i; 602 diff_t next_node = - prev[parent - 1]; 603 while (next_node > 0) { 604 prev[parent-1] = - root; 605 parent = next_node; 606 next_node = - prev[parent - 1]; 607 } 608 } 609 for (i = 0; i < n; i++) { 610 diff_t num = - next[i] - 1; 611 next[i] = num; 612 prev[num] = i; 613 } 614 } // build_permutation() 615 }; 616 617 } //namespace detail 618 619 620 // MMD algorithm 621 // 622 //The implementation presently includes the enhancements for mass 623 //elimination, incomplete degree update, multiple elimination, and 624 //external degree. 625 // 626 //Important Note: This implementation requires the BGL graph to be 627 //directed. Therefore, nonzero entry (i, j) in a symmetrical matrix 628 //A coresponds to two directed edges (i->j and j->i). 629 // 630 //see Alan George and Joseph W. H. Liu, The Evolution of the Minimum 631 //Degree Ordering Algorithm, SIAM Review, 31, 1989, Page 1-19 632 template<class Graph, class DegreeMap, 633 class InversePermutationMap, 634 class PermutationMap, 635 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)636 void minimum_degree_ordering 637 (Graph& G, 638 DegreeMap degree, 639 InversePermutationMap inverse_perm, 640 PermutationMap perm, 641 SuperNodeMap supernode_size, 642 int delta, 643 VertexIndexMap vertex_index_map) 644 { 645 detail::mmd_impl<Graph,DegreeMap,InversePermutationMap, 646 PermutationMap, SuperNodeMap, VertexIndexMap> 647 impl(G, num_vertices(G), delta, degree, inverse_perm, 648 perm, supernode_size, vertex_index_map); 649 impl.do_mmd(); 650 impl.build_permutation(inverse_perm, perm); 651 } 652 653 } // namespace boost 654 655 #endif // MINIMUM_DEGREE_ORDERING_HPP 656