ceph/src/boost/libs/graph/example/topo-sort-with-sgb.cpp

   1 //=======================================================================
   2 // Copyright 2001 Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee,
   3 //
   4 // Distributed under the Boost Software License, Version 1.0. (See
   5 // accompanying file LICENSE_1_0.txt or copy at
   6 // http://www.boost.org/LICENSE_1_0.txt)
   7 //=======================================================================
   8 #include <vector>
   9 #include <string>
  10 #include <iostream>
  11 #include <boost/graph/stanford_graph.hpp>
  12 #include <boost/graph/topological_sort.hpp>
  13
  14 int
  15 main()
  16 {
  17   using namespace boost;
  18   const int n_vertices = 7;
  19   Graph *sgb_g = gb_new_graph(n_vertices);
  20
  21   const char *tasks[] = {
  22     "pick up kids from school",
  23     "buy groceries (and snacks)",
  24     "get cash at ATM",
  25     "drop off kids at soccer practice",
  26     "cook dinner",
  27     "pick up kids from soccer",
  28     "eat dinner"
  29   };
  30   const int n_tasks = sizeof(tasks) / sizeof(char *);
  31
  32   gb_new_arc(sgb_g->vertices + 0, sgb_g->vertices + 3, 0);
  33   gb_new_arc(sgb_g->vertices + 1, sgb_g->vertices + 3, 0);
  34   gb_new_arc(sgb_g->vertices + 1, sgb_g->vertices + 4, 0);
  35   gb_new_arc(sgb_g->vertices + 2, sgb_g->vertices + 1, 0);
  36   gb_new_arc(sgb_g->vertices + 3, sgb_g->vertices + 5, 0);
  37   gb_new_arc(sgb_g->vertices + 4, sgb_g->vertices + 6, 0);
  38   gb_new_arc(sgb_g->vertices + 5, sgb_g->vertices + 6, 0);
  39
  40   typedef graph_traits < Graph * >::vertex_descriptor vertex_t;
  41   std::vector < vertex_t > topo_order;
  42   topological_sort(sgb_g, std::back_inserter(topo_order),
  43                    vertex_index_map(get(vertex_index, sgb_g)));
  44   int n = 1;
  45   for (std::vector < vertex_t >::reverse_iterator i = topo_order.rbegin();
  46        i != topo_order.rend(); ++i, ++n)
  47     std::cout << n << ": " << tasks[get(vertex_index, sgb_g)[*i]] << std::endl;
  48
  49   gb_recycle(sgb_g);
  50   return EXIT_SUCCESS;
  51 }