1 //=======================================================================
2 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
3 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
4 //
5 // Distributed under the Boost Software License, Version 1.0. (See
6 // accompanying file LICENSE_1_0.txt or copy at
7 // http://www.boost.org/LICENSE_1_0.txt)
8 //=======================================================================
9 //
10 // Sample output
11 //
12 // DFS categorized directed graph
13 // tree: 0 --> 2
14 // tree: 2 --> 1
15 // back: 1 --> 1
16 // tree: 1 --> 3
17 // back: 3 --> 1
18 // tree: 3 --> 4
19 // back: 4 --> 0
20 // back: 4 --> 1
21 // forward or cross: 2 --> 3
22
23 // BFS categorized directed graph
24 // tree: 0 --> 2
25 // tree: 2 --> 1
26 // tree: 2 --> 3
27 // cycle: 1 --> 1
28 // cycle: 1 --> 3
29 // cycle: 3 --> 1
30 // tree: 3 --> 4
31 // cycle: 4 --> 0
32 // cycle: 4 --> 1
33
34 #include <boost/config.hpp>
35 #include <iostream>
36 #include <vector>
37 #include <algorithm>
38 #include <utility>
39 #include <string>
40
41 #include <boost/graph/visitors.hpp>
42 #include <boost/graph/graph_utility.hpp>
43 #include <boost/graph/adjacency_list.hpp>
44 #include <boost/graph/breadth_first_search.hpp>
45 #include <boost/graph/depth_first_search.hpp>
46
47 using namespace boost;
48 using namespace std;
49
50 template <class Tag>
51 struct edge_printer : public base_visitor<edge_printer<Tag> > {
52 typedef Tag event_filter;
edge_printeredge_printer53 edge_printer(std::string edge_t) : m_edge_type(edge_t) { }
54 template <class Edge, class Graph>
operator ()edge_printer55 void operator()(Edge e, Graph& G) {
56 std::cout << m_edge_type << ": " << source(e, G)
57 << " --> " << target(e, G) << std::endl;
58 }
59 std::string m_edge_type;
60 };
61 template <class Tag>
print_edge(std::string type,Tag)62 edge_printer<Tag> print_edge(std::string type, Tag) {
63 return edge_printer<Tag>(type);
64 }
65
66 int
main(int,char * [])67 main(int, char*[])
68 {
69
70 using namespace boost;
71
72 typedef adjacency_list<> Graph;
73 typedef std::pair<int,int> E;
74 E edges[] = { E(0, 2),
75 E(1, 1), E(1, 3),
76 E(2, 1), E(2, 3),
77 E(3, 1), E(3, 4),
78 E(4, 0), E(4, 1) };
79 #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
80 Graph G(5);
81 for (std::size_t j = 0; j < sizeof(edges)/sizeof(E); ++j)
82 add_edge(edges[j].first, edges[j].second, G);
83 #else
84 Graph G(edges, edges + sizeof(edges)/sizeof(E), 5);
85 #endif
86
87 typedef boost::graph_traits<Graph>::vertices_size_type size_type;
88
89 std::vector<size_type> d(num_vertices(G));
90 std::vector<size_type> f(num_vertices(G));
91
92 cout << "DFS categorized directed graph" << endl;
93 depth_first_search(G, visitor(make_dfs_visitor(
94 make_list(print_edge("tree", on_tree_edge()),
95 print_edge("back", on_back_edge()),
96 print_edge("forward or cross", on_forward_or_cross_edge())
97 ))));
98
99 cout << endl << "BFS categorized directed graph" << endl;
100 boost::breadth_first_search
101 (G, vertex(0, G), visitor(make_bfs_visitor(
102 std::make_pair(print_edge("tree", on_tree_edge()),
103 print_edge("cycle", on_non_tree_edge())))));
104
105 return 0;
106 }
107
108