ceph/src/boost/boost/graph/minimum_degree_ordering.hpp

   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
 273       bool has_no_edges;
 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)
 299         : has_no_edges(true), G(g), delta(delta), degree(degree),
 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) {
 321           typename Traits::degree_size_type d = out_degree(*v, G);
 322           put(degree, *v, d);
 323           if (0 < d) has_no_edges = false;
 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         }
 342
 343         if (has_no_edges)
 344         {
 345           return;
 346         }
 347
 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