cottax.core.maths.graph module¶
The graph: node definitions bound to names, the two rules they obey, and everything that follows from owns and reads alone
The rules first: a graph is a set of bindings that satisfies them.
- check_one_producer_per_place(g: AbstractGraph)[source]¶
The owned places, over every node, form an antichain (do not overlap).
o || m ∀ n_i ≠ n_j, n_i, n_j ∊ N: o ∊ O_i, m ∊ O_j
- Return type:
Iterator[Violation]
- owned_overlaps[N: Label, V: Place](owned: Iterable[tuple[N, V]])[source]¶
Every comparable pair of `(owner, place)`s, the later against each earlier one it meets, so each violation names its own two owners.
- Return type:
Iterator[Violation]
- owned_against[N: Label, V: Place](owned: Iterable[tuple[N, V]], owners: Mapping[V, N], below: set[V] | None = None)[source]¶
Every (owner, place) comparable to a place owners already holds; below is strictly_below(owners) when the caller keeps it.
- Return type:
Iterator[Violation]
- check_reads_are_exact(g: AbstractGraph)[source]¶
No read is strictly inside or around another node’s owned place: a read is exactly an owned place, or unrelated to every one.
o || p or o = p ∀ n_i, n_j ∊ N: o ∊ O_i, p ∊ I_j
- Return type:
Iterator[Violation]
- reads_exact_against[N: Label, V: Place](readers: Mapping[V, Sequence[N]], owners: Mapping[V, N], below: set[V] | None = None)[source]¶
check_reads_are_exact of readers against owners alone: a rebinding’s proof asks it of what is new, and reports the same kinds the rule does.
- Return type:
Iterator[Violation]
- class AbstractGraph[N: Label, V: Place](definitions: OrderedMap[N, NodeDefinition[V]])[source]¶
Bases:
Frozen,Generic[N,V]A graph of definitions, with the places they own and read. An edge is the fact that one node’s owns intersects another’s reads, so no edge can disagree with the nodes.
- definitions: OrderedMap[N, NodeDefinition[V]]¶
- checks: PerLevel[tuple[Callable[[Any], object], ...]] = (<function check_one_producer_per_place>, <function check_reads_are_exact>)¶
Callable [self] -> iterable of violations, which are raised at construction unless skipped (see unchecked).
- property owners: dict[V, N]¶
Which V is output (owned) by which N.
- property readers: dict[V, tuple[N, ...]]¶
Which V is read by which N (multiple)
- property owned_below: set[V]¶
what makes an edit’s lookup of its own places against the owners cost no scan of them.
- Type:
Every place with an owned extension
- property read_below: set[V]¶
The same, of the reads.
- property components: tuple[tuple[N, ...], ...]¶
The strongly connected components, in dependency order, members in the order bound (TOSCC). Of the components ready at once, the one bound first comes first, so a graph bound in dependency order comes back as bound.
- property nodes: tuple[N, ...]¶
Every node’s name, in binding order.
- property variables: tuple[V, ...]¶
owned by a node, or read from outside.
- Type:
Every variable the graph names
- property owned_variables: tuple[V, ...]¶
- property read_variables: tuple[V, ...]¶
- property boundary_inputs: tuple[V, ...]¶
- property boundary_outputs: tuple[V, ...]¶
Variables owned by a node but never read.
- property topological_order: tuple[N, ...]¶
The nodes in dependency order, raising if the graph has a cycle.
- property components_order: tuple[N, ...]¶
In run order; components are adjacent nodes
- property cycles: tuple[tuple[N, ...], ...]¶
A cycle iff the component is length larger than 1 (no self-loops)
- property is_acyclic: bool¶
- ancestors(of: Iterable[N])[source]¶
Every node of depends on (including itself)
- Return type:
tuple[N,...]
- descendants(of: Iterable[N])[source]¶
Every node depending on of (including itself)
- Return type:
tuple[N,...]
- reach(varying: Iterable[V])[source]¶
Every node depending on the variables varying (except the owner itself)
- Return type:
tuple[N,...]
- property feedback_variables: tuple[V, ...]¶
Which variables are read in the same SCC as their producer.
- closing_readers(var: V)[source]¶
The readers of var that close a cycle back onto its producer – the minimal set that has to stop reading the computed value for the cycle to break.
- Return type:
tuple[N,...]
- subgraph(keep: Iterable[N])[source]¶
Only the nodes in keep, with their definitions and the edges among them, in the parent’s binding order – so a subgraph of a set is one graph however the set was ordered. O(k log k) in what is kept, not O(V): a subgraph per component stays linear over all of them.
- Return type:
Self
- owners_of[N: Label, V: Place](definitions: Mapping[N, NodeDefinition[V]])[source]¶
Who owns each place. One producer per place is check_one_producer_per_place’s rule; assumed here.
- Return type:
dict[V,N]
- readers_of[N: Label, V: Place](definitions: Mapping[N, NodeDefinition[V]])[source]¶
Who reads each place, in the order given. fn(x, x) reads x once.
- Return type:
dict[V,tuple[N,...]]
- nx_dependencies[N: Label](definitions: Mapping[N, NodeDefinition])[source]¶
Networkx dependency graph
- Return type:
DiGraph
- class OwnedTwice(place: Place, node: Label, other: Label)[source]¶
Bases:
Violation- template: AbstractClassVar[str] = 'output {place!r} is owned by both {other!r} and {node!r}'¶
e.g. ‘output {place!r} is owned by both {other!r} and {node!r}’
- Type:
Wording
- class OwnInsideOwner(place: Place, witness: Place, node: Label, other: Label)[source]¶
Bases:
Violation- template: AbstractClassVar[str] = 'output {place!r} of {node!r} lies inside {witness!r}, owned by {other!r} -- two nodes would determine one place'¶
e.g. ‘output {place!r} is owned by both {other!r} and {node!r}’
- Type:
Wording
- class OwnAroundOwner(place: Place, witness: Place, node: Label, other: Label)[source]¶
Bases:
Violation- template: AbstractClassVar[str] = 'output {witness!r} of {other!r} lies inside {place!r}, owned by {node!r} -- two nodes would determine one place'¶
e.g. ‘output {place!r} is owned by both {other!r} and {node!r}’
- Type:
Wording
- class ReadInsideOwner(place: Place, witness: Place, readers: tuple[Label, ...], owner: Label)[source]¶
Bases:
Violation- template: AbstractClassVar[str] = '{readers} read {place!r}, which lies inside {witness!r}, owned by {owner!r} -- reads are matched by equality, so this would silently be a boundary input'¶
e.g. ‘output {place!r} is owned by both {other!r} and {node!r}’
- Type:
Wording
- class OwnerInsideRead(place: Place, witness: Place, readers: tuple[Label, ...], owner: Label)[source]¶
Bases:
Violation- template: AbstractClassVar[str] = 'output {witness!r} of {owner!r} lies inside {place!r}, read by {readers} -- that read would silently miss this output'¶
e.g. ‘output {place!r} is owned by both {other!r} and {node!r}’
- Type:
Wording