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