Struct EventDag 

pub struct EventDag { /* private fields */ }

An in-memory DAG of events, indexed by content-addressed hash.

Provides O(1) insertion, O(1) node lookup, and efficient traversal in both causal directions (ancestors and descendants).

Implementations

impl EventDag

pub fn new() -> Self

Create an empty DAG.

pub fn insert(&mut self, event: Event)

Insert an event into the DAG.

• Registers the event as a node with its declared parents.
• Creates bidirectional parent→child links for any parents already in the DAG.
• If a later-inserted parent references this event, the link is created then.
• Duplicate events (same event_hash) are silently skipped.

Runs in O(P) where P is the number of parents for this event.

pub fn from_events(events: &[Event]) -> Self

Build a DAG from a slice of events.

Events are inserted in the order given. For replay from an event log, this is typically chronological order.

pub fn with_capacity(capacity: usize) -> Self

Create an empty DAG with pre-allocated capacity.

pub fn len(&self) -> usize

Number of events in the DAG.

pub fn is_empty(&self) -> bool

Returns true if the DAG has no events.

pub fn get(&self, hash: &str) -> Option<&DagNode>

Look up a node by its event hash.

pub fn get_event(&self, hash: &str) -> Option<&Event>

Return the event for a given hash.

pub fn contains(&self, hash: &str) -> bool

Returns true if the DAG contains an event with the given hash.

pub fn roots(&self) -> Vec<&str>

Return the hashes of all root events (events with no parents in the DAG).

Multiple roots occur when agents create items concurrently without seeing each other’s genesis events.

pub fn tips(&self) -> Vec<&str>

Return the hashes of all tip events (events with no children).

Tips are the “current heads” of the DAG — events that no other event has yet referenced as a parent.

pub fn ancestors(&self, hash: &str) -> HashSet<String>

Get all ancestor hashes of the given event (transitive parents).

Performs a BFS walk up the parent chain. Returns an empty set for root events. Does NOT include the starting event itself.

pub fn descendants(&self, hash: &str) -> HashSet<String>

Get all descendant hashes of the given event (transitive children).

Performs a BFS walk down the children chain. Returns an empty set for tip events. Does NOT include the starting event itself.

pub fn topological_order(&self) -> Vec<&Event>

Iterate events in topological (causal) order via Kahn’s algorithm.

Events with no unresolved parents come first. If multiple events are ready simultaneously, they are returned in hash-sorted order for determinism.

Multiple Roots

The algorithm handles multiple roots naturally — all root events start in the ready set.

pub fn is_ancestor(&self, a: &str, b: &str) -> bool

Check if event a is a causal ancestor of event b.

Returns true if there is a directed path from a to b in the DAG (i.e., a happened before b).

pub fn are_concurrent(&self, a: &str, b: &str) -> bool

Check if two events are concurrent (neither is an ancestor of the other).

pub fn hashes(&self) -> impl Iterator<Item = &str>

Return an iterator over all event hashes in the DAG.

pub fn nodes(&self) -> impl Iterator<Item = (&str, &DagNode)>

Return an iterator over all nodes in the DAG.

Trait Implementations

impl Clone for EventDag

fn clone(&self) -> EventDag

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for EventDag

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for EventDag

fn default() -> Self

Returns the “default value” for a type.