C++ Reference: topologicalsorter

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.


  vector result;
  vector nodes = {"a", "b", "c"};
  vector> 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 sorting means that if
   nodes A and B appear in that order and aren't ancestors of each other,
   they will remain in that order in the returned topological order.


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

TopologicalSorter classes below.

#include "ortools/base/vector32.h"