hydra.sorting module

Utilities for sorting. This module includes an implementation of Tarjan’s algorithm, originally based on GraphSCC by Iavor S. Diatchki: https://hackage.haskell.org/package/GraphSCC. Tarjan was chosen because it computes strongly connected components in O(V+E), in a single pass, and yields the components in reverse topological order — exactly the shape every consumer in the kernel (HM let-generalization, schema graph construction, target-language emission) needs.

hydra.sorting.adjacency_list_to_map(pairs: Sequence[tuple[T0, Sequence[T1]]]) → Mapping[T0, Sequence[T1]]

Convert an adjacency list to a map, concatenating values for duplicate keys.

hydra.sorting.adjacency_lists_to_graph(edges0: Sequence[tuple[T0, Sequence[T0]]]) → tuple[Mapping[int, Sequence[int]], Callable[[int], object]]

Given a list of adjacency lists represented as (key, [key]) pairs, construct a graph along with a function mapping each vertex (an Int) back to its original key (Nothing for unknown vertices).

hydra.sorting.create_ordering_isomorphism(source_ord: Sequence[T0], target_ord: Sequence[T0]) → OrderingIsomorphism[T1]

Construct an OrderingIsomorphism between two orderings of the same elements. The two list arguments must be permutations of each other; the result is a pair of mappings that transport an element list from one ordering to the other.

hydra.sorting.find_reachable_nodes(adj: Callable[[T0], Set[T0]], root: T0) → Set[T0]

Given an adjacency function and a distinguished root node, find all reachable nodes (including the root node).

hydra.sorting.initial_state() → TarjanState

Initial state for Tarjan’s algorithm.

hydra.sorting.pop_stack_until(v: int, st0: TarjanState) → tuple[Sequence[int], TarjanState]

Pop vertices off the stack until the given vertex is reached, collecting the current strongly connected component.

hydra.sorting.propagate_tags(edges: Sequence[tuple[T0, Sequence[T0]]], node_tags: Sequence[tuple[T0, Sequence[T1]]]) → Sequence[tuple[T0, Set[T1]]]

Given a graph as an adjacency list of edges and a list of explicit tags per node, compute the full set of tags for each node by propagating tags through edges. If there is an edge from n1 to n2 and n2 has tag t, then n1 also has tag t. Note: pairs in the output are not ordered.

hydra.sorting.strong_connect(graph: Mapping[int, Sequence[int]], v: int, st: TarjanState) → TarjanState

Visit a vertex and recursively explore its successors.

hydra.sorting.strongly_connected_components(graph: Mapping[int, Sequence[int]]) → Sequence[Sequence[int]]

Compute the strongly connected components of the given graph. The components are returned in reverse topological order.

hydra.sorting.topological_sort(pairs: Sequence[tuple[T0, Sequence[T0]]]) → object

Sort a directed acyclic graph (DAG) based on an adjacency list. Yields a list of nontrivial strongly connected components if the graph has cycles, otherwise a simple list.

hydra.sorting.topological_sort_components(pairs: Sequence[tuple[T0, Sequence[T0]]]) → Sequence[Sequence[T0]]

Find the strongly connected components (including cycles and isolated vertices) of a graph, in (reverse) topological order, i.e. dependencies before dependents.

hydra.sorting.topological_sort_nodes(get_key: Callable[[T0], T1], get_adj: Callable[[T0], Sequence[T1]], nodes: Sequence[T0]) → Sequence[Sequence[T0]]

Sort a directed acyclic graph (DAG) of nodes using two helper functions: one for node keys, and one for the adjacency list of connected node keys. The result is a list of strongly-connected components (cycles), in which singleton lists represent acyclic nodes.