//=======================================================================
|
// 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_EDGE_LIST_HPP
|
#define BOOST_GRAPH_EDGE_LIST_HPP
|
|
#include <iterator>
|
#include <boost/config.hpp>
|
#include <boost/mpl/if.hpp>
|
#include <boost/mpl/bool.hpp>
|
#include <boost/range/irange.hpp>
|
#include <boost/graph/graph_traits.hpp>
|
#include <boost/graph/properties.hpp>
|
|
namespace boost
|
{
|
|
//
|
// The edge_list class is an EdgeListGraph module that is constructed
|
// from a pair of iterators whose value type is a pair of vertex
|
// descriptors.
|
//
|
// For example:
|
//
|
// typedef std::pair<int,int> E;
|
// list<E> elist;
|
// ...
|
// typedef edge_list<list<E>::iterator> Graph;
|
// Graph g(elist.begin(), elist.end());
|
//
|
// If the iterators are random access, then Graph::edge_descriptor
|
// is of Integral type, otherwise it is a struct, though it is
|
// convertible to an Integral type.
|
//
|
|
struct edge_list_tag
|
{
|
};
|
|
// The implementation class for edge_list.
|
template < class G, class EdgeIter, class T, class D > class edge_list_impl
|
{
|
public:
|
typedef D edge_id;
|
typedef T Vpair;
|
typedef typename Vpair::first_type V;
|
typedef V vertex_descriptor;
|
typedef edge_list_tag graph_tag;
|
typedef void edge_property_type;
|
|
struct edge_descriptor
|
{
|
edge_descriptor() {}
|
edge_descriptor(EdgeIter p, edge_id id) : _ptr(p), _id(id) {}
|
operator edge_id() { return _id; }
|
EdgeIter _ptr;
|
edge_id _id;
|
};
|
typedef edge_descriptor E;
|
|
struct edge_iterator
|
{
|
typedef edge_iterator self;
|
typedef E value_type;
|
typedef E& reference;
|
typedef E* pointer;
|
typedef std::ptrdiff_t difference_type;
|
typedef std::input_iterator_tag iterator_category;
|
edge_iterator() {}
|
edge_iterator(EdgeIter iter) : _iter(iter), _i(0) {}
|
E operator*() { return E(_iter, _i); }
|
self& operator++()
|
{
|
++_iter;
|
++_i;
|
return *this;
|
}
|
self operator++(int)
|
{
|
self t = *this;
|
++(*this);
|
return t;
|
}
|
bool operator==(const self& x) { return _iter == x._iter; }
|
bool operator!=(const self& x) { return _iter != x._iter; }
|
EdgeIter _iter;
|
edge_id _i;
|
};
|
typedef void out_edge_iterator;
|
typedef void in_edge_iterator;
|
typedef void adjacency_iterator;
|
typedef void vertex_iterator;
|
};
|
|
template < class G, class EI, class T, class D >
|
std::pair< typename edge_list_impl< G, EI, T, D >::edge_iterator,
|
typename edge_list_impl< G, EI, T, D >::edge_iterator >
|
edges(const edge_list_impl< G, EI, T, D >& g_)
|
{
|
const G& g = static_cast< const G& >(g_);
|
typedef typename edge_list_impl< G, EI, T, D >::edge_iterator edge_iterator;
|
return std::make_pair(edge_iterator(g._first), edge_iterator(g._last));
|
}
|
template < class G, class EI, class T, class D >
|
typename edge_list_impl< G, EI, T, D >::vertex_descriptor source(
|
typename edge_list_impl< G, EI, T, D >::edge_descriptor e,
|
const edge_list_impl< G, EI, T, D >&)
|
{
|
return (*e._ptr).first;
|
}
|
template < class G, class EI, class T, class D >
|
typename edge_list_impl< G, EI, T, D >::vertex_descriptor target(
|
typename edge_list_impl< G, EI, T, D >::edge_descriptor e,
|
const edge_list_impl< G, EI, T, D >&)
|
{
|
return (*e._ptr).second;
|
}
|
|
template < class D, class E >
|
class el_edge_property_map
|
: public put_get_helper< D, el_edge_property_map< D, E > >
|
{
|
public:
|
typedef E key_type;
|
typedef D value_type;
|
typedef D reference;
|
typedef readable_property_map_tag category;
|
|
value_type operator[](key_type e) const { return e._i; }
|
};
|
struct edge_list_edge_property_selector
|
{
|
template < class Graph, class Property, class Tag > struct bind_
|
{
|
typedef el_edge_property_map< typename Graph::edge_id,
|
typename Graph::edge_descriptor >
|
type;
|
typedef type const_type;
|
};
|
};
|
template <> struct edge_property_selector< edge_list_tag >
|
{
|
typedef edge_list_edge_property_selector type;
|
};
|
|
template < class G, class EI, class T, class D >
|
typename property_map< edge_list_impl< G, EI, T, D >, edge_index_t >::type get(
|
edge_index_t, const edge_list_impl< G, EI, T, D >&)
|
{
|
typedef typename property_map< edge_list_impl< G, EI, T, D >,
|
edge_index_t >::type EdgeIndexMap;
|
return EdgeIndexMap();
|
}
|
|
template < class G, class EI, class T, class D >
|
inline D get(edge_index_t, const edge_list_impl< G, EI, T, D >&,
|
typename edge_list_impl< G, EI, T, D >::edge_descriptor e)
|
{
|
return e._i;
|
}
|
|
// A specialized implementation for when the iterators are random access.
|
|
struct edge_list_ra_tag
|
{
|
};
|
|
template < class G, class EdgeIter, class T, class D > class edge_list_impl_ra
|
{
|
public:
|
typedef D edge_id;
|
typedef T Vpair;
|
typedef typename Vpair::first_type V;
|
typedef edge_list_ra_tag graph_tag;
|
typedef void edge_property_type;
|
|
typedef edge_id edge_descriptor;
|
typedef V vertex_descriptor;
|
typedef typename boost::integer_range< edge_id >::iterator edge_iterator;
|
typedef void out_edge_iterator;
|
typedef void in_edge_iterator;
|
typedef void adjacency_iterator;
|
typedef void vertex_iterator;
|
};
|
|
template < class G, class EI, class T, class D >
|
std::pair< typename edge_list_impl_ra< G, EI, T, D >::edge_iterator,
|
typename edge_list_impl_ra< G, EI, T, D >::edge_iterator >
|
edges(const edge_list_impl_ra< G, EI, T, D >& g_)
|
{
|
const G& g = static_cast< const G& >(g_);
|
typedef
|
typename edge_list_impl_ra< G, EI, T, D >::edge_iterator edge_iterator;
|
return std::make_pair(edge_iterator(0), edge_iterator(g._last - g._first));
|
}
|
template < class G, class EI, class T, class D >
|
typename edge_list_impl_ra< G, EI, T, D >::vertex_descriptor source(
|
typename edge_list_impl_ra< G, EI, T, D >::edge_descriptor e,
|
const edge_list_impl_ra< G, EI, T, D >& g_)
|
{
|
const G& g = static_cast< const G& >(g_);
|
return g._first[e].first;
|
}
|
template < class G, class EI, class T, class D >
|
typename edge_list_impl_ra< G, EI, T, D >::vertex_descriptor target(
|
typename edge_list_impl_ra< G, EI, T, D >::edge_descriptor e,
|
const edge_list_impl_ra< G, EI, T, D >& g_)
|
{
|
const G& g = static_cast< const G& >(g_);
|
return g._first[e].second;
|
}
|
template < class E >
|
class el_ra_edge_property_map
|
: public put_get_helper< E, el_ra_edge_property_map< E > >
|
{
|
public:
|
typedef E key_type;
|
typedef E value_type;
|
typedef E reference;
|
typedef readable_property_map_tag category;
|
|
value_type operator[](key_type e) const { return e; }
|
};
|
struct edge_list_ra_edge_property_selector
|
{
|
template < class Graph, class Property, class Tag > struct bind_
|
{
|
typedef el_ra_edge_property_map< typename Graph::edge_descriptor > type;
|
typedef type const_type;
|
};
|
};
|
template <> struct edge_property_selector< edge_list_ra_tag >
|
{
|
typedef edge_list_ra_edge_property_selector type;
|
};
|
template < class G, class EI, class T, class D >
|
inline typename property_map< edge_list_impl_ra< G, EI, T, D >,
|
edge_index_t >::type
|
get(edge_index_t, const edge_list_impl_ra< G, EI, T, D >&)
|
{
|
typedef typename property_map< edge_list_impl_ra< G, EI, T, D >,
|
edge_index_t >::type EdgeIndexMap;
|
return EdgeIndexMap();
|
}
|
|
template < class G, class EI, class T, class D >
|
inline D get(edge_index_t, const edge_list_impl_ra< G, EI, T, D >&,
|
typename edge_list_impl_ra< G, EI, T, D >::edge_descriptor e)
|
{
|
return e;
|
}
|
|
// Some helper classes for determining if the iterators are random access
|
template < class Cat > struct is_random
|
{
|
enum
|
{
|
RET = false
|
};
|
typedef mpl::false_ type;
|
};
|
template <> struct is_random< std::random_access_iterator_tag >
|
{
|
enum
|
{
|
RET = true
|
};
|
typedef mpl::true_ type;
|
};
|
|
// The edge_list class conditionally inherits from one of the
|
// above two classes.
|
|
template < class EdgeIter,
|
#if !defined BOOST_NO_STD_ITERATOR_TRAITS
|
class T = typename std::iterator_traits< EdgeIter >::value_type,
|
class D = typename std::iterator_traits< EdgeIter >::difference_type,
|
class Cat = typename std::iterator_traits< EdgeIter >::iterator_category >
|
#else
|
class T, class D, class Cat >
|
#endif
|
class edge_list
|
: public mpl::if_< typename is_random< Cat >::type,
|
edge_list_impl_ra< edge_list< EdgeIter, T, D, Cat >, EdgeIter, T, D >,
|
edge_list_impl< edge_list< EdgeIter, T, D, Cat >, EdgeIter, T, D > >::type
|
{
|
public:
|
typedef directed_tag directed_category;
|
typedef allow_parallel_edge_tag edge_parallel_category;
|
typedef edge_list_graph_tag traversal_category;
|
typedef std::size_t edges_size_type;
|
typedef std::size_t vertices_size_type;
|
typedef std::size_t degree_size_type;
|
edge_list(EdgeIter first, EdgeIter last) : _first(first), _last(last)
|
{
|
m_num_edges = std::distance(first, last);
|
}
|
edge_list(EdgeIter first, EdgeIter last, edges_size_type E)
|
: _first(first), _last(last), m_num_edges(E)
|
{
|
}
|
|
EdgeIter _first, _last;
|
edges_size_type m_num_edges;
|
};
|
|
template < class EdgeIter, class T, class D, class Cat >
|
std::size_t num_edges(const edge_list< EdgeIter, T, D, Cat >& el)
|
{
|
return el.m_num_edges;
|
}
|
|
#ifndef BOOST_NO_STD_ITERATOR_TRAITS
|
template < class EdgeIter >
|
inline edge_list< EdgeIter > make_edge_list(EdgeIter first, EdgeIter last)
|
{
|
return edge_list< EdgeIter >(first, last);
|
}
|
#endif
|
|
} /* namespace boost */
|
|
#endif /* BOOST_GRAPH_EDGE_LIST_HPP */
|
