graflo.architecture.evolution.ordering

Order resources so that each runs after the resources it depends on.

Attributes

__all__ = ['order_resources'] module-attribute

Functions:

order_resources(declared, constraints)

The declared order, moved only as far as constraints require.

Each constraint (before, after) asks that before run first. A stable topological sort over the strongly connected components of the constraints: at each step the first component, in declared order of its earliest member, whose predecessors outside it are all placed comes next, its members in declared order. Resources no constraint names keep their relative order. A name declared does not list is ignored, as is a resource constrained against itself.

Returns:

Type	Description
list[str]	The order, and the constraints it leaves unsatisfied. Those are empty
list[tuple[str, str]]	unless the constraints form a cycle; then only the resources in the
tuple[list[str], list[tuple[str, str]]]	cycle keep their declared order among themselves, and each constraint
tuple[list[str], list[tuple[str, str]]]	between two of them that this order violates is returned, in declared
tuple[list[str], list[tuple[str, str]]]	order of their after resource.

Source code in graflo/architecture/evolution/ordering.py

def order_resources(
    declared: Sequence[str], constraints: Iterable[tuple[str, str]]
) -> tuple[list[str], list[tuple[str, str]]]:
    """The declared order, moved only as far as *constraints* require.

    Each constraint ``(before, after)`` asks that *before* run first. A stable
    topological sort over the strongly connected components of the
    constraints: at each step the first component, in declared order of its
    earliest member, whose predecessors outside it are all placed comes next,
    its members in declared order. Resources no constraint names keep their
    relative order. A name *declared* does not list is ignored, as is a
    resource constrained against itself.

    Returns:
        The order, and the constraints it leaves unsatisfied. Those are empty
        unless the constraints form a cycle; then only the resources in the
        cycle keep their declared order among themselves, and each constraint
        between two of them that this order violates is returned, in declared
        order of their ``after`` resource.
    """
    names = list(declared)
    position = {name: i for i, name in enumerate(names)}
    pairs = sorted(
        {
            (before, after)
            for before, after in constraints
            if before in position and after in position and before != after
        },
        key=lambda pair: (position[pair[1]], position[pair[0]]),
    )
    successors: dict[str, list[str]] = {name: [] for name in names}
    for before, after in pairs:
        successors[before].append(after)

    component = _components(names, successors, position)
    members: dict[int, list[str]] = {}
    for name in names:
        members.setdefault(component[name], []).append(name)
    predecessors: dict[int, set[int]] = {c: set() for c in members}
    for before, after in pairs:
        if component[before] != component[after]:
            predecessors[component[after]].add(component[before])

    # ``members`` holds the components in declared order of their earliest
    # member: the order a tie among ready components is broken in.
    order: list[str] = []
    placed: set[int] = set()
    while len(placed) < len(members):
        ready = next(
            c for c in members if c not in placed and predecessors[c] <= placed
        )
        order.extend(members[ready])
        placed.add(ready)
    return order, [
        (before, after)
        for before, after in pairs
        if component[before] == component[after] and position[before] > position[after]
    ]