- Main Page
- Namespaces
- Classes
- Files

# topological_sort.hpp

Go to the documentation of this file.

    00001
    00003 #ifndef TOPOLOGICAL_SORT_HPP_
    00004 #define TOPOLOGICAL_SORT_HPP_
    00005
    00006 #include <queue>
    00007 #include <stdexcept>
    00008
    00009 #include <iostream>
    00010 #include <ostream>
    00011 #include "data.hpp"
    00012
    00019 template<class Graph, class Nodes>
    00020 void topsort_clean_graph(Graph& graph, Nodes& nodes)
    00021 {
    00022   for (typename Graph::iterator iter(graph.begin()); iter != graph.end(); )
    00023   {
    00024     if (iter->second.empty())
    00025     {
    00026       nodes.push(iter->first);
    00027       graph.erase(iter++);  // advance iterator before erase invalidates it
    00028     }
    00029     else
    00030       ++iter;
    00031   }
    00032 }
    00033
    00042 template<class Graph, class OutIterator>
    00043 void topological_sort(Graph graph, OutIterator sorted)
    00044 {
    00045   std::queue<typename Graph::key_type> nodes;
    00046   // Start with the set of nodes with no incoming edges.
    00047   topsort_clean_graph(graph, nodes);
    00048
    00049   while (not nodes.empty())
    00050   {
    00051     // Grab the first node to process, output it to sorted,
    00052     // and remove it from the graph.
    00053     typename Graph::key_type n(nodes.front());
    00054     nodes.pop();
    00055     *sorted = n;
    00056     ++sorted;
    00057
    00058     // Erase n from the graph
    00059     for (typename Graph::iterator iter(graph.begin()); iter != graph.end(); ++iter)
    00060     {
    00061       iter->second.erase(n);
    00062     }
    00063     // After removing n, find any nodes that no longer
    00064     // have any incoming edges.
    00065     topsort_clean_graph(graph, nodes);
    00066   }
    00067   if (not graph.empty())
    00068     throw std::invalid_argument("Dependency graph contains cycles");
    00069 }
    00070
    00071 #endif // TOPOLOGICAL_SORT_HPP_