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