Template Function sequant::strongly_connected_components_indexed

Function Documentation

template<typename IndexDepFunc>
std::vector<std::size_t> sequant::strongly_connected_components_indexed(std::size_t n, const IndexDepFunc &get_dependencies)

Partitions the indices in [0, n) into the strongly connected components of their dependency graph: two indices share a component iff each depends on the other, directly or through other indices. An index with no cycle through it is a component of its own.

Parameters:

  • n – The number of elements

  • get_dependencies – A function that, given an index in [0, n), yields a range of indices in [0, n) that it depends on

Returns:

per index, the id of its component, in [0, number of components); components are numbered in the order they complete, so an index depends (transitively) only on indices in components with ids at most its own