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 #include <boost/config.hpp>
11
12 #include <algorithm>
13 #include <vector>
14 #include <utility>
15 #include <iostream>
16
17 #include <boost/graph/visitors.hpp>
18 #include <boost/graph/adjacency_list.hpp>
19 #include <boost/graph/graph_utility.hpp>
20 #include <boost/graph/neighbor_bfs.hpp>
21 #include <boost/property_map/property_map.hpp>
22
23 /*
24
25 Sample Output:
26
27 0 --> 2
28 1 --> 1 3 4
29 2 --> 1 3 4
30 3 --> 1 4
31 4 --> 0 1
32 distances: 0 2 1 2 1
33 parent[0] = 0
34 parent[1] = 2
35 parent[2] = 0
36 parent[3] = 2
37 parent[4] = 0
38
39 */
40
41 using namespace boost;
42
43 template < class ParentDecorator > struct print_parent
44 {
print_parentprint_parent45 print_parent(const ParentDecorator& p_) : p(p_) {}
operator ()print_parent46 template < class Vertex > void operator()(const Vertex& v) const
47 {
48 std::cout << "parent[" << v << "] = " << p[v] << std::endl;
49 }
50 ParentDecorator p;
51 };
52
53 template < class DistanceMap, class PredecessorMap, class ColorMap >
54 class distance_and_pred_visitor : public neighbor_bfs_visitor<>
55 {
56 typedef typename property_traits< ColorMap >::value_type ColorValue;
57 typedef color_traits< ColorValue > Color;
58
59 public:
distance_and_pred_visitor(DistanceMap d,PredecessorMap p,ColorMap c)60 distance_and_pred_visitor(DistanceMap d, PredecessorMap p, ColorMap c)
61 : m_distance(d), m_predecessor(p), m_color(c)
62 {
63 }
64
65 template < class Edge, class Graph >
tree_out_edge(Edge e,const Graph & g) const66 void tree_out_edge(Edge e, const Graph& g) const
67 {
68 typename graph_traits< Graph >::vertex_descriptor u = source(e, g),
69 v = target(e, g);
70 put(m_distance, v, get(m_distance, u) + 1);
71 put(m_predecessor, v, u);
72 }
73 template < class Edge, class Graph >
tree_in_edge(Edge e,const Graph & g) const74 void tree_in_edge(Edge e, const Graph& g) const
75 {
76 typename graph_traits< Graph >::vertex_descriptor u = source(e, g),
77 v = target(e, g);
78 put(m_distance, u, get(m_distance, v) + 1);
79 put(m_predecessor, u, v);
80 }
81
82 DistanceMap m_distance;
83 PredecessorMap m_predecessor;
84 ColorMap m_color;
85 };
86
main(int,char * [])87 int main(int, char*[])
88 {
89 typedef adjacency_list< mapS, vecS, bidirectionalS,
90 property< vertex_color_t, default_color_type > >
91 Graph;
92
93 typedef property_map< Graph, vertex_color_t >::type ColorMap;
94
95 Graph G(5);
96 add_edge(0, 2, G);
97 add_edge(1, 1, G);
98 add_edge(1, 3, G);
99 add_edge(1, 4, G);
100 add_edge(2, 1, G);
101 add_edge(2, 3, G);
102 add_edge(2, 4, G);
103 add_edge(3, 1, G);
104 add_edge(3, 4, G);
105 add_edge(4, 0, G);
106 add_edge(4, 1, G);
107
108 typedef Graph::vertex_descriptor Vertex;
109
110 // Array to store predecessor (parent) of each vertex. This will be
111 // used as a Decorator (actually, its iterator will be).
112 std::vector< Vertex > p(num_vertices(G));
113 // VC++ version of std::vector has no ::pointer, so
114 // I use ::value_type* instead.
115 typedef std::vector< Vertex >::value_type* Piter;
116
117 // Array to store distances from the source to each vertex . We use
118 // a built-in array here just for variety. This will also be used as
119 // a Decorator.
120 typedef graph_traits< Graph >::vertices_size_type size_type;
121 size_type d[5];
122 std::fill_n(d, 5, 0);
123
124 // The source vertex
125 Vertex s = *(vertices(G).first);
126 p[s] = s;
127 distance_and_pred_visitor< size_type*, Vertex*, ColorMap > vis(
128 d, &p[0], get(vertex_color, G));
129 neighbor_breadth_first_search(
130 G, s, visitor(vis).color_map(get(vertex_color, G)));
131
132 print_graph(G);
133
134 if (num_vertices(G) < 11)
135 {
136 std::cout << "distances: ";
137 #ifdef BOOST_OLD_STREAM_ITERATORS
138 std::copy(d, d + 5, std::ostream_iterator< int, char >(std::cout, " "));
139 #else
140 std::copy(d, d + 5, std::ostream_iterator< int >(std::cout, " "));
141 #endif
142 std::cout << std::endl;
143
144 std::for_each(vertices(G).first, vertices(G).second,
145 print_parent< Piter >(&p[0]));
146 }
147
148 return 0;
149 }
150