Struct DiGraph

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

A directed graph using reference-counted nodes.

Fields

nodes: IndexSet<Rc<N>>

The set of nodes in the graph.

edges: IndexMap<Rc<N>, IndexSet<Rc<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: GraphNode> DiGraph<N>

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

Initializes a new DiGraph from a set of source nodes.

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

Adds a node to the graph.

pub fn nodes(&self) -> impl Iterator<Item = &N>

Returns an iterator over the nodes in the graph.

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) -> impl Iterator<Item = &N>

Returns an iterator to the 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_with_filter<F>( &self, filter: 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 that satisfy the given filter.

Detects if there is a cycle in the graph.

pub fn retain_nodes(&mut self, keep: &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: &Rc<N>, discovered: &mut IndexSet<Rc<N>>, finished: &mut IndexSet<Rc<N>>, ) -> Option<Rc<N>>

fn get_or_insert(&mut self, node: N) -> Rc<N>

Helper: get or insert Rc into the graph.

Trait Implementations

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

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

Returns a duplicate of the value.

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

Performs copy-assignment from source.

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

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

Formats the value using the given formatter.

impl<N: GraphNode> Default for DiGraph<N>

fn default() -> Self

Returns the “default value” for a type.

impl<N: PartialEq + GraphNode> 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 + GraphNode> Eq for DiGraph<N>

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