williamr@2: //======================================================================= williamr@2: // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. williamr@2: // Copyright 2006 The Trustees of Indiana University. williamr@2: // Copyright (C) 2001 Vladimir Prus williamr@2: // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek, Douglas Gregor williamr@2: // williamr@2: // Distributed under the Boost Software License, Version 1.0. (See williamr@2: // accompanying file LICENSE_1_0.txt or copy at williamr@2: // http://www.boost.org/LICENSE_1_0.txt) williamr@2: //======================================================================= williamr@2: williamr@2: // The mutating functions (add_edge, etc.) were added by Vladimir Prus. williamr@2: williamr@2: #ifndef BOOST_VECTOR_AS_GRAPH_HPP williamr@2: #define BOOST_VECTOR_AS_GRAPH_HPP williamr@2: williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: williamr@2: /* williamr@2: This module implements the VertexListGraph concept using a williamr@2: std::vector as the "back-bone" of the graph (the vector *is* the williamr@2: graph object). The edge-lists type of the graph is templated, so the williamr@2: user can choose any STL container, so long as the value_type of the williamr@2: container is convertible to the size_type of the vector. For now any williamr@2: graph properties must be stored seperately. williamr@2: williamr@2: This module requires the C++ compiler to support partial williamr@2: specialization for the graph_traits class, so this is not portable williamr@2: to VC++. williamr@2: williamr@2: */ williamr@2: williamr@2: #ifdef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION williamr@2: #error The vector-as-graph module requires a compiler that supports partial specialization williamr@2: #endif williamr@2: williamr@2: williamr@2: namespace boost { williamr@2: namespace detail { williamr@2: template struct val_out_edge_ret; williamr@2: template struct val_out_edge_iter; williamr@2: template struct val_edge; williamr@2: } williamr@2: } williamr@2: williamr@2: #if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION williamr@2: namespace boost { williamr@2: williamr@2: struct vector_as_graph_traversal_tag williamr@2: : public vertex_list_graph_tag, williamr@2: public adjacency_graph_tag, williamr@2: public incidence_graph_tag { }; williamr@2: williamr@2: template williamr@2: struct graph_traits< std::vector > williamr@2: { williamr@2: typedef typename EdgeList::value_type V; williamr@2: typedef V vertex_descriptor; williamr@2: typedef typename detail::val_edge::type edge_descriptor; williamr@2: typedef typename EdgeList::const_iterator adjacency_iterator; williamr@2: typedef typename detail::val_out_edge_iter::type williamr@2: out_edge_iterator; williamr@2: typedef void in_edge_iterator; williamr@2: typedef void edge_iterator; williamr@2: typedef typename integer_range::iterator vertex_iterator; williamr@2: typedef directed_tag directed_category; williamr@2: typedef allow_parallel_edge_tag edge_parallel_category; williamr@2: typedef vector_as_graph_traversal_tag traversal_category; williamr@2: typedef typename std::vector::size_type vertices_size_type; williamr@2: typedef void edges_size_type; williamr@2: typedef typename EdgeList::size_type degree_size_type; williamr@2: }; williamr@2: template williamr@2: struct edge_property_type< std::vector > williamr@2: { williamr@2: typedef void type; williamr@2: }; williamr@2: template williamr@2: struct vertex_property_type< std::vector > williamr@2: { williamr@2: typedef void type; williamr@2: }; williamr@2: template williamr@2: struct graph_property_type< std::vector > williamr@2: { williamr@2: typedef void type; williamr@2: }; williamr@2: } williamr@2: #endif williamr@2: williamr@2: namespace boost { williamr@2: williamr@2: namespace detail { williamr@2: williamr@2: // "val" is short for Vector Adjacency List williamr@2: williamr@2: template williamr@2: struct val_edge williamr@2: { williamr@2: typedef typename EdgeList::value_type V; williamr@2: typedef std::pair type; williamr@2: }; williamr@2: williamr@2: // need rewrite this using boost::iterator_adaptor williamr@2: template williamr@2: class val_out_edge_iterator williamr@2: : public boost::iterator, williamr@2: std::ptrdiff_t, std::pair*, const std::pair > williamr@2: { williamr@2: typedef val_out_edge_iterator self; williamr@2: typedef std::pair Edge; williamr@2: public: williamr@2: val_out_edge_iterator() { } williamr@2: val_out_edge_iterator(V s, Iter i) : _source(s), _iter(i) { } williamr@2: Edge operator*() const { return Edge(_source, *_iter); } williamr@2: self& operator++() { ++_iter; return *this; } williamr@2: self operator++(int) { self t = *this; ++_iter; return t; } williamr@2: bool operator==(const self& x) const { return _iter == x._iter; } williamr@2: bool operator!=(const self& x) const { return _iter != x._iter; } williamr@2: protected: williamr@2: V _source; williamr@2: Iter _iter; williamr@2: }; williamr@2: williamr@2: template williamr@2: struct val_out_edge_iter williamr@2: { williamr@2: typedef typename EdgeList::value_type V; williamr@2: typedef typename EdgeList::const_iterator Iter; williamr@2: typedef val_out_edge_iterator type; williamr@2: }; williamr@2: williamr@2: template williamr@2: struct val_out_edge_ret williamr@2: { williamr@2: typedef typename val_out_edge_iter::type IncIter; williamr@2: typedef std::pair type; williamr@2: }; williamr@2: williamr@2: } // namesapce detail williamr@2: williamr@2: template williamr@2: typename detail::val_out_edge_ret::type williamr@2: out_edges(typename EdgeList::value_type v, williamr@2: const std::vector& g) williamr@2: { williamr@2: typedef typename detail::val_out_edge_iter::type Iter; williamr@2: typedef typename detail::val_out_edge_ret::type return_type; williamr@2: return return_type(Iter(v, g[v].begin()), Iter(v, g[v].end())); williamr@2: } williamr@2: williamr@2: template williamr@2: typename EdgeList::size_type williamr@2: out_degree(typename EdgeList::value_type v, williamr@2: const std::vector& g) williamr@2: { williamr@2: return g[v].size(); williamr@2: } williamr@2: williamr@2: template williamr@2: std::pair williamr@2: adjacent_vertices(typename EdgeList::value_type v, williamr@2: const std::vector& g) williamr@2: { williamr@2: return std::make_pair(g[v].begin(), g[v].end()); williamr@2: } williamr@2: williamr@2: // source() and target() already provided for pairs in graph_traits.hpp williamr@2: williamr@2: template williamr@2: std::pair williamr@2: ::iterator, williamr@2: typename boost::integer_range williamr@2: ::iterator > williamr@2: vertices(const std::vector& v) williamr@2: { williamr@2: typedef typename boost::integer_range williamr@2: ::iterator Iter; williamr@2: return std::make_pair(Iter(0), Iter(v.size())); williamr@2: } williamr@2: williamr@2: template williamr@2: typename std::vector::size_type williamr@2: num_vertices(const std::vector& v) williamr@2: { williamr@2: return v.size(); williamr@2: } williamr@2: williamr@2: template williamr@2: typename std::pair::type, bool> williamr@2: add_edge(typename EdgeList::value_type u, typename EdgeList::value_type v, williamr@2: std::vector& g) williamr@2: { williamr@2: typedef typename detail::val_edge::type edge_type; williamr@2: g[u].insert(g[u].end(), v); williamr@2: return std::make_pair(edge_type(u, v), true); williamr@2: } williamr@2: williamr@2: template williamr@2: typename std::pair::type, bool> williamr@2: edge(typename EdgeList::value_type u, typename EdgeList::value_type v, williamr@2: std::vector& g) williamr@2: { williamr@2: typedef typename detail::val_edge::type edge_type; williamr@2: typename EdgeList::iterator i = g[u].begin(), end = g[u].end(); williamr@2: for (; i != end; ++i) williamr@2: if (*i == v) williamr@2: return std::make_pair(edge_type(u, v), true); williamr@2: return std::make_pair(edge_type(), false); williamr@2: } williamr@2: williamr@2: template williamr@2: void williamr@2: remove_edge(typename EdgeList::value_type u, typename EdgeList::value_type v, williamr@2: std::vector& g) williamr@2: { williamr@2: typename EdgeList::iterator i = std::remove(g[u].begin(), g[u].end(), v); williamr@2: if (i != g[u].end()) williamr@2: g[u].erase(i, g[u].end()); williamr@2: } williamr@2: williamr@2: template williamr@2: void williamr@2: remove_edge(typename detail::val_edge::type e, williamr@2: std::vector& g) williamr@2: { williamr@2: typename EdgeList::value_type u, v; williamr@2: u = e.first; williamr@2: v = e.second; williamr@2: // FIXME: edge type does not fully specify the edge to be deleted williamr@2: typename EdgeList::iterator i = std::remove(g[u].begin(), g[u].end(), v); williamr@2: if (i != g[u].end()) williamr@2: g[u].erase(i, g[u].end()); williamr@2: } williamr@2: williamr@2: template williamr@2: void williamr@2: remove_edge_if(Predicate p, williamr@2: std::vector& g) williamr@2: { williamr@2: for (std::size_t u = 0; u < g.size(); ++u) { williamr@2: // Oops! gcc gets internal compiler error on compose_....... williamr@2: williamr@2: typedef typename EdgeList::iterator iterator; williamr@2: iterator b = g[u].begin(), e = g[u].end(); williamr@2: williamr@2: if (!g[u].empty()) { williamr@2: williamr@2: for(; b != e;) { williamr@2: if (p(std::make_pair(u, *b))) { williamr@2: --e; williamr@2: if (b == e) williamr@2: break; williamr@2: else williamr@2: iter_swap(b, e); williamr@2: } else { williamr@2: ++b; williamr@2: } williamr@2: } williamr@2: } williamr@2: williamr@2: if (e != g[u].end()) williamr@2: g[u].erase(e, g[u].end()); williamr@2: } williamr@2: } williamr@2: williamr@2: template williamr@2: typename EdgeList::value_type williamr@2: add_vertex(std::vector& g) williamr@2: { williamr@2: g.resize(g.size()+1); williamr@2: return g.size()-1; williamr@2: } williamr@2: williamr@2: template williamr@2: void williamr@2: clear_vertex(typename EdgeList::value_type u, williamr@2: std::vector& g) williamr@2: { williamr@2: g[u].clear(); williamr@2: for (std::size_t i = 0; i < g.size(); ++i) williamr@2: remove_edge(i, u, g); williamr@2: } williamr@2: williamr@2: template williamr@2: void williamr@2: remove_vertex(typename EdgeList::value_type u, williamr@2: std::vector& g) williamr@2: { williamr@2: typedef typename EdgeList::iterator iterator; williamr@2: clear_vertex(u, g); williamr@2: g.erase(g.begin() + u); williamr@2: for (std::size_t i = 0; i < g.size(); ++i) williamr@2: for ( iterator it = g[i].begin(); it != g[i].end(); ++it ) williamr@2: // after clear_vertex *it is never equal to u williamr@2: if ( *it > u ) williamr@2: --*it; williamr@2: } williamr@2: williamr@2: template williamr@2: struct property_map, vertex_index_t> williamr@2: { williamr@2: typedef identity_property_map type; williamr@2: typedef type const_type; williamr@2: }; williamr@2: williamr@2: template williamr@2: identity_property_map williamr@2: get(vertex_index_t, const std::vector&) williamr@2: { williamr@2: return identity_property_map(); williamr@2: } williamr@2: williamr@2: template williamr@2: identity_property_map williamr@2: get(vertex_index_t, std::vector&) williamr@2: { williamr@2: return identity_property_map(); williamr@2: } williamr@2: } // namespace boost williamr@2: williamr@2: #endif // BOOST_VECTOR_AS_GRAPH_HPP