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 | |
---|

7 | typedef lemon::ListGraph Graph; |
---|

8 | typedef Graph::NodeIt NodeIt; |
---|

9 | typedef Graph::Node Node; |
---|

10 | |
---|

11 | namespace boost { |
---|

12 | |
---|

13 | template<> |
---|

14 | struct 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 | |
---|

60 | inline std::pair<graph_traits<Graph>::vertex_iterator, |
---|

61 | graph_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 | |
---|

66 | graph_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 | |
---|

73 | int main(int argc, char **argv) { |
---|

74 | boost::function_requires<boost::VertexListGraphConcept<Graph> >(); |
---|

75 | return 0; |
---|

76 | } |
---|