# 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
[{ "type": "thumb-down", "id": "missingTheInformationINeed", "label":"Missing the information I need" },{ "type": "thumb-down", "id": "tooComplicatedTooManySteps", "label":"Too complicated / too many steps" },{ "type": "thumb-down", "id": "outOfDate", "label":"Out of date" },{ "type": "thumb-down", "id": "samplesCodeIssue", "label":"Samples / code issue" },{ "type": "thumb-down", "id": "otherDown", "label":"Other" }]
[{ "type": "thumb-up", "id": "easyToUnderstand", "label":"Easy to understand" },{ "type": "thumb-up", "id": "solvedMyProblem", "label":"Solved my problem" },{ "type": "thumb-up", "id": "otherUp", "label":"Other" }]