hbutils.algorithm.topological

Overview:

Implement of topological sorting algorithm.

This module provides two main functions for performing topological sorting: - topoids: Performs topological sort on nodes represented by integers - topo: Performs topological sort on arbitrary objects with custom identifiers

Wikipedia: Topological sorting.

topoids

hbutils.algorithm.topological.topoids(n: int, edges: Collection[Tuple[int, int]], sort: bool = False) → List[int][source]

Topological sort with nodes count and edges.

This function performs a topological sort on a directed acyclic graph (DAG) represented by integer node IDs and edges. It uses Kahn’s algorithm for topological sorting.

Parameters:

  • n (int) – Count of nodes in the graph (nodes are numbered from 0 to n-1).

  • edges (Collection[Tuple[int, int]]) – Collection of directed edges, where each tuple (x, y) means node x should appear earlier than node y in the final sequence.

  • sort (bool) – Keep the output list in order. When True, the time complexity will increase by an extra \(O\left(\log{N}\right)\) due to heap maintenance. Default is False, which means no strict order is maintained.

Returns:

Sorted sequence of node IDs in topological order.

Return type:

List[int]

Raises:

  • ArithmeticError – If the graph contains a cycle or invalid node references, making topological sorting impossible.

  • AssertionError – If edge endpoints are not valid node IDs (not in range [0, n)).

Examples:

>>> topoids(3, [])
[0, 1, 2]
>>> topoids(3, [(0, 1), (2, 1)])
[0, 2, 1]
>>> topoids(3, [(0, 1), (2, 1), (1, 0)])
ArithmeticError: ('Invalid topological graph, for some node ids not accessible - (0, 1).', (0, 1))

>>> topoids(4, [(0, 2), (0, 1), (2, 3), (1, 3)])
[0, 1, 2, 3]  # [0, 2, 1, 3] is also possible
>>> topoids(4, [(0, 2), (0, 1), (2, 3), (1, 3)], sort=True)
[0, 1, 2, 3]  # only [0, 1, 2, 3] is possible

topo

hbutils.algorithm.topological.topo(items: Iterable[_ElementType], edges: Collection[Tuple[_ElementType, _ElementType]], identifier: Callable[[_ElementType], _IdType] | None = None, sort: bool = False) → List[_ElementType][source]

Topological sort with objects and their edges.

This function performs topological sorting on arbitrary objects by converting them to integer IDs internally and then using the topoids function. It allows custom identifier functions to determine object uniqueness.

Parameters:

  • items (Iterable[_ElementType]) – Iterable of items to be sorted.

  • edges (Collection[Tuple[_ElementType, _ElementType]]) – Collection of directed edges, where each tuple (x, y) means item x should appear earlier than item y in the final sequence.

  • identifier (Callable[[_ElementType], _IdType], optional) – Identifier function for the items. Must return a hashable value that uniquely identifies each item. Default is None, which uses Python’s built-in id() function (object identity).

  • sort (bool) – Keep the output list in order. When True, the time complexity will increase by an extra \(O\left(\log{N}\right)\) due to heap maintenance. Default is False, which means no strict order is maintained.

Returns:

Sorted sequence of items in topological order.

Return type:

List[_ElementType]

Raises:

ArithmeticError – If the graph contains a cycle, making topological sorting impossible.

Examples:

>>> n1 = _Container(1)  # _Container is a hashable wrapper class
>>> n2 = _Container('sdfklj')
>>> n3 = _Container((2, 3))
>>> n4 = _Container((3, 'sdj'))
>>> n5 = _Container(1)
>>> topo([n1, n2, n3], [], sort=True)
[n1, n2, n3]
>>> topo([n1, n2, n5], [(n1, n2), (n5, n2)], sort=True)
[n1, n5, n2]
>>> topo([n1, n2, n5], [(n1, n2), (n5, n2)], identifier=lambda x: x.v, sort=True)
[n1, n2]
>>> topo([n1, n2, n3, n4], [(n1, n3), (n3, n1), (n2, n3), (n4, n1)])
ArithmeticError: ('Invalid topological graph, for some items not accessible - (n1, n3).', (n1, n3))