Struct DiGraph

pub struct DiGraph<N: Node> {
    nodes: IndexSet<N>,
    edges: IndexMap<N, IndexSet<N>>,
}

A directed graph.

Fields

nodes: IndexSet<N>

The set of nodes in the graph.

edges: IndexMap<N, IndexSet<N>>

The directed edges in the graph. Each entry in the map is a node in the graph, and the set of nodes that it points to.

Implementations

impl<N: Node> DiGraph<N>

pub fn new(nodes: IndexSet<N>) -> Self

Initializes a new DiGraph from a vector of source nodes.

pub fn add_node(&mut self, node: N)

pub fn add_edge(&mut self, from: N, to: N)

Adds an edge to the graph.

pub fn remove_node(&mut self, node: &N) -> bool

Removes a node and all associated edges from the graph.

pub fn neighbors(&self, node: &N) -> Option<IndexSet<N>>

Returns the set of immediate neighbors of a given node.

pub fn contains_node(&self, node: N) -> bool

Returns true if the graph contains the given node.

pub fn post_order(&self) -> Result<IndexSet<N>, DiGraphError<N>>

Returns the post-order ordering of the graph. Detects if there is a cycle in the graph.

pub fn post_order_from_entry_points<F>( &self, is_entry_point: F, ) -> Result<IndexSet<N>, DiGraphError<N>>

where F: Fn(&N) -> bool,

Returns the post-order ordering of the graph but only considering a subset of the nodes as “entry points”. Meaning, nodes that are not accessible from the entry nodes are not considered in the post order.

Detects if there is a cycle in the graph.

pub fn retain_nodes(&mut self, nodes: &IndexSet<N>)

Retains a subset of the nodes, and removes all edges in which the source or destination is not in the subset.

fn contains_cycle_from( &self, node: N, discovered: &mut IndexSet<N>, finished: &mut IndexSet<N>, ) -> Option<N>

Trait Implementations

impl<N: Clone + Node> Clone for DiGraph<N>

fn clone(&self) -> DiGraph<N>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<N: Debug + Node> Debug for DiGraph<N>

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

Formats the value using the given formatter.

impl<N: Default + Node> Default for DiGraph<N>

fn default() -> DiGraph<N>

Returns the “default value” for a type.

impl<N: PartialEq + Node> PartialEq for DiGraph<N>

fn eq(&self, other: &DiGraph<N>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<N: Eq + Node> Eq for DiGraph<N>

impl<N: Node> StructuralPartialEq for DiGraph<N>