Trait DiagramRules

pub trait DiagramRules<E: Edge, N: InnerNode<E>, T> {
    type Cofactors<'a>: Iterator<Item = Borrowed<'a, E>>
       where E: 'a,
             N: 'a;

    // Required methods
    fn reduce<M: Manager<Edge = E, InnerNode = N, Terminal = T>>(
        manager: &M,
        level: LevelNo,
        children: impl IntoIterator<Item = E>,
    ) -> ReducedOrNew<E, N>;
    fn cofactors(tag: E::Tag, node: &N) -> Self::Cofactors<'_>;

    // Provided method
    fn cofactor(tag: E::Tag, node: &N, n: usize) -> Borrowed<'_, E> { ... }
}

Reduction rules for decision diagrams

This trait is intended to be implemented on a zero-sized type. Refer to DiagramRules::reduce() for an example implementation.

Required Associated Types

type Cofactors<'a>: Iterator<Item = Borrowed<'a, E>> where E: 'a, N: 'a

Iterator created by DiagramRules::cofactors()

Required Methods

fn reduce<M: Manager<Edge = E, InnerNode = N, Terminal = T>>( manager: &M, level: LevelNo, children: impl IntoIterator<Item = E>, ) -> ReducedOrNew<E, N>

Apply the reduction rule(s)

Besides uniqueness of nodes (there are no two nodes with the same children at the same level), decision diagrams typically impose some other reduction rules. The former is provided by the Manager / LevelViews, the latter is implemented here.

The implementation is responsible for consuming the entire children iterator and dropping unused edges.

Example implementation

In binary decision diagrams (BDDs), there are no nodes with equal children. An implementation might look like this:

struct BDDRules;
impl<E: Edge, N: InnerNode<E>, T> DiagramRules<E, N, T> for BDDRules {
    type Cofactors<'a> = N::ChildrenIter<'a> where N: 'a, E: 'a;

    fn reduce<M: Manager<Edge = E, InnerNode = N, Terminal = T>>(
        manager: &M,
        level: LevelNo,
        children: impl IntoIterator<Item = E>,
    ) -> ReducedOrNew<E, N> {
        let mut it = children.into_iter();
        let f0 = it.next().unwrap();
        let f1 = it.next().unwrap();
        debug_assert!(it.next().is_none());

        if f0 == f1 {
            manager.drop_edge(f1);
            ReducedOrNew::Reduced(f0)
        } else {
            ReducedOrNew::New(InnerNode::new(level, [f0, f1]), Default::default())
        }
    }

    fn cofactors(_tag: E::Tag, node: &N) -> Self::Cofactors<'_> {
        node.children()
    }
}

Note that we assume no complemented edges, hence the cofactor iterator is just node.children().

The implementation assumes that there are no panics, otherwise it would leak some edges. It might be a bit better to use EdgeDropGuards, but this would make the code more clumsy, and our assumption is usually fair enough.

fn cofactors(tag: E::Tag, node: &N) -> Self::Cofactors<'_>

Get the cofactors of node assuming an incoming edge with tag

In some diagram types, this is the same as InnerNode::children(). However, in a binary decision diagram with complement edges, we need to respect the tag of the incoming edge: If the incoming edge is complemented, then we need to complement the outgoing edges as well.

Provided Methods

fn cofactor(tag: E::Tag, node: &N, n: usize) -> Borrowed<'_, E>

Get the n-th cofactor of node assuming an incoming edge with tag

This is equivalent to Self::cofactors(tag, node).nth(n).unwrap().

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors