| //======================================================================= |
| // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. |
| // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek |
| // |
| // Distributed under the Boost Software License, Version 1.0. (See |
| // accompanying file LICENSE_1_0.txt or copy at |
| // http://www.boost.org/LICENSE_1_0.txt) |
| //======================================================================= |
| |
| #include <boost/config.hpp> |
| |
| #include <algorithm> |
| #include <vector> |
| #include <utility> |
| #include <iostream> |
| |
| #include <boost/graph/visitors.hpp> |
| #include <boost/graph/adjacency_list.hpp> |
| #include <boost/graph/graph_utility.hpp> |
| #include <boost/graph/neighbor_bfs.hpp> |
| #include <boost/property_map/property_map.hpp> |
| |
| /* |
| |
| Sample Output: |
| |
| 0 --> 2 |
| 1 --> 1 3 4 |
| 2 --> 1 3 4 |
| 3 --> 1 4 |
| 4 --> 0 1 |
| distances: 0 2 1 2 1 |
| parent[0] = 0 |
| parent[1] = 2 |
| parent[2] = 0 |
| parent[3] = 2 |
| parent[4] = 0 |
| |
| */ |
| |
| using namespace boost; |
| |
| template <class ParentDecorator> |
| struct print_parent { |
| print_parent(const ParentDecorator& p_) : p(p_) { } |
| template <class Vertex> |
| void operator()(const Vertex& v) const { |
| std::cout << "parent[" << v << "] = " << p[v] << std::endl; |
| } |
| ParentDecorator p; |
| }; |
| |
| template <class DistanceMap, class PredecessorMap, class ColorMap> |
| class distance_and_pred_visitor : public neighbor_bfs_visitor<> |
| { |
| typedef typename property_traits<ColorMap>::value_type ColorValue; |
| typedef color_traits<ColorValue> Color; |
| public: |
| distance_and_pred_visitor(DistanceMap d, PredecessorMap p, ColorMap c) |
| : m_distance(d), m_predecessor(p), m_color(c) { } |
| |
| template <class Edge, class Graph> |
| void tree_out_edge(Edge e, const Graph& g) const |
| { |
| typename graph_traits<Graph>::vertex_descriptor |
| u = source(e, g), v = target(e, g); |
| put(m_distance, v, get(m_distance, u) + 1); |
| put(m_predecessor, v, u); |
| } |
| template <class Edge, class Graph> |
| void tree_in_edge(Edge e, const Graph& g) const |
| { |
| typename graph_traits<Graph>::vertex_descriptor |
| u = source(e, g), v = target(e, g); |
| put(m_distance, u, get(m_distance, v) + 1); |
| put(m_predecessor, u, v); |
| } |
| |
| DistanceMap m_distance; |
| PredecessorMap m_predecessor; |
| ColorMap m_color; |
| }; |
| |
| int main(int , char* []) |
| { |
| typedef adjacency_list< |
| mapS, vecS, bidirectionalS, |
| property<vertex_color_t, default_color_type> |
| > Graph; |
| |
| typedef property_map<Graph, vertex_color_t>::type |
| ColorMap; |
| |
| Graph G(5); |
| add_edge(0, 2, G); |
| add_edge(1, 1, G); |
| add_edge(1, 3, G); |
| add_edge(1, 4, G); |
| add_edge(2, 1, G); |
| add_edge(2, 3, G); |
| add_edge(2, 4, G); |
| add_edge(3, 1, G); |
| add_edge(3, 4, G); |
| add_edge(4, 0, G); |
| add_edge(4, 1, G); |
| |
| typedef Graph::vertex_descriptor Vertex; |
| |
| // Array to store predecessor (parent) of each vertex. This will be |
| // used as a Decorator (actually, its iterator will be). |
| std::vector<Vertex> p(num_vertices(G)); |
| // VC++ version of std::vector has no ::pointer, so |
| // I use ::value_type* instead. |
| typedef std::vector<Vertex>::value_type* Piter; |
| |
| // Array to store distances from the source to each vertex . We use |
| // a built-in array here just for variety. This will also be used as |
| // a Decorator. |
| typedef graph_traits<Graph>::vertices_size_type size_type; |
| size_type d[5]; |
| std::fill_n(d, 5, 0); |
| |
| // The source vertex |
| Vertex s = *(vertices(G).first); |
| p[s] = s; |
| distance_and_pred_visitor<size_type*, Vertex*, ColorMap> |
| vis(d, &p[0], get(vertex_color, G)); |
| neighbor_breadth_first_search |
| (G, s, visitor(vis). |
| color_map(get(vertex_color, G))); |
| |
| print_graph(G); |
| |
| if (num_vertices(G) < 11) { |
| std::cout << "distances: "; |
| #ifdef BOOST_OLD_STREAM_ITERATORS |
| std::copy(d, d + 5, std::ostream_iterator<int, char>(std::cout, " ")); |
| #else |
| std::copy(d, d + 5, std::ostream_iterator<int>(std::cout, " ")); |
| #endif |
| std::cout << std::endl; |
| |
| std::for_each(vertices(G).first, vertices(G).second, |
| print_parent<Piter>(&p[0])); |
| } |
| |
| return 0; |
| } |