sl@0: //=======================================================================
sl@0: // Copyright 2001 Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee, 
sl@0: //
sl@0: // Distributed under the Boost Software License, Version 1.0. (See
sl@0: // accompanying file LICENSE_1_0.txt or copy at
sl@0: // http://www.boost.org/LICENSE_1_0.txt)
sl@0: //=======================================================================
sl@0: 
sl@0: /*
sl@0:  * © Portions copyright (c) 2006-2007 Nokia Corporation.  All rights reserved.
sl@0: */
sl@0: 
sl@0: 
sl@0: #include <boost/graph/adjacency_list.hpp>
sl@0: #include <boost/graph/breadth_first_search.hpp>
sl@0: #include <boost/pending/indirect_cmp.hpp>
sl@0: #include <boost/pending/integer_range.hpp>
sl@0: 
sl@0: #include <iostream>
sl@0: 
sl@0: #ifdef __SYMBIAN32__
sl@0: #include "std_log_result.h"
sl@0: #define LOG_FILENAME_LINE __FILE__, __LINE__
sl@0: #endif
sl@0: 
sl@0: using namespace boost;
sl@0: template < typename TimeMap > class bfs_time_visitor:public default_bfs_visitor {
sl@0:   typedef typename property_traits < TimeMap >::value_type T;
sl@0: public:
sl@0:   bfs_time_visitor(TimeMap tmap, T & t):m_timemap(tmap), m_time(t) { }
sl@0:   template < typename Vertex, typename Graph >
sl@0:     void discover_vertex(Vertex u, const Graph & g) const
sl@0:   {
sl@0:     put(m_timemap, u, m_time++);
sl@0:   }
sl@0:   TimeMap m_timemap;
sl@0:   T & m_time;
sl@0: };
sl@0: 
sl@0: 
sl@0: int
sl@0: main()
sl@0: {
sl@0:   using namespace boost;
sl@0:   // Select the graph type we wish to use
sl@0:   typedef adjacency_list < vecS, vecS, undirectedS > graph_t;
sl@0:   // Set up the vertex IDs and names
sl@0:   enum { r, s, t, u, v, w, x, y, N };
sl@0:   const char *name = "rstuvwxy";
sl@0:   // Specify the edges in the graph
sl@0:   typedef std::pair < int, int >E;
sl@0:   E edge_array[] = { E(r, s), E(r, v), E(s, w), E(w, r), E(w, t),
sl@0:     E(w, x), E(x, t), E(t, u), E(x, y), E(u, y)
sl@0:   };
sl@0:   // Create the graph object
sl@0:   const int n_edges = sizeof(edge_array) / sizeof(E);
sl@0: #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
sl@0:   // VC++ has trouble with the edge iterator constructor
sl@0:   graph_t g(N);
sl@0:   for (std::size_t j = 0; j < n_edges; ++j)
sl@0:     add_edge(edge_array[j].first, edge_array[j].second, g);
sl@0: #else
sl@0:   typedef graph_traits<graph_t>::vertices_size_type v_size_t;
sl@0:   graph_t g(edge_array, edge_array + n_edges, v_size_t(N));
sl@0: #endif
sl@0: 
sl@0:   // Typedefs
sl@0:   typedef graph_traits < graph_t >::vertex_descriptor Vertex;
sl@0:   typedef graph_traits < graph_t >::vertices_size_type Size;
sl@0:   typedef Size* Iiter;
sl@0: 
sl@0:   // a vector to hold the discover time property for each vertex
sl@0:   std::vector < Size > dtime(num_vertices(g));
sl@0: 
sl@0:   Size time = 0;
sl@0:   bfs_time_visitor < Size * >vis(&dtime[0], time);
sl@0:   breadth_first_search(g, vertex(s, g), visitor(vis));
sl@0: 
sl@0:   // Use std::sort to order the vertices by their discover time
sl@0:   std::vector<graph_traits<graph_t>::vertices_size_type > discover_order(N);
sl@0:   integer_range < int >range(0, N);
sl@0:   std::copy(range.begin(), range.end(), discover_order.begin());
sl@0:   std::sort(discover_order.begin(), discover_order.end(),
sl@0:             indirect_cmp < Iiter, std::less < Size > >(&dtime[0]));
sl@0: 
sl@0:   std::cout << "order of discovery: ";
sl@0:   for (int i = 0; i < N; ++i)
sl@0:     std::cout << name[discover_order[i]] << " ";
sl@0:   std::cout << std::endl;
sl@0: 
sl@0:    #ifdef __SYMBIAN32__
sl@0: 	std_log(LOG_FILENAME_LINE,"[End Test Case ]");
sl@0:   	testResultXml("bfs-example");
sl@0: 	close_log_file();
sl@0:   #endif
sl@0:   return EXIT_SUCCESS;
sl@0: }