1 //=======================================================================
2 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
3 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
4 //
5 // Distributed under the Boost Software License, Version 1.0. (See
6 // accompanying file LICENSE_1_0.txt or copy at
7 // http://www.boost.org/LICENSE_1_0.txt)
8 //=======================================================================
9 #include <boost/config.hpp>
10 #include <iostream>
11 #include <list>
12 #include <algorithm>
13 #include <boost/graph/adjacency_list.hpp>
14 #include <boost/graph/topological_sort.hpp>
15 #include <iterator>
16 #include <utility>
17
18
19 typedef std::pair<std::size_t,std::size_t> Pair;
20
21 /*
22 Topological sort example
23
24 The topological sort algorithm creates a linear ordering
25 of the vertices such that if edge (u,v) appears in the graph,
26 then u comes before v in the ordering.
27
28 Sample output:
29
30 A topological ordering: 2 5 0 1 4 3
31
32 */
33
34 int
main(int,char * [])35 main(int , char* [])
36 {
37 //begin
38 using namespace boost;
39
40 /* Topological sort will need to color the graph. Here we use an
41 internal decorator, so we "property" the color to the graph.
42 */
43 typedef adjacency_list<vecS, vecS, directedS,
44 property<vertex_color_t, default_color_type> > Graph;
45
46 typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;
47 Pair edges[6] = { Pair(0,1), Pair(2,4),
48 Pair(2,5),
49 Pair(0,3), Pair(1,4),
50 Pair(4,3) };
51 #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
52 // VC++ can't handle the iterator constructor
53 Graph G(6);
54 for (std::size_t j = 0; j < 6; ++j)
55 add_edge(edges[j].first, edges[j].second, G);
56 #else
57 Graph G(edges, edges + 6, 6);
58 #endif
59
60 boost::property_map<Graph, vertex_index_t>::type id = get(vertex_index, G);
61
62 typedef std::vector< Vertex > container;
63 container c;
64 topological_sort(G, std::back_inserter(c));
65
66 std::cout << "A topological ordering: ";
67 for (container::reverse_iterator ii = c.rbegin();
68 ii != c.rend(); ++ii)
69 std::cout << id[*ii] << " ";
70 std::cout << std::endl;
71
72 return 0;
73 }
74
75