//=======================================================================

// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.

// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. 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_TRAITS_HPP

#define BOOST_GRAPH_TRAITS_HPP

#include <boost/config.hpp>

#include <iterator>

#include <utility> /* Primarily for std::pair */

#include <boost/tuple/tuple.hpp>

#include <boost/mpl/if.hpp>

#include <boost/mpl/eval_if.hpp>

#include <boost/mpl/bool.hpp>

#include <boost/mpl/not.hpp>

#include <boost/mpl/has_xxx.hpp>

#include <boost/mpl/void.hpp>

#include <boost/mpl/identity.hpp>

#include <boost/mpl/and.hpp>

#include <boost/type_traits/is_same.hpp>

#include <boost/iterator/iterator_categories.hpp>

#include <boost/iterator/iterator_adaptor.hpp>

#include <boost/pending/property.hpp>

#include <boost/detail/workaround.hpp>

namespace boost

{

namespace detail

{

#define BOOST_GRAPH_MEMBER_OR_VOID(name)                                                                                            \

    BOOST_MPL_HAS_XXX_TRAIT_DEF(name)                                                                                               \

    template < typename T > struct BOOST_JOIN(get_member_, name)                                                                    \

    {                                                                                                                               \

        typedef typename T::name type;                                                                                              \

    };                                                                                                                              \

    template < typename T >                                                                                                         \

    struct BOOST_JOIN(get_opt_member_, name)                                                                                        \

    : boost::mpl::eval_if_c< BOOST_JOIN(has_, name) < T >::value, BOOST_JOIN(get_member_, name)< T >, boost::mpl::identity< void > >\

    {                                                                                                                               \

    };

    BOOST_GRAPH_MEMBER_OR_VOID(adjacency_iterator)

    BOOST_GRAPH_MEMBER_OR_VOID(out_edge_iterator)

    BOOST_GRAPH_MEMBER_OR_VOID(in_edge_iterator)

    BOOST_GRAPH_MEMBER_OR_VOID(vertex_iterator)

    BOOST_GRAPH_MEMBER_OR_VOID(edge_iterator)

    BOOST_GRAPH_MEMBER_OR_VOID(vertices_size_type)

    BOOST_GRAPH_MEMBER_OR_VOID(edges_size_type)

    BOOST_GRAPH_MEMBER_OR_VOID(degree_size_type)

}

template < typename G > struct graph_traits

{

#define BOOST_GRAPH_PULL_OPT_MEMBER(name) \

    typedef typename detail::BOOST_JOIN(get_opt_member_, name)< G >::type name;

    typedef typename G::vertex_descriptor vertex_descriptor;

    typedef typename G::edge_descriptor edge_descriptor;

    BOOST_GRAPH_PULL_OPT_MEMBER(adjacency_iterator)

    BOOST_GRAPH_PULL_OPT_MEMBER(out_edge_iterator)

    BOOST_GRAPH_PULL_OPT_MEMBER(in_edge_iterator)

    BOOST_GRAPH_PULL_OPT_MEMBER(vertex_iterator)

    BOOST_GRAPH_PULL_OPT_MEMBER(edge_iterator)

    typedef typename G::directed_category directed_category;

    typedef typename G::edge_parallel_category edge_parallel_category;

    typedef typename G::traversal_category traversal_category;

    BOOST_GRAPH_PULL_OPT_MEMBER(vertices_size_type)

    BOOST_GRAPH_PULL_OPT_MEMBER(edges_size_type)

    BOOST_GRAPH_PULL_OPT_MEMBER(degree_size_type)

#undef BOOST_GRAPH_PULL_OPT_MEMBER

    static inline vertex_descriptor null_vertex();

};

template < typename G >

inline typename graph_traits< G >::vertex_descriptor

graph_traits< G >::null_vertex()

{

    return G::null_vertex();

}

// directed_category tags

struct directed_tag

{

};

struct undirected_tag

{

};

struct bidirectional_tag : public directed_tag

{

};

namespace detail

{

    inline bool is_directed(directed_tag) { return true; }

    inline bool is_directed(undirected_tag) { return false; }

}

/** Return true if the given graph is directed. */

template < typename Graph > bool is_directed(const Graph&)

{

    typedef typename graph_traits< Graph >::directed_category Cat;

    return detail::is_directed(Cat());

}

/** Return true if the given graph is undirected. */

template < typename Graph > bool is_undirected(const Graph& g)

{

    return !is_directed(g);

}

/** @name Directed/Undirected Graph Traits */

//@{

namespace graph_detail

{

    template < typename Tag >

    struct is_directed_tag

    : mpl::bool_< is_convertible< Tag, directed_tag >::value >

    {

    };

} // namespace graph_detail

template < typename Graph >

struct is_directed_graph

: graph_detail::is_directed_tag<

      typename graph_traits< Graph >::directed_category >

{

};

template < typename Graph >

struct is_undirected_graph : mpl::not_< is_directed_graph< Graph > >

{

};

//@}

// edge_parallel_category tags

struct allow_parallel_edge_tag

{

};

struct disallow_parallel_edge_tag

{

};

namespace detail

{

    inline bool allows_parallel(allow_parallel_edge_tag) { return true; }

    inline bool allows_parallel(disallow_parallel_edge_tag) { return false; }

}

template < typename Graph > bool allows_parallel_edges(const Graph&)

{

    typedef typename graph_traits< Graph >::edge_parallel_category Cat;

    return detail::allows_parallel(Cat());

}

/** @name Parallel Edges Traits */

//@{

/**

 * The is_multigraph metafunction returns true if the graph allows

 * parallel edges. Technically, a multigraph is a simple graph that

 * allows parallel edges, but since there are no traits for the allowance

 * or disallowance of loops, this is a moot point.

 */

template < typename Graph >

struct is_multigraph

: mpl::bool_< is_same< typename graph_traits< Graph >::edge_parallel_category,

      allow_parallel_edge_tag >::value >

{

};

//@}

// traversal_category tags

struct incidence_graph_tag

{

};

struct adjacency_graph_tag

{

};

struct bidirectional_graph_tag : virtual incidence_graph_tag

{

};

struct vertex_list_graph_tag

{

};

struct edge_list_graph_tag

{

};

struct adjacency_matrix_tag

{

};

// Parallel traversal_category tags

struct distributed_graph_tag

{

};

struct distributed_vertex_list_graph_tag

{

};

struct distributed_edge_list_graph_tag

{

};

#define BOOST_GRAPH_SEQUENTIAL_TRAITS_DEFINES_DISTRIBUTED_TAGS // Disable these

                                                               // from external

                                                               // versions of

                                                               // PBGL

/** @name Traversal Category Traits

 * These traits classify graph types by their supported methods of

 * vertex and edge traversal.

 */

//@{

template < typename Graph >

struct is_incidence_graph

: mpl::bool_<

      is_convertible< typename graph_traits< Graph >::traversal_category,

          incidence_graph_tag >::value >

{

};

template < typename Graph >

struct is_bidirectional_graph

: mpl::bool_<

      is_convertible< typename graph_traits< Graph >::traversal_category,

          bidirectional_graph_tag >::value >

{

};

template < typename Graph >

struct is_vertex_list_graph

: mpl::bool_<

      is_convertible< typename graph_traits< Graph >::traversal_category,

          vertex_list_graph_tag >::value >

{

};

template < typename Graph >

struct is_edge_list_graph

: mpl::bool_<

      is_convertible< typename graph_traits< Graph >::traversal_category,

          edge_list_graph_tag >::value >

{

};

template < typename Graph >

struct is_adjacency_matrix

: mpl::bool_<

      is_convertible< typename graph_traits< Graph >::traversal_category,

          adjacency_matrix_tag >::value >

{

};

//@}

/** @name Directed Graph Traits

 * These metafunctions are used to fully classify directed vs. undirected

 * graphs. Recall that an undirected graph is also bidirectional, but it

 * cannot be both undirected and directed at the same time.

 */

//@{

template < typename Graph >

struct is_directed_unidirectional_graph

: mpl::and_< is_directed_graph< Graph >,

      mpl::not_< is_bidirectional_graph< Graph > > >

{

};

template < typename Graph >

struct is_directed_bidirectional_graph

: mpl::and_< is_directed_graph< Graph >, is_bidirectional_graph< Graph > >

{

};

//@}

//?? not the right place ?? Lee

typedef boost::forward_traversal_tag multi_pass_input_iterator_tag;

namespace detail

{

    BOOST_MPL_HAS_XXX_TRAIT_DEF(graph_property_type)

    BOOST_MPL_HAS_XXX_TRAIT_DEF(edge_property_type)

    BOOST_MPL_HAS_XXX_TRAIT_DEF(vertex_property_type)

    template < typename G > struct get_graph_property_type

    {

        typedef typename G::graph_property_type type;

    };

    template < typename G > struct get_edge_property_type

    {

        typedef typename G::edge_property_type type;

    };

    template < typename G > struct get_vertex_property_type

    {

        typedef typename G::vertex_property_type type;

    };

}

template < typename G >

struct graph_property_type

: boost::mpl::eval_if< detail::has_graph_property_type< G >,

      detail::get_graph_property_type< G >, no_property >

{

};

template < typename G >

struct edge_property_type

: boost::mpl::eval_if< detail::has_edge_property_type< G >,

      detail::get_edge_property_type< G >, no_property >

{

};

template < typename G >

struct vertex_property_type

: boost::mpl::eval_if< detail::has_vertex_property_type< G >,

      detail::get_vertex_property_type< G >, no_property >

{

};

template < typename G > struct graph_bundle_type

{

    typedef typename G::graph_bundled type;

};

template < typename G > struct vertex_bundle_type

{

    typedef typename G::vertex_bundled type;

};

template < typename G > struct edge_bundle_type

{

    typedef typename G::edge_bundled type;

};

namespace graph

{

    namespace detail

    {

        template < typename Graph, typename Descriptor > class bundled_result

        {

            typedef typename graph_traits< Graph >::vertex_descriptor Vertex;

            typedef typename mpl::if_c< (is_same< Descriptor, Vertex >::value),

                vertex_bundle_type< Graph >, edge_bundle_type< Graph > >::type

                bundler;

        public:

            typedef typename bundler::type type;

        };

        template < typename Graph >

        class bundled_result< Graph, graph_bundle_t >

        {

            typedef typename graph_traits< Graph >::vertex_descriptor Vertex;

            typedef graph_bundle_type< Graph > bundler;

        public:

            typedef typename bundler::type type;

        };

    }

} // namespace graph::detail

namespace graph_detail

{

    // A helper metafunction for determining whether or not a type is

    // bundled.

    template < typename T >

    struct is_no_bundle : mpl::bool_< is_same< T, no_property >::value >

    {

    };

} // namespace graph_detail

/** @name Graph Property Traits

 * These metafunctions (along with those above), can be used to access the

 * vertex and edge properties (bundled or otherwise) of vertices and

 * edges.

 */

//@{

template < typename Graph >

struct has_graph_property

: mpl::not_< typename detail::is_no_property<

      typename graph_property_type< Graph >::type >::type >::type

{

};

template < typename Graph >

struct has_bundled_graph_property

: mpl::not_<

      graph_detail::is_no_bundle< typename graph_bundle_type< Graph >::type > >

{

};

template < typename Graph >

struct has_vertex_property

: mpl::not_< typename detail::is_no_property<

      typename vertex_property_type< Graph >::type > >::type

{

};

template < typename Graph >

struct has_bundled_vertex_property

: mpl::not_<

      graph_detail::is_no_bundle< typename vertex_bundle_type< Graph >::type > >

{

};

template < typename Graph >

struct has_edge_property

: mpl::not_< typename detail::is_no_property<

      typename edge_property_type< Graph >::type > >::type

{

};

template < typename Graph >

struct has_bundled_edge_property

: mpl::not_<

      graph_detail::is_no_bundle< typename edge_bundle_type< Graph >::type > >

{

};

//@}

} // namespace boost

// Since pair is in namespace std, Koenig lookup will find source and

// target if they are also defined in namespace std.  This is illegal,

// but the alternative is to put source and target in the global

// namespace which causes name conflicts with other libraries (like

// SUIF).

namespace std

{

/* Some helper functions for dealing with pairs as edges */

template < class T, class G > T source(pair< T, T > p, const G&)

{

    return p.first;

}

template < class T, class G > T target(pair< T, T > p, const G&)

{

    return p.second;

}

}

#if defined(__GNUC__) && defined(__SGI_STL_PORT)

// For some reason g++ with STLport does not see the above definition

// of source() and target() unless we bring them into the boost

// namespace.

namespace boost

{

using std::source;

using std::target;

}

#endif

#endif // BOOST_GRAPH_TRAITS_HPP