Trait Edge

Source

pub trait Edge:
    Sized
    + Ord
    + Hash {
    type Tag: Tag;

    // Required methods
    fn borrowed(&self) -> Borrowed<'_, Self>;
    fn with_tag(&self, tag: Self::Tag) -> Borrowed<'_, Self>;
    fn with_tag_owned(self, tag: Self::Tag) -> Self;
    fn tag(&self) -> Self::Tag;
    fn node_id(&self) -> NodeID;
}

Expand description

Edge in a decision diagram

Generally speaking, an edge is the directed connection between two nodes, with some kind of annotation. In a binary decision diagram with complement edges, there are the “true” edges as well as the normal and the complemented “false” edges. When considering a single edge, it usually is not so important whether this edge is a “true” or “false” edge; we can simply have distinguishable “slots” in the source node. In contrast, whether an edge is complemented or not has a much greater influence on the meaning of an edge.

In a decision diagram, obtaining the source of an edge is usually not so important, hence this trait does not provide such functionality. This means that an edge can (more or less) be implemented as a (tagged) pointer to the target node.

This trait requires implementors to also implement Ord. Edges should be considered equal if and only if they point to the same node with the same tag. Besides that, there are no further restrictions. The order implemented for Ord can be an arbitrary, fixed order (e.g. using addresses of the nodes). The main idea of this is to give the set {f, g} of two edges f and g a unique tuple/array representation.