Struct Acyclic

pub struct Acyclic<G: Visitable> { /* private fields */ }

A directed acyclic graph.

Wrap directed acyclic graphs and expose an API that ensures the invariant is maintained, i.e. no cycles can be created. This uses a topological order that is dynamically updated when edges are added. In the worst case, the runtime may be linear in the number of vertices, but it has been shown to be fast in practice, particularly on sparse graphs (Pierce and Kelly, 2004).

To be modifiable (and hence to be useful), the graphs of generic type G should implement the Build trait. Good candidates for G are thus crate::graph::DiGraph and [crate::stable_graph::StableDiGraph].

Algorithm

This implements the PK algorithm for dynamic topological sort described in “A Dynamic Topological Sort Algorithm for Directed Acyclic Graphs” by D. Pierce and P. Kelly, JEA, 2004. It maintains a topological order of the nodes that can be efficiently updated when edges are added. Achieves a good balance between simplicity and performance in practice, see the paper for discussions of the running time.

Graph traits

All graph traits are delegated to the inner graph, with the exception of the graph construction trait Build. The wrapped graph can thus only be modified through the wrapped API that ensures no cycles are created.

Behaviour on cycles

By design, edge additions to this datatype may fail. It is recommended to prefer the dedicated Acyclic::try_add_edge and Acyclic::try_update_edge methods whenever possible. The Build::update_edge methods will panic if it is attempted to add an edge that would create a cycle. The Build::add_edge on the other hand method will return None if the edge cannot be added (either it already exists on a graph type that does not support it or would create a cycle).

Implementations

impl<G: Visitable> Acyclic<G>

pub fn get_position<'a>(&'a self, id: G::NodeId) -> TopologicalPosition

where &'a G: NodeIndexable + GraphBase<NodeId = G::NodeId>,

Get the position of a node in the topological sort.

Panics if the node index is out of bounds.

pub fn at_position(&self, pos: TopologicalPosition) -> Option<G::NodeId>

Get the node at a given position in the topological sort, if it exists.

impl<G: Visitable> Acyclic<G>

pub fn new() -> Self

where G: Default,

Create a new empty acyclic graph.

pub fn nodes_iter(&self) -> impl Iterator<Item = G::NodeId> + '_

Get an iterator over the nodes, ordered by their position.

pub fn range<'r>( &'r self, range: impl RangeBounds<TopologicalPosition> + 'r, ) -> impl Iterator<Item = G::NodeId> + 'r

Get an iterator over the nodes within the range of positions.

The nodes are ordered by their position in the topological sort.

pub fn inner(&self) -> &G

Get the underlying graph.

pub fn into_inner(self) -> G

Consume the Acyclic wrapper and return the underlying graph.

impl<G: Visitable + NodeIndexable> Acyclic<G>

where for<'a> &'a G: IntoNeighborsDirected + IntoNodeIdentifiers + GraphBase<NodeId = G::NodeId>,

pub fn try_from_graph(graph: G) -> Result<Self, Cycle<G::NodeId>>

Wrap a graph into an acyclic graph.

The graph types DiGraph and [StableDiGraph] also implement TryFrom, which can be used instead of this method and have looser type bounds.

pub fn try_add_edge( &mut self, a: G::NodeId, b: G::NodeId, weight: G::EdgeWeight, ) -> Result<G::EdgeId, AcyclicEdgeError<G::NodeId>>

where G: Build, G::NodeId: IndexType,

Add an edge to the graph using Build::add_edge.

Returns the id of the added edge, or an AcyclicEdgeError if the edge would create a cycle, a self-loop or if the edge addition failed in the underlying graph.

In cases where edge addition cannot fail in the underlying graph (e.g. when multi-edges are allowed, as in DiGraph and [StableDiGraph]), this will return an error if and only if Self::is_valid_edge returns false.

pub fn try_update_edge( &mut self, a: G::NodeId, b: G::NodeId, weight: G::EdgeWeight, ) -> Result<G::EdgeId, AcyclicEdgeError<G::NodeId>>

where G: Build, G::NodeId: IndexType,

Update an edge in a graph using Build::update_edge.

Returns the id of the updated edge, or an AcyclicEdgeError if the edge would create a cycle or a self-loop. If the edge does not exist, the edge is created.

This will return an error if and only if Self::is_valid_edge returns false.

pub fn is_valid_edge(&self, a: G::NodeId, b: G::NodeId) -> bool

where G::NodeId: IndexType,

Check if an edge would be valid, i.e. adding it would not create a cycle.

impl<N, E, Ix: IndexType> Acyclic<DiGraph<N, E, Ix>>

pub fn remove_edge( &mut self, e: <DiGraph<N, E, Ix> as GraphBase>::EdgeId, ) -> Option<E>

Remove an edge and return its edge weight, or None if it didn’t exist.

Pass through to underlying graph.

pub fn remove_node( &mut self, n: <DiGraph<N, E, Ix> as GraphBase>::NodeId, ) -> Option<N>

Remove a node from the graph if it exists, and return its weight. If it doesn’t exist in the graph, return None.

This updates the order in O(v) runtime and removes the node in the underlying graph.

Trait Implementations

impl<G: Build + Visitable + NodeIndexable> Build for Acyclic<G>

where for<'a> &'a G: IntoNeighborsDirected + IntoNodeIdentifiers + Visitable<Map = G::Map> + GraphBase<NodeId = G::NodeId>, G::NodeId: IndexType,

fn add_node(&mut self, weight: Self::NodeWeight) -> Self::NodeId

fn add_edge( &mut self, a: Self::NodeId, b: Self::NodeId, weight: Self::EdgeWeight, ) -> Option<Self::EdgeId>

Add a new edge. If parallel edges (duplicate) are not allowed and the edge already exists, return None.

fn update_edge( &mut self, a: Self::NodeId, b: Self::NodeId, weight: Self::EdgeWeight, ) -> Self::EdgeId

Add or update the edge from a to b. Return the id of the affected edge.

impl<G: Clone + Visitable> Clone for Acyclic<G>

where G::NodeId: Clone,

fn clone(&self) -> Acyclic<G>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<G: Create + Visitable + NodeIndexable> Create for Acyclic<G>

where for<'a> &'a G: IntoNeighborsDirected + IntoNodeIdentifiers + Visitable<Map = G::Map> + GraphBase<NodeId = G::NodeId>, G::NodeId: IndexType,

fn with_capacity(nodes: usize, edges: usize) -> Self

impl<G: Visitable + Data> Data for Acyclic<G>

type NodeWeight = <G as Data>::NodeWeight

type EdgeWeight = <G as Data>::EdgeWeight

impl<G: Visitable + DataMap> DataMap for Acyclic<G>

fn node_weight(&self, id: Self::NodeId) -> Option<&Self::NodeWeight>

fn edge_weight(&self, id: Self::EdgeId) -> Option<&Self::EdgeWeight>

impl<G: Visitable + DataMapMut> DataMapMut for Acyclic<G>

fn node_weight_mut(&mut self, id: Self::NodeId) -> Option<&mut Self::NodeWeight>

fn edge_weight_mut(&mut self, id: Self::EdgeId) -> Option<&mut Self::EdgeWeight>

impl<G: Debug + Visitable> Debug for Acyclic<G>

where G::NodeId: Debug,

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

Formats the value using the given formatter.

impl<G: Default + Visitable> Default for Acyclic<G>

fn default() -> Self

Returns the “default value” for a type.

impl<G: Visitable> Deref for Acyclic<G>

type Target = G

The resulting type after dereferencing.

fn deref(&self) -> &Self::Target

Dereferences the value.

impl<G: Visitable + EdgeCount> EdgeCount for Acyclic<G>

fn edge_count(&self) -> usize

Return the number of edges in the graph.

impl<G: Visitable + EdgeIndexable> EdgeIndexable for Acyclic<G>

fn edge_bound(&self) -> usize

Return an upper bound of the edge indices in the graph (suitable for the size of a bitmap).

fn to_index(&self, a: Self::EdgeId) -> usize

Convert a to an integer index.

fn from_index(&self, i: usize) -> Self::EdgeId

Convert i to an edge index. i must be a valid value in the graph.

impl<G: Visitable + GetAdjacencyMatrix> GetAdjacencyMatrix for Acyclic<G>

type AdjMatrix = <G as GetAdjacencyMatrix>::AdjMatrix

The associated adjacency matrix type

fn adjacency_matrix(&self) -> Self::AdjMatrix

Create the adjacency matrix

fn is_adjacent( &self, matrix: &Self::AdjMatrix, a: Self::NodeId, b: Self::NodeId, ) -> bool

Return true if there is an edge from a to b, false otherwise.

impl<G: Visitable> GraphBase for Acyclic<G>

type NodeId = <G as GraphBase>::NodeId

node identifier

type EdgeId = <G as GraphBase>::EdgeId

edge identifier

impl<G: Visitable + GraphProp> GraphProp for Acyclic<G>

type EdgeType = <G as GraphProp>::EdgeType

The kind of edges in the graph.

fn is_directed(&self) -> bool

impl<'a, N, E, Ix: IndexType> IntoEdgeReferences for &'a Acyclic<DiGraph<N, E, Ix>>

type EdgeRef = <&'a Graph<N, E, Directed, Ix> as IntoEdgeReferences>::EdgeRef

type EdgeReferences = <&'a Graph<N, E, Directed, Ix> as IntoEdgeReferences>::EdgeReferences

fn edge_references(self) -> Self::EdgeReferences

impl<'a, N, E, Ix: IndexType> IntoEdges for &'a Acyclic<DiGraph<N, E, Ix>>

type Edges = <&'a Graph<N, E, Directed, Ix> as IntoEdges>::Edges

fn edges(self, a: Self::NodeId) -> Self::Edges

impl<'a, N, E, Ix: IndexType> IntoEdgesDirected for &'a Acyclic<DiGraph<N, E, Ix>>

type EdgesDirected = <&'a Graph<N, E, Directed, Ix> as IntoEdgesDirected>::EdgesDirected

fn edges_directed(self, a: Self::NodeId, dir: Direction) -> Self::EdgesDirected

impl<'a, N, E, Ix: IndexType> IntoNeighbors for &'a Acyclic<DiGraph<N, E, Ix>>

type Neighbors = <&'a Graph<N, E, Directed, Ix> as IntoNeighbors>::Neighbors

fn neighbors(self, a: Self::NodeId) -> Self::Neighbors

Return an iterator of the neighbors of node a.

impl<'a, N, E, Ix: IndexType> IntoNeighborsDirected for &'a Acyclic<DiGraph<N, E, Ix>>

type NeighborsDirected = <&'a Graph<N, E, Directed, Ix> as IntoNeighborsDirected>::NeighborsDirected

fn neighbors_directed( self, n: Self::NodeId, d: Direction, ) -> Self::NeighborsDirected

impl<'a, N, E, Ix: IndexType> IntoNodeIdentifiers for &'a Acyclic<DiGraph<N, E, Ix>>

type NodeIdentifiers = <&'a Graph<N, E, Directed, Ix> as IntoNodeIdentifiers>::NodeIdentifiers

fn node_identifiers(self) -> Self::NodeIdentifiers

impl<'a, N, E, Ix: IndexType> IntoNodeReferences for &'a Acyclic<DiGraph<N, E, Ix>>

type NodeRef = <&'a Graph<N, E, Directed, Ix> as IntoNodeReferences>::NodeRef

type NodeReferences = <&'a Graph<N, E, Directed, Ix> as IntoNodeReferences>::NodeReferences

fn node_references(self) -> Self::NodeReferences

impl<G: Visitable + NodeCount> NodeCount for Acyclic<G>

fn node_count(&self) -> usize

impl<G: Visitable + NodeIndexable> NodeIndexable for Acyclic<G>

fn node_bound(&self) -> usize

Return an upper bound of the node indices in the graph (suitable for the size of a bitmap).

fn to_index(&self, a: Self::NodeId) -> usize

Convert a to an integer index.

fn from_index(&self, i: usize) -> Self::NodeId

Convert i to a node index. i must be a valid value in the graph.

impl<N, E, Ix: IndexType> TryFrom<Graph<N, E, Directed, Ix>> for Acyclic<DiGraph<N, E, Ix>>

type Error = Cycle<NodeIndex<Ix>>

The type returned in the event of a conversion error.

fn try_from(graph: DiGraph<N, E, Ix>) -> Result<Self, Self::Error>

Performs the conversion.

impl<G: Visitable> Visitable for Acyclic<G>

type Map = <G as Visitable>::Map

The associated map type

fn visit_map(&self) -> Self::Map

Create a new visitor map

fn reset_map(&self, map: &mut Self::Map)

Reset the visitor map (and resize to new size of graph if needed)

impl<G: Visitable + NodeCompactIndexable> NodeCompactIndexable for Acyclic<G>