Module transitive_closure

Expand description

Module containing code to compute the transitive closure of a graph. This is a generic utility, and not specific to Cedar.

Structs§

HasCycle
Error raised when enforce_dag finds that the graph is not a DAG
MissingTcEdge
Error raised when TCComputation::EnforceAlreadyComputed finds that the TC was in fact not already computed

TcError
Error type for errors raised during transitive closure computation. This error type is parametrized by a type K which is the type of a unique identifier for graph nodes and the type returned by get_key on the TCNode trait.

TCNode
Trait used to generalize transitive closure computation. This trait should be implemented for types representing a node in the hierarchy (e.g., the entity hierarchy) where we need to compute the transitive closure of the hierarchy starting from only direct adjacencies. This trait is parametrized by a type K which represents a unique identifier for graph nodes.

compute_tc
Given Graph as a map from keys with type K to implementations of TCNode with type V, compute the transitive closure of the hierarchy. In case of error, the result contains an error structure Err<K> which contains the keys (with type K) for the nodes in the graph which caused the error. If enforce_dag then also check that the heirarchy is a DAG
enforce_tc_and_dag
Given a graph (as a map from keys to TCNode), enforce that all transitive edges are included, ie, the transitive closure has already been computed and that it is a DAG. If this is not the case, return an appropriate TCEnforcementError.