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 #include <boost/config.hpp>
10 #include <assert.h>
11 #include <iostream>
12
13 #include <vector>
14 #include <algorithm>
15 #include <utility>
16
17
18 #include <boost/graph/adjacency_list.hpp>
19 #include <boost/graph/depth_first_search.hpp>
20 #include <boost/graph/visitors.hpp>
21
22 /*
23 This calculates the discover finishing time.
24
25 Sample Output
26
27 Tree edge: 0 --> 2
28 Tree edge: 2 --> 1
29 Back edge: 1 --> 1
30 Finish edge: 1 --> 1
31 Tree edge: 1 --> 3
32 Back edge: 3 --> 1
33 Finish edge: 3 --> 1
34 Tree edge: 3 --> 4
35 Back edge: 4 --> 0
36 Finish edge: 4 --> 0
37 Back edge: 4 --> 1
38 Finish edge: 4 --> 1
39 Forward or cross edge: 2 --> 3
40 Finish edge: 2 --> 3
41 Finish edge: 0 --> 2
42 1 10
43 3 8
44 2 9
45 4 7
46 5 6
47
48 */
49
50 using namespace boost;
51 using namespace std;
52
53
54 template <class VisitorList>
55 struct edge_categorizer : public dfs_visitor<VisitorList> {
56 typedef dfs_visitor<VisitorList> Base;
57
edge_categorizeredge_categorizer58 edge_categorizer(const VisitorList& v = null_visitor()) : Base(v) { }
59
60 template <class Edge, class Graph>
tree_edgeedge_categorizer61 void tree_edge(Edge e, Graph& G) {
62 cout << "Tree edge: " << source(e, G) <<
63 " --> " << target(e, G) << endl;
64 Base::tree_edge(e, G);
65 }
66 template <class Edge, class Graph>
back_edgeedge_categorizer67 void back_edge(Edge e, Graph& G) {
68 cout << "Back edge: " << source(e, G)
69 << " --> " << target(e, G) << endl;
70 Base::back_edge(e, G);
71 }
72 template <class Edge, class Graph>
forward_or_cross_edgeedge_categorizer73 void forward_or_cross_edge(Edge e, Graph& G) {
74 cout << "Forward or cross edge: " << source(e, G)
75 << " --> " << target(e, G) << endl;
76 Base::forward_or_cross_edge(e, G);
77 }
78 template <class Edge, class Graph>
finish_edgeedge_categorizer79 void finish_edge(Edge e, Graph& G) {
80 cout << "Finish edge: " << source(e, G) <<
81 " --> " << target(e, G) << endl;
82 Base::finish_edge(e, G);
83 }
84 };
85 template <class VisitorList>
86 edge_categorizer<VisitorList>
categorize_edges(const VisitorList & v)87 categorize_edges(const VisitorList& v) {
88 return edge_categorizer<VisitorList>(v);
89 }
90
91 int
main(int,char * [])92 main(int , char* [])
93 {
94
95 using namespace boost;
96
97 typedef adjacency_list<> Graph;
98
99 Graph G(5);
100 add_edge(0, 2, G);
101 add_edge(1, 1, G);
102 add_edge(1, 3, G);
103 add_edge(2, 1, G);
104 add_edge(2, 3, G);
105 add_edge(3, 1, G);
106 add_edge(3, 4, G);
107 add_edge(4, 0, G);
108 add_edge(4, 1, G);
109
110 typedef graph_traits<Graph>::vertices_size_type size_type;
111
112 std::vector<size_type> d(num_vertices(G));
113 std::vector<size_type> f(num_vertices(G));
114 int t = 0;
115 depth_first_search(G, visitor(categorize_edges(
116 make_pair(stamp_times(&d[0], t, on_discover_vertex()),
117 stamp_times(&f[0], t, on_finish_vertex())))));
118
119 std::vector<size_type>::iterator i, j;
120 for (i = d.begin(), j = f.begin(); i != d.end(); ++i, ++j)
121 cout << *i << " " << *j << endl;
122
123 return 0;
124 }
125
126