Ticket #294: testgraph.cpp

#include <lemon/list_graph.h>

#include <boost/graph/graph_traits.hpp>
#include <boost/graph/graph_concepts.hpp>
#include <boost/iterator/iterator_facade.hpp>

typedef lemon::ListGraph Graph;
typedef Graph::NodeIt NodeIt;
typedef Graph::Node Node;

namespace boost {

template<>
struct graph_traits<Graph> {

        typedef Graph::Node vertex_descriptor;
        typedef directed_tag directed_category;
        typedef allow_parallel_edge_tag edge_parallel_category;
        typedef int vertices_size_type;

        struct traversal_category: public virtual forward_traversal_tag,
                        public virtual vertex_list_graph_tag {
        };

        class vertex_iterator: public iterator_facade<vertex_iterator, Node,
                        forward_traversal_tag, const Node&> {
        public:
                vertex_iterator(const Graph& g) :
                        base(g) {
                }

                vertex_iterator(lemon::Invalid arg = lemon::INVALID) :
                        base(arg) {
                }

        private:
                const Node& dereference() const {
                        return base;
                }

                bool equal(const vertex_iterator& other) const {
                        return base == other.base;
                }

                void increment() {
                        ++base;
                }
                //void decrement() { base = g->pred_node(base); }

                NodeIt base;

                friend class iterator_core_access;
        };

        static vertex_descriptor null_vertex() {
                return Node();
        }
};

inline std::pair<graph_traits<Graph>::vertex_iterator,
graph_traits<Graph>::vertex_iterator> vertices(const Graph& g) {
        typedef graph_traits<Graph>::vertex_iterator Iter;
        return std::make_pair(Iter(g), Iter(lemon::INVALID));
}

graph_traits<Graph>::vertices_size_type num_vertices(const Graph& g) {
        //FIXME: takes O(n) for ListGraphs
        return lemon::countNodes(g);
}

} // namespace boost

int main(int argc, char **argv) {
        boost::function_requires<boost::VertexListGraphConcept<Graph> >();
        return 0;
}