]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | /* | |
f67539c2 | 24 | |
7c673cae FG |
25 | Sample Output: |
26 | ||
f67539c2 TL |
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 | |
7c673cae FG |
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 | ||
f67539c2 TL |
43 | template < class ParentDecorator > struct print_parent |
44 | { | |
45 | print_parent(const ParentDecorator& p_) : p(p_) {} | |
46 | template < class Vertex > void operator()(const Vertex& v) const | |
47 | { | |
48 | std::cout << "parent[" << v << "] = " << p[v] << std::endl; | |
49 | } | |
50 | ParentDecorator p; | |
7c673cae FG |
51 | }; |
52 | ||
f67539c2 | 53 | template < class DistanceMap, class PredecessorMap, class ColorMap > |
7c673cae FG |
54 | class distance_and_pred_visitor : public neighbor_bfs_visitor<> |
55 | { | |
f67539c2 TL |
56 | typedef typename property_traits< ColorMap >::value_type ColorValue; |
57 | typedef color_traits< ColorValue > Color; | |
58 | ||
7c673cae | 59 | public: |
f67539c2 TL |
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 > | |
66 | 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 > | |
74 | 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; | |
7c673cae FG |
85 | }; |
86 | ||
f67539c2 | 87 | int main(int, char*[]) |
7c673cae | 88 | { |
f67539c2 TL |
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: "; | |
7c673cae | 137 | #ifdef BOOST_OLD_STREAM_ITERATORS |
f67539c2 | 138 | std::copy(d, d + 5, std::ostream_iterator< int, char >(std::cout, " ")); |
7c673cae | 139 | #else |
f67539c2 | 140 | std::copy(d, d + 5, std::ostream_iterator< int >(std::cout, " ")); |
7c673cae | 141 | #endif |
f67539c2 | 142 | std::cout << std::endl; |
7c673cae | 143 | |
f67539c2 TL |
144 | std::for_each(vertices(G).first, vertices(G).second, |
145 | print_parent< Piter >(&p[0])); | |
146 | } | |
7c673cae | 147 | |
f67539c2 | 148 | return 0; |
7c673cae | 149 | } |