COIN-OR::LEMON - Graph Library

Ticket #294: testgraph.cpp

File testgraph.cpp, 1.7 KB (added by chrisatlemon, 10 years ago)
Line 
1#include <lemon/list_graph.h>
2
3#include <boost/graph/graph_traits.hpp>
4#include <boost/graph/graph_concepts.hpp>
5#include <boost/iterator/iterator_facade.hpp>
6
7typedef lemon::ListGraph Graph;
8typedef Graph::NodeIt NodeIt;
9typedef Graph::Node Node;
10
11namespace boost {
12
13template<>
14struct graph_traits<Graph> {
15
16        typedef Graph::Node vertex_descriptor;
17        typedef directed_tag directed_category;
18        typedef allow_parallel_edge_tag edge_parallel_category;
19        typedef int vertices_size_type;
20
21        struct traversal_category: public virtual forward_traversal_tag,
22                        public virtual vertex_list_graph_tag {
23        };
24
25        class vertex_iterator: public iterator_facade<vertex_iterator, Node,
26                        forward_traversal_tag, const Node&> {
27        public:
28                vertex_iterator(const Graph& g) :
29                        base(g) {
30                }
31
32                vertex_iterator(lemon::Invalid arg = lemon::INVALID) :
33                        base(arg) {
34                }
35
36        private:
37                const Node& dereference() const {
38                        return base;
39                }
40
41                bool equal(const vertex_iterator& other) const {
42                        return base == other.base;
43                }
44
45                void increment() {
46                        ++base;
47                }
48                //void decrement() { base = g->pred_node(base); }
49
50                NodeIt base;
51
52                friend class iterator_core_access;
53        };
54
55        static vertex_descriptor null_vertex() {
56                return Node();
57        }
58};
59
60inline std::pair<graph_traits<Graph>::vertex_iterator,
61graph_traits<Graph>::vertex_iterator> vertices(const Graph& g) {
62        typedef graph_traits<Graph>::vertex_iterator Iter;
63        return std::make_pair(Iter(g), Iter(lemon::INVALID));
64}
65
66graph_traits<Graph>::vertices_size_type num_vertices(const Graph& g) {
67        //FIXME: takes O(n) for ListGraphs
68        return lemon::countNodes(g);
69}
70
71} // namespace boost
72
73int main(int argc, char **argv) {
74        boost::function_requires<boost::VertexListGraphConcept<Graph> >();
75        return 0;
76}