//======================================================================= | |
// 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 */ |