Hi, In the spirit of vector_as_graph.hpp, I created map_as_graph.hpp. One useful feature is that the vertex_descriptor can be any user-defined type, such as a string or an arbitrary object. It's not in a form that's ready to be included in Boost, but I have found it occasionally useful. I though I'd post it in the case that someone else found it useful. If someone found it useful enough that he or she where interested in further developing to the point where it could be included in Boost, please be my guest. Cheers, Shaun #ifndef MAP_AS_GRAPH_HPP #define MAP_AS_GRAPH_HPP 1 #include <boost/graph/graph_traits.hpp> #include <cassert> #include <map> #include <utility> // for make_pair namespace boost { /** * A std::map is a model of a directed graph. * @author Shaun Jackman <sjackman@gmail.com> */ template <typename V, typename T> struct graph_traits<std::map<V, T> > { // Graph typedef V vertex_descriptor; typedef boost::directed_tag directed_category; struct traversal_category : boost::adjacency_graph_tag, boost::vertex_list_graph_tag { }; typedef boost::disallow_parallel_edge_tag edge_parallel_category; // IncidenceGraph typedef std::pair<vertex_descriptor, vertex_descriptor> edge_descriptor; typedef size_t degree_size_type; /** Iterate through the out edges of a vertex. */ struct out_edge_iterator : std::map<V, typename T::mapped_type>::const_iterator { typedef typename std::map<V, typename T::mapped_type>::const_iterator It; out_edge_iterator(const It& it, vertex_descriptor src) : It(it), m_src(src) { } edge_descriptor operator*() const { return edge_descriptor(m_src, It::operator*().first); } private: vertex_descriptor m_src; }; // BidirectionalGraph typedef void in_edge_iterator; // AdjacencyGraph /** Iterate through the adjacent vertices of a vertex. */ struct adjacency_iterator : std::map<V, typename T::mapped_type>::const_iterator { typedef typename std::map<V, typename T::mapped_type>::const_iterator It; adjacency_iterator(const It& it) : It(it) { } const vertex_descriptor& operator*() const { return It::operator*().first; } }; // VertexListGraph /** Iterate through the vertices of this graph. */ struct vertex_iterator : std::map<V, T>::const_iterator { typedef typename std::map<V, T>::const_iterator It; vertex_iterator(const It& it) : It(it) { } const vertex_descriptor& operator*() const { return It::operator*().first; } }; typedef size_t vertices_size_type; // EdgeListGraph typedef void edge_iterator; typedef void edges_size_type; }; // graph_traits<std::map> // IncidenceGraph template <typename V, typename T> std::pair< typename graph_traits<std::map<V, T> >::out_edge_iterator, typename graph_traits<std::map<V, T> >::out_edge_iterator> out_edges( typename graph_traits<std::map<V, T> >::vertex_descriptor u, const std::map<V, T>& g) { typedef typename graph_traits<std::map<V, T> >::out_edge_iterator out_edge_iterator; typename std::map<V, T>::const_iterator it = g.find(u); assert(it != g.end()); return make_pair( out_edge_iterator(it->second.begin(), u), out_edge_iterator(it->second.end(), u)); } template <typename V, typename T> typename graph_traits<std::map<V, T> >::degree_size_type out_degree( typename graph_traits<std::map<V, T> >::vertex_descriptor u, const std::map<V, T>& g) { typename std::map<V, T>::const_iterator it = g.find(u); assert(it != g.end()); return it->second.size(); } // AdjacencyGraph template <typename V, typename T> std::pair<typename graph_traits<std::map<V, T> >::adjacency_iterator, typename graph_traits<std::map<V, T> >::adjacency_iterator> adjacent_vertices( typename graph_traits<std::map<V, T> >::vertex_descriptor u, const std::map<V, T>& g) { typename std::map<V, T>::const_iterator it = g.find(u); assert(it != g.end()); return make_pair(it->second.begin(), it->second.end()); } // VertexListGraph template <typename V, typename T> std::pair<typename graph_traits<std::map<V, T> >::vertex_iterator, typename graph_traits<std::map<V, T> >::vertex_iterator> vertices(const std::map<V, T>& g) { return make_pair(g.begin(), g.end()); } // AdjacencyMatrix template <typename V, typename T> std::pair< typename graph_traits<std::map<V, T> >::edge_descriptor, bool> edge( typename graph_traits<std::map<V, T> >::vertex_descriptor u, typename graph_traits<std::map<V, T> >::vertex_descriptor v, std::map<V, T>& g) { typename std::map<V, T>::const_iterator it = g.find(u); return std::make_pair(make_pair(u, v), it == g.end() ? false : it->second.count(v) > 0); } // VertexMutableGraph template <typename V, typename T> void remove_vertex( typename graph_traits<std::map<V, T> >::vertex_descriptor u, std::map<V, T>& g) { size_t n = g.erase(u); assert(n == 1); (void)n; } // EdgeMutableGraph template <typename V, typename T> void clear_out_edges( typename graph_traits<std::map<V, T> >::vertex_descriptor u, std::map<V, T>& g) { typename std::map<V, T>::iterator it = g.find(u); assert(it != g.end()); it->second.clear(); } template <typename V, typename T> std::pair< typename graph_traits<std::map<V, T> >::edge_descriptor, bool> add_edge( typename graph_traits<std::map<V, T> >::vertex_descriptor u, typename graph_traits<std::map<V, T> >::vertex_descriptor v, std::map<V, T>& g) { typename edge_property<std::map<V, T> >::type ep; return make_pair(std::make_pair(u, v), g[u].insert(make_pair(v, ep)).second); } template <typename V, typename T> void remove_edge( typename graph_traits<std::map<V, T> >::vertex_descriptor u, typename graph_traits<std::map<V, T> >::vertex_descriptor v, std::map<V, T>& g) { size_t n = g[u].erase(v); assert(n == 1); (void)n; } // PropertyGraph template <typename V, typename T> no_property get(vertex_bundle_t, const std::map<V, T>&, typename graph_traits<std::map<V, T> >::vertex_descriptor) { return no_property(); } template <typename V, typename T> const typename T::mapped_type& get(edge_bundle_t, const std::map<V, T>& g, typename graph_traits<std::map<V, T> >::edge_descriptor e) { typename std::map<V, T>::const_iterator u = g.find(source(e, g)); assert(u != g.end()); typename T::const_iterator v = u->second.find(target(e, g)); assert(v != u->second.end()); return v->second; } // MutablePropertyGraph namespace boost { template <typename V, typename T> class vertex_property<std::map<V, T> > { public: typedef no_property type; }; template <typename V, typename T> class edge_property<std::map<V, T> > { public: typedef typename T::mapped_type type; }; } template <typename V, typename T> std::pair< typename graph_traits<std::map<V, T> >::edge_descriptor, bool> add_edge( typename graph_traits<std::map<V, T> >::vertex_descriptor u, typename graph_traits<std::map<V, T> >::vertex_descriptor v, typename edge_property<std::map<V, T> >::type ep, std::map<V, T>& g) { return make_pair(std::make_pair(u, v), g[u].insert(std::make_pair(v, ep)).second); } } // namespace boost #endif