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.

EXAMPLE:

  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.


   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.

#include "ortools/base/vector32.h"

Classes

DenseIntTopologicalSorterTpl
TopologicalSorter