Skip to main content

would_cycle

memstead_base::graph::query

Function would_cycle 

Source 
pub fn would_cycle(
    store: &Store,
    from: &EntityId,
    to: &EntityId,
    rel_type: &str,
) -> Option<Vec<EntityId>>
Expand description

Would adding an edge from --rel_type--> to close a cycle in the subgraph restricted to edges of rel_type? Returns the back-path as [to, …, from] when a cycle exists, None otherwise.

A self-loop (from == to) is a length-1 cycle and is reported without a BFS. Otherwise this walks forward from to along outgoing edges whose rel_type matches, looking for from. Cost is O(edges of that rel_type) in the worst case.