This class template provides data structures required to sort the partial unsorted edges into a total ordered set of nodes. The value type of the nodes(*) must be hashable and equality comparable by bsl::hash, and bsl::equal_to respectively.

Synopsis

Declared in <bdlb_topologicalsortutil.h>

template<class INPUT_ITER>
class TopologicalSortUtil_Helper;

Description

* (*) The value type is determined by first getting the iterator's value type using bsl::iterator_traits<INPUT_ITER>::ValueType and then using TopologicalSortUtilEdgeTraits::ValueType on that result.

Member Functions

Name

Description

TopologicalSortUtil_Helper [constructor]

Create a helper class that holds the different data structures required to sort in topological order the directed acyclic graph described by the specified relationsBegin and relationsEnd. Optionally, specify an allocator for needed memory. If allocator is 0, use the globally supply default allocator instead.

processNextNodeInOrder

Write the next element in order that doesn't have any predecessors into the specified resultOutIter_p output iterator then increment it and return true. If there are still elements left but all of them still have predecessors do nothing and return false. The behavior is undefined unless !d_workSet.empty().

sortImpl

Sort the input elements provided during construction in topological order and write the resulting linear ordered set into the specified resultOutIter and return true. If the sort is unsuccessful (the input is not an acyclic directed graph) write the nodes that have not been sorted to the specified unsortedOutIter output and return false. See TopologicalSortUtil::sort "iterators overload" for more detailed specification.

operator BloombergLP::bslmf::NestedTraitDeclaration<TopologicalSortUtil_Helper, UsesBslmaAllocator>

Nested trait declaration for bslma::UsesBslmaAllocator.

Created with MrDocs