Ticket #1021: bug_report_example_skeleton.hpp

#include <boost/property_map.hpp>
#include <boost/graph/properties.hpp>
#include <boost/graph/adjacency_iterator.hpp>
#include <vector>

/// A skeleton user defined graph not using any of the builtin Boost Graph Library graph types.
namespace MyGraph {

    class Graph;
    class Vertex;
    class Edge;

    typedef Vertex* VertexDesc;
    typedef Edge* EdgeDesc;
    typedef std::vector<EdgeDesc>::iterator EdgeIterator;
    typedef std::vector<VertexDesc>::iterator VertexIterator;

    class Vertex {
    public:
        unsigned int index();
        std::pair<EdgeIterator, EdgeIterator> outEdges() const;
        std::pair<EdgeIterator, EdgeIterator> inEdges() const;
        unsigned int outEdgeCount() const;
        unsigned int inEdgeCount() const;
        EdgeIterator outEdgeBegin() const;
        EdgeIterator outEdgeEnd() const;
        EdgeIterator inEdgeBegin() const;
        EdgeIterator inEdgeEnd() const;
        void clearEdges();
    };

    class Edge {
    public:
        unsigned int index() const;
        VertexDesc source() const;
        VertexDesc target() const;
    };

    class Graph {
    public:
        std::pair<EdgeIterator, EdgeIterator> edges() const;
        std::pair<VertexIterator, VertexIterator> vertices() const;
        unsigned int vertexCount() const;
        unsigned int edgeCount() const;
        std::pair<EdgeDesc, bool> findEdge(VertexDesc source, VertexDesc target) const;
        VertexDesc addVertex();
        void removeVertex(VertexDesc vertex);
        std::pair<EdgeDesc, bool> addEdge(VertexDesc source, VertexDesc target);
        void removeEdge(EdgeDesc edge);
    };

} // namespace MyGraph

/// An adapter to allow the user defined graph MyGraph to be used as a Boost Graph.
namespace boost {

    /// The Boost Graph Library algorithms use graph_traits to obtain
    /// information about the types to use to access the graph.
    template <>
    struct graph_traits<MyGraph::Graph> {

        // Our user defined graph models all of the following concepts:
        struct bidir_adj_list_traversal_tag :
            public virtual vertex_list_graph_tag,
            public virtual incidence_graph_tag,
            public virtual adjacency_graph_tag,
            public virtual edge_list_graph_tag,
            public virtual bidirectional_graph_tag { };

        // Graph requires:
        typedef MyGraph::VertexDesc                     vertex_descriptor;
        typedef MyGraph::EdgeDesc                       edge_descriptor;
        typedef directed_tag                            directed_category;
        typedef disallow_parallel_edge_tag              edge_parallel_category;
        typedef bidir_adj_list_traversal_tag            traversal_category;

        static inline vertex_descriptor null_vertex()
        {
            return MyGraph::VertexDesc(0);
        }

        // IncidenceGraph requires:
        typedef MyGraph::EdgeIterator                   out_edge_iterator;
        typedef unsigned int                            degree_size_type;

        // BidirectionalGraph requires:
        typedef MyGraph::EdgeIterator                   in_edge_iterator;

        // Adjacency Graph requires:
        typedef adjacency_iterator_generator
            <MyGraph::Graph, vertex_descriptor, out_edge_iterator>::type
                                                        adjacency_iterator;

        // VertexListGraph requires:
        typedef MyGraph::VertexIterator                 vertex_iterator;
        typedef unsigned int                            vertices_size_type;

        // EdgeListGraph requires:
        typedef MyGraph::EdgeIterator                   edge_iterator;
        typedef unsigned int                            edges_size_type;
    };

} // namespace boost

/// In addition we must provide the following operations.
/// These definitions are logically part of MyGraph.
namespace MyGraph {

    /// IncidenceGraph refines Graph requires:
    inline
    std::pair<boost::graph_traits<MyGraph::Graph>::out_edge_iterator,
              boost::graph_traits<MyGraph::Graph>::out_edge_iterator>
    out_edges(boost::graph_traits<MyGraph::Graph>::vertex_descriptor v, const MyGraph::Graph& g)
    {
        return v->outEdges();
    }

    inline
    boost::graph_traits<MyGraph::Graph>::vertex_descriptor
    source(boost::graph_traits<MyGraph::Graph>::edge_descriptor e, const MyGraph::Graph& g)
    {
        return e->source();
    }

    inline
    boost::graph_traits<MyGraph::Graph>::vertex_descriptor
    target(boost::graph_traits<MyGraph::Graph>::edge_descriptor e, const MyGraph::Graph& g)
    {
        return e->target();
    }

    inline
    boost::graph_traits<MyGraph::Graph>::degree_size_type
    out_degree(boost::graph_traits<MyGraph::Graph>::vertex_descriptor v, const MyGraph::Graph& g)
    {
        return v->outEdgeCount();
    }


    /// BidirectionalGraph refines IncidenceGraph and requires:
    inline
    std::pair<boost::graph_traits<MyGraph::Graph>::in_edge_iterator, boost::graph_traits<MyGraph::Graph>::in_edge_iterator>
    in_edges(boost::graph_traits<MyGraph::Graph>::vertex_descriptor v, const MyGraph::Graph& g)
    {
        return v->inEdges();
    }

    inline
    boost::graph_traits<MyGraph::Graph>::degree_size_type
    in_degree(boost::graph_traits<MyGraph::Graph>::vertex_descriptor v, const MyGraph::Graph& g)
    {
        return v->inEdgeCount();
    }

    inline
    boost::graph_traits<MyGraph::Graph>::degree_size_type
    degree(boost::graph_traits<MyGraph::Graph>::vertex_descriptor v, const MyGraph::Graph& g)
    {
        return in_degree(v, g) + out_degree(v, g);
    }

    /// AdjacencyGraph refines Graph and requires:
    inline
    std::pair<boost::graph_traits<MyGraph::Graph>::adjacency_iterator, boost::graph_traits<MyGraph::Graph>::adjacency_iterator>
    adjacent_vertices(boost::graph_traits<MyGraph::Graph>::vertex_descriptor v, const MyGraph::Graph& g)
    {
        boost::graph_traits<MyGraph::Graph>::adjacency_iterator begin(v->outEdgeBegin(), &g);
        boost::graph_traits<MyGraph::Graph>::adjacency_iterator end(v->outEdgeEnd(), &g);
        return std::make_pair(begin, end);
    }

    /// VertexListGraph refines IncidenceGraph and AdjacencyGraph and requires:
    inline
    std::pair<boost::graph_traits<MyGraph::Graph>::vertex_iterator, boost::graph_traits<MyGraph::Graph>::vertex_iterator>
    vertices(const MyGraph::Graph& g)
    {
        return g.vertices();
    }

    inline
    boost::graph_traits<MyGraph::Graph>::vertices_size_type
    num_vertices(const MyGraph::Graph& g)
    {
        return g.vertexCount();
    }

    /// EdgeListGraph refines Graph and requires:
    inline
    std::pair<boost::graph_traits<MyGraph::Graph>::edge_iterator, boost::graph_traits<MyGraph::Graph>::edge_iterator>
    edges(const MyGraph::Graph& g)
    {
        return g.edges();
    }

    inline
    boost::graph_traits<MyGraph::Graph>::edges_size_type
    num_edges(const MyGraph::Graph& g)
    {
        return g.edgeCount();
    }

    /// AdjacencyMatrix refines Graph and requires:
    inline
    std::pair<boost::graph_traits<MyGraph::Graph>::edge_descriptor, bool>
    edge(boost::graph_traits<MyGraph::Graph>::vertex_descriptor u,
         boost::graph_traits<MyGraph::Graph>::vertex_descriptor v, const MyGraph::Graph& g)
    {
        return g.findEdge(u, v);
    }

    /// MutableGraph refines Graph and requires:
    inline
    boost::graph_traits<MyGraph::Graph>::vertex_descriptor
    add_vertex(MyGraph::Graph& g)
    {
        return g.addVertex();
    }

    inline
    void
    clear_vertex(boost::graph_traits<MyGraph::Graph>::vertex_descriptor v, MyGraph::Graph& g)
    {
        v->clearEdges();
    }

    inline
    void
    remove_vertex(boost::graph_traits<MyGraph::Graph>::vertex_descriptor v, MyGraph::Graph& g)
    {
        g.removeVertex(v);
    }

    inline
    std::pair<boost::graph_traits<MyGraph::Graph>::edge_descriptor, bool>
    add_edge(boost::graph_traits<MyGraph::Graph>::vertex_descriptor u, boost::graph_traits<MyGraph::Graph>::vertex_descriptor v,
             MyGraph::Graph& g)
    {
        return g.addEdge(u, v);
    }

    inline
    void
    remove_edge(boost::graph_traits<MyGraph::Graph>::vertex_descriptor u, boost::graph_traits<MyGraph::Graph>::vertex_descriptor v,
                MyGraph::Graph& g)
    {
        std::pair<MyGraph::EdgeDesc, bool> edge_pair = g.findEdge(u, v);
        if (edge_pair.second){
            g.removeEdge(edge_pair.first);
        }

    }

    inline
    void
    remove_edge(boost::graph_traits<MyGraph::Graph>::edge_descriptor e, MyGraph::Graph& g)
    {
        g.removeEdge(e);
    }

    inline
    void
    remove_edge(boost::graph_traits<MyGraph::Graph>::edge_iterator e_iter, MyGraph::Graph& g)
    {
        g.removeEdge(*e_iter);
    }

    /// We also need to provide the predefined property maps used by the algorithms we will use.

    /// The vertex_index_t property map:
    class VertexDescMap
        : public boost::put_get_helper<unsigned int, VertexDescMap>
    {
    public:
        typedef boost::readable_property_map_tag category;
        typedef unsigned int value_type;
        typedef unsigned int reference;
        typedef MyGraph::VertexDesc key_type;
        VertexDescMap()
        {
        }
        VertexDescMap(const MyGraph::Graph& g)
        {
        }

        unsigned int operator[](key_type v) const
        {
            return v->index();
        }
    };

    inline
    VertexDescMap
    get(boost::vertex_index_t, const MyGraph::Graph& g)
    {
        return VertexDescMap(g);
    }

    /// The edge_index_t property map:
    class EdgeDescMap
        : public boost::put_get_helper<EdgeDesc, EdgeDescMap>
    {
    public:
        typedef boost::readable_property_map_tag category;
        typedef unsigned int value_type;
        typedef unsigned int reference;
        typedef MyGraph::EdgeDesc key_type;
        EdgeDescMap()
        {
        }
        EdgeDescMap(const MyGraph::Graph& g)
        {
        }

        unsigned int operator[](key_type e) const
        {
            return e->index();
        }
    };

    inline
    EdgeDescMap
    get(boost::edge_index_t, const MyGraph::Graph& g)
    {
        return EdgeDescMap(g);
    }

} // namespace MyGraph

/// We must also provide specializations for property_map for our
/// graph for the predefined property maps we support.
///
/// NOTE: This mechanism is not currently described in the
/// documentation on how to provide an adapter for a user defined
/// graph.
namespace boost {

    template<>
    struct property_map<MyGraph::Graph, vertex_index_t>
    {
        typedef MyGraph::VertexDescMap type;

        /// The BGL graphs all seem to define their
        /// property_map<...>::const_type the same as their
        /// property_map<...>::type (ie both non-const). It seems that
        /// ::const_type ought to be the const version of ::type.
        /// However, making it a const type results in
        /// make_iterator_property_map not working.
        typedef const MyGraph::VertexDescMap const_type;
    };

    /// We also provide a specialization for the edge_index_t which serves
    /// the same purpose as vertex_index_t except for the edges.
    template<>
    struct property_map<MyGraph::Graph, edge_index_t>
    {
        typedef MyGraph::EdgeDescMap type;
        typedef const MyGraph::EdgeDescMap const_type;
    };

} // namespace boost