1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374 |
- //=======================================================================
- // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
- // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
- //
- // Distributed under the Boost Software License, Version 1.0. (See
- // accompanying file LICENSE_1_0.txt or copy at
- // http://www.boost.org/LICENSE_1_0.txt)
- //=======================================================================
- #include <boost/config.hpp>
- #include <iostream>
- #include <list>
- #include <algorithm>
- #include <boost/graph/adjacency_list.hpp>
- #include <boost/graph/topological_sort.hpp>
- #include <iterator>
- #include <utility>
- typedef std::pair<std::size_t,std::size_t> Pair;
- /*
- Topological sort example
- The topological sort algorithm creates a linear ordering
- of the vertices such that if edge (u,v) appears in the graph,
- then u comes before v in the ordering.
- Sample output:
- A topological ordering: 2 5 0 1 4 3
- */
- int
- main(int , char* [])
- {
- //begin
- using namespace boost;
- /* Topological sort will need to color the graph. Here we use an
- internal decorator, so we "property" the color to the graph.
- */
- typedef adjacency_list<vecS, vecS, directedS,
- property<vertex_color_t, default_color_type> > Graph;
- typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;
- Pair edges[6] = { Pair(0,1), Pair(2,4),
- Pair(2,5),
- Pair(0,3), Pair(1,4),
- Pair(4,3) };
- #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
- // VC++ can't handle the iterator constructor
- Graph G(6);
- for (std::size_t j = 0; j < 6; ++j)
- add_edge(edges[j].first, edges[j].second, G);
- #else
- Graph G(edges, edges + 6, 6);
- #endif
- boost::property_map<Graph, vertex_index_t>::type id = get(vertex_index, G);
- typedef std::vector< Vertex > container;
- container c;
- topological_sort(G, std::back_inserter(c));
- std::cout << "A topological ordering: ";
- for (container::reverse_iterator ii = c.rbegin();
- ii != c.rend(); ++ii)
- std::cout << id[*ii] << " ";
- std::cout << std::endl;
- return 0;
- }
|