ceph/src/boost/libs/graph/example/topo-sort1.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 <deque>                // to store the vertex ordering
   9 #include <vector>
  10 #include <list>
  11 #include <iostream>
  12 #include <boost/graph/vector_as_graph.hpp>
  13 #include <boost/graph/topological_sort.hpp>
  14
  15 int
  16 main()
  17 {
  18   using namespace boost;
  19   const char *tasks[] = {
  20     "pick up kids from school",
  21     "buy groceries (and snacks)",
  22     "get cash at ATM",
  23     "drop off kids at soccer practice",
  24     "cook dinner",
  25     "pick up kids from soccer",
  26     "eat dinner"
  27   };
  28   const int n_tasks = sizeof(tasks) / sizeof(char *);
  29
  30   std::vector < std::list < int > > g(n_tasks);
  31   g[0].push_back(3);
  32   g[1].push_back(3);
  33   g[1].push_back(4);
  34   g[2].push_back(1);
  35   g[3].push_back(5);
  36   g[4].push_back(6);
  37   g[5].push_back(6);
  38
  39   std::deque < int >topo_order;
  40
  41   topological_sort(g, std::front_inserter(topo_order),
  42                    vertex_index_map(identity_property_map()));
  43
  44   int n = 1;
  45   for (std::deque < int >::iterator i = topo_order.begin();
  46        i != topo_order.end(); ++i, ++n)
  47     std::cout << tasks[*i] << std::endl;
  48
  49   return EXIT_SUCCESS;
  50 }