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 <boost/config.hpp>
9#include <fstream>
10#include <iostream>
11#include <string>
12#include <boost/graph/adjacency_list.hpp>
13#include <boost/graph/graph_utility.hpp>
14
15using namespace boost;
16
17namespace std
18{
19template < typename T >
20std::istream& operator>>(std::istream& in, std::pair< T, T >& p)
21{
22 in >> p.first >> p.second;
23 return in;
24}
25}
26
27typedef adjacency_list< listS, // Store out-edges of each vertex in a std::list
28 vecS, // Store vertex set in a std::vector
29 directedS // The file dependency graph is directed
30 >
31 file_dep_graph;
32
33typedef graph_traits< file_dep_graph >::vertex_descriptor vertex_t;
34typedef graph_traits< file_dep_graph >::edge_descriptor edge_t;
35
36void topo_sort_dfs(
37 const file_dep_graph& g, vertex_t u, vertex_t*& topo_order, int* mark)
38{
39 mark[u] = 1; // 1 means visited, 0 means not yet visited
40 graph_traits< file_dep_graph >::adjacency_iterator vi, vi_end;
41 for (boost::tie(t0&: vi, t1&: vi_end) = adjacent_vertices(u, g_: g); vi != vi_end; ++vi)
42 if (mark[*vi] == 0)
43 topo_sort_dfs(g, u: *vi, topo_order, mark);
44
45 *--topo_order = u;
46}
47
48void topo_sort(const file_dep_graph& g, vertex_t* topo_order)
49{
50 std::vector< int > mark(num_vertices(g_: g), 0);
51 graph_traits< file_dep_graph >::vertex_iterator vi, vi_end;
52 for (boost::tie(t0&: vi, t1&: vi_end) = vertices(g_: g); vi != vi_end; ++vi)
53 if (mark[*vi] == 0)
54 topo_sort_dfs(g, u: *vi, topo_order, mark: &mark[0]);
55}
56
57int main(int argc, const char** argv)
58{
59 std::ifstream file_in(argc >= 2 ? argv[1] : "makefile-dependencies.dat");
60 typedef graph_traits< file_dep_graph >::vertices_size_type size_type;
61 size_type n_vertices;
62 file_in >> n_vertices; // read in number of vertices
63 std::istream_iterator< std::pair< size_type, size_type > > input_begin(
64 file_in),
65 input_end;
66#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
67 // VC++ can't handle the iterator constructor
68 file_dep_graph g(n_vertices);
69 while (input_begin != input_end)
70 {
71 size_type i, j;
72 boost::tie(i, j) = *input_begin++;
73 add_edge(i, j, g);
74 }
75#else
76 file_dep_graph g(input_begin, input_end, n_vertices);
77#endif
78
79 std::vector< std::string > name(num_vertices(g_: g));
80 std::ifstream name_in(argc >= 3 ? argv[2] : "makefile-target-names.dat");
81 graph_traits< file_dep_graph >::vertex_iterator vi, vi_end;
82 for (boost::tie(t0&: vi, t1&: vi_end) = vertices(g_: g); vi != vi_end; ++vi)
83 name_in >> name[*vi];
84
85 std::vector< vertex_t > order(num_vertices(g_: g));
86 topo_sort(g, topo_order: &order[0] + num_vertices(g_: g));
87 for (size_type i = 0; i < num_vertices(g_: g); ++i)
88 std::cout << name[order[i]] << std::endl;
89
90 return 0;
91}
92

source code of boost/libs/graph/example/topo-sort-file-dep.cpp