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 isFalse
, 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 isNone
, 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 isFalse
, 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))