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 #include <boost/graph/adjacency_list.hpp>
18 #include <boost/graph/depth_first_search.hpp>
19 #include <boost/graph/visitors.hpp>
20
21 /*
22 This calculates the discover finishing time.
23
24 Sample Output
25
26 Tree edge: 0 --> 2
27 Tree edge: 2 --> 1
28 Back edge: 1 --> 1
29 Finish edge: 1 --> 1
30 Tree edge: 1 --> 3
31 Back edge: 3 --> 1
32 Finish edge: 3 --> 1
33 Tree edge: 3 --> 4
34 Back edge: 4 --> 0
35 Finish edge: 4 --> 0
36 Back edge: 4 --> 1
37 Finish edge: 4 --> 1
38 Forward or cross edge: 2 --> 3
39 Finish edge: 2 --> 3
40 Finish edge: 0 --> 2
41 1 10
42 3 8
43 2 9
44 4 7
45 5 6
46
47 */
48
49 using namespace boost;
50 using namespace std;
51
52 template < class VisitorList >
53 struct edge_categorizer : public dfs_visitor< VisitorList >
54 {
55 typedef dfs_visitor< VisitorList > Base;
56
edge_categorizeredge_categorizer57 edge_categorizer(const VisitorList& v = null_visitor()) : Base(v) {}
58
tree_edgeedge_categorizer59 template < class Edge, class Graph > void tree_edge(Edge e, Graph& G)
60 {
61 cout << "Tree edge: " << source(e, G) << " --> " << target(e, G)
62 << endl;
63 Base::tree_edge(e, G);
64 }
back_edgeedge_categorizer65 template < class Edge, class Graph > void back_edge(Edge e, Graph& G)
66 {
67 cout << "Back edge: " << source(e, G) << " --> " << target(e, G)
68 << endl;
69 Base::back_edge(e, G);
70 }
71 template < class Edge, class Graph >
forward_or_cross_edgeedge_categorizer72 void forward_or_cross_edge(Edge e, Graph& G)
73 {
74 cout << "Forward or cross edge: " << source(e, G) << " --> "
75 << target(e, G) << endl;
76 Base::forward_or_cross_edge(e, G);
77 }
finish_edgeedge_categorizer78 template < class Edge, class Graph > void finish_edge(Edge e, Graph& G)
79 {
80 cout << "Finish edge: " << source(e, G) << " --> " << target(e, G)
81 << endl;
82 Base::finish_edge(e, G);
83 }
84 };
85 template < class VisitorList >
categorize_edges(const VisitorList & v)86 edge_categorizer< VisitorList > categorize_edges(const VisitorList& v)
87 {
88 return edge_categorizer< VisitorList >(v);
89 }
90
main(int,char * [])91 int main(int, char*[])
92 {
93
94 using namespace boost;
95
96 typedef adjacency_list<> Graph;
97
98 Graph G(5);
99 add_edge(0, 2, G);
100 add_edge(1, 1, G);
101 add_edge(1, 3, G);
102 add_edge(2, 1, G);
103 add_edge(2, 3, G);
104 add_edge(3, 1, G);
105 add_edge(3, 4, G);
106 add_edge(4, 0, G);
107 add_edge(4, 1, G);
108
109 typedef graph_traits< Graph >::vertices_size_type size_type;
110
111 std::vector< size_type > d(num_vertices(G));
112 std::vector< size_type > f(num_vertices(G));
113 int t = 0;
114 depth_first_search(G,
115 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