C++ Reference: topologicalsorter

Note: This documentation is automatically generated.

TopologicalSorter provides topologically sorted traversal of the nodes of a directed acyclic graph (DAG) with up to INT_MAX nodes. It sorts ancestor nodes before their descendants.

If your graph is not a DAG and you're reading this, you are probably looking for ortools/graph/strongly_connected_components.h which does the topological decomposition of a directed graph.

EXAMPLE:

vector<int> result; vector<string> nodes = {"a", "b", "c"}; vector<pair<string, string>> arcs = { { "a", "c"}, {"a", "b"}, {"b", "c" } }; if (util::StableTopologicalSort(num_nodes, arcs, &result)) { LOG(INFO) << "The topological order is: " << gtl::LogContainer(result); } else { LOG(INFO) << "The graph is cyclic."; // Note: you can extract a cycle with the TopologicalSorter class, or // with the API defined in circularity_detector.h. } // This will be successful and result will be equal to {"a", "b", "c"}.

There are 8 flavors of topological sort, from these 3 bits:
   - There are OrDie() versions that directly return the topological order, or
   crash if a cycle is detected (and LOG the cycle).
   - There are type-generic versions that can take any node type (including
   non-dense integers), but slower, or the "dense int" versions which requires
   nodes to be a dense interval [0..num_nodes-1]. Note that the type must
   be compatible with LOG << T if you're using the OrDie() version.
   - The sorting can be either stable or not. "Stable" essentially means that it
   will preserve the order of nodes, if possible. More precisely, the returned
   topological order will be the lexicographically minimal valid order, where
   "lexicographic" applies to the indices of the nodes.


   TopologicalSort()
   TopologicalSortOrDie()
   StableTopologicalSort()
   StableTopologicalSortOrDie()
   DenseIntTopologicalSort()
   DenseIntTopologicalSortOrDie()
   DenseIntStableTopologicalSort()
   DenseIntStableTopologicalSortOrDie()

If you need more control, or a step-by-step topological sort, see the

TopologicalSorter classes below.

Classes
DenseIntTopologicalSorterTpl
TopologicalSorter