hbutils.algorithm.topological

Overview:

Implement of topological sorting algorithm.

Wikipedia: Topological sorting.

topoids

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

Topological sort with nodes count and edges.

Arguments:

  • n (int): Count of nodes.

  • edges (Collection[Tuple[int, int]]): Collection of edges, in each tuple (x, y), means x should be earlier appeared than y in the final sequence.

  • sort (bool): Keep the output list in order. When open, the time complexity will increase an extra \(O\left(\log{N}\right)\) because of the maintenance of heap. Default is False, which means no not keep the strict order.

Returns:

  • sequence (List[int]): Sorted sequence.

Example:
>>> 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, sort: bool = False) → List[_ElementType][source]
Overview:

Topological sort with objects and their edges.

Arguments:

  • items (Iterable[_ElementType]): List of the items.

  • edges (Collection[Tuple[_ElementType, _ElementType]]): Collection of edges, in each tuple (x, y), means x should be earlier appeared than y in the final sequence.

  • identifier (Callable[[_ElementType], _IdType]): Identifier function for the items, need to make sure the output id value is hashable. Default is None, which means use the id value of the objects.

  • sort (bool): Keep the output list in order. When open, the time complexity will increase an extra \(O\left(\log{N}\right)\) because of the maintenance of heap. Default is False, which means no not keep the strict order.

Returns:

  • sequence (List[_ElementType]): Sorted sequence.

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))