N
      ˆÉ�þ\|’¬Ü¤’¸Æ ùÎ„ yßÍÈ¿Ê ?÷     //-*-c++-*-
//=======================================================================
// Copyright 1997-2001 University of Notre Dame.
// Authors: Lie-Quan Lee, Jeremy Siek
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================
//
#ifndef BOOST_GRAPH_MINIMUM_DEGREE_ORDERING_HPP
#define BOOST_GRAPH_MINIMUM_DEGREE_ORDERING_HPP

#include <vector>
#include <boost/assert.hpp>
#include <boost/config.hpp>
#include <boost/pending/bucket_sorter.hpp>
#include <boost/detail/numeric_traits.hpp> // for integer_traits
#include <boost/graph/graph_traits.hpp>
#include <boost/property_map/property_map.hpp>

namespace boost
{

namespace detail
{

    //
    // Given a set of n integers (where the integer values range from
    // zero to n-1), we want to keep track of a collection of stacks
    // of integers. It so happens that an integer will appear in at
    // most one stack at a time, so the stacks form disjoint sets.
    // Because of these restrictions, we can use one big array to
    // store all the stacks, intertwined with one another.
    // No allocation/deallocation happens in the push()/pop() methods
    // so this is faster than using std::stack's.
    //
    template < class SignedInteger > class Stacks
    {
        typedef SignedInteger value_type;
        typedef typename std::vector< value_type >::size_type size_type;

    public:
        Stacks(size_type n) : data(n) {}

        //: stack
        class stack
        {
            typedef typename std::vector< value_type >::iterator Iterator;

        public:
            stack(Iterator _data, const value_type& head)
            : data(_data), current(head)
            {
            }

            // did not use default argument here to avoid internal compiler
            // error in g++.
            stack(Iterator _data)
            : data(_data), current(-(std::numeric_limits< value_type >::max)())
            {
            }

            void pop()
            {
                BOOST_ASSERT(!empty());
                current = data[current];
            }
            void push(value_type v)
            {
                data[v] = current;
                current = v;
            }
            bool empty()
            {
                return current == -(std::numeric_limits< value_type >::max)();
            }
            value_type& top() { return current; }

        private:
            Iterator data;
            value_type current;
        };

        // To return a stack object
        stack make_stack() { return stack(data.begin()); }

    protected:
        std::vector< value_type > data;
    };

    // marker class, a generalization of coloring.
    //
    // This class is to provide a generalization of coloring which has
    // complexity of amortized constant time to set all vertices' color
    // back to be untagged. It implemented by increasing a tag.
    //
    // The colors are:
    //   not tagged
    //   tagged
    //   multiple_tagged
    //   done
    //
    template < class SignedInteger, class Vertex, class VertexIndexMap >
    class Marker
    {
        typedef SignedInteger value_type;
        typedef typename std::vector< value_type >::size_type size_type;

        static value_type done()
        {
            return (std::numeric_limits< value_type >::max)() / 2;
        }

    public:
        Marker(size_type _num, VertexIndexMap index_map)
        : tag(1 - (std::numeric_limits< value_type >::max)())
        , data(_num, -(std::numeric_limits< value_type >::max)())
        , id(index_map)
        {
        }

        void mark_done(Vertex node) { data[get(id, node)] = done(); }

        bool is_done(Vertex node) { return data[get(id, node)] == done(); }

        void mark_tagged(Vertex node) { data[get(id, node)] = tag; }

        void mark_multiple_tagged(Vertex node)
        {
            data[get(id, node)] = mul