123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148 |
- //=======================================================================
- // 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;
- }
|