Struct StableUnGraph

pub struct StableUnGraph<N, E> { /* private fields */ }

A graph with undirected edges and stable indices.

Unlike UnGraph, this graph does not invalidate any unrelated node or edge indices when items are removed. Removed nodes and edges are replaced with vacant slots, which can be reused later in order of lowest index first.

Implementations

impl<N, E> StableUnGraph<N, E>

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

Creates a new StableUnGraph with estimated capacity.

pub fn node_count(&self) -> usize

Returns the number of nodes in the graph.

Computes in O(1) time.

pub fn edge_count(&self) -> usize

Returns the number of edges in the graph.

Computes in O(1) time.

pub fn add_node(&mut self, weight: N) -> NodeIndex

Adds a node (also called vertex) with associated data weight to the graph.

Computes in O(1) time.

Returns the index of the new node.

Panics

Panics if the graph is at the maximum number of nodes.

pub fn node_weight(&self, a: NodeIndex) -> Option<&N>

Accesses the weight for node a.

Also available with indexing syntax: &graph[a].

pub fn add_edge(&mut self, a: NodeIndex, b: NodeIndex, weight: E) -> EdgeIndex

Adds an edge from a to b to the graph, with its associated data weight.

Returns the index of the new edge.

Computes in O(1) time.

Note: UnGraph allows adding parallel (“duplicate”) edges. If you want to avoid this, use .update_edge(a, b, weight) instead.

Panics

Panics if any of the nodes don’t exist or the graph is at the maximum number of edges.

pub fn update_edge( &mut self, a: NodeIndex, b: NodeIndex, weight: E, ) -> EdgeIndex

Adds or updates an edge from a to b. If the edge already exists, its weight is updated.

Returns the index of the affected edge.

Computes in O(e’) time, where e’ is the number of edges connected to a (and b, if the graph edges are undirected).

Panics

Panics if any of the nodes doesn’t exist or the graph is at the maximum number of edges.

pub fn edge_weight(&self, e: EdgeIndex) -> Option<&E>

Accesses the weight for edge e.

Also available with indexing syntax: &graph[e].

pub fn edge_weight_mut(&mut self, e: EdgeIndex) -> Option<&mut E>

Accesses the weight for edge e mutably.

Also available with indexing syntax: &mut graph[e].

pub fn edge_endpoints(&self, e: EdgeIndex) -> Option<(NodeIndex, NodeIndex)>

Accesses the source and target nodes for e.

pub fn remove_node_with<F>( &mut self, a: NodeIndex, edge_callback: F, ) -> Option<N>

where F: FnMut(&mut Self, EdgeIndex),

Removes a from the graph if it exists, calling edge_callback for each of its edges right before removal, and returns its weight. If it doesn’t exist in the graph, returns None.

Invalidates the node index a, but not any other indices. Edge indices are invalidated as they would be following the removal of each edge with an endpoint in a.

Computes in O(e’) time, where e’ is the number of affected edges, including n calls to remove_edge, where n is the number of edges with an endpoint in a, and including the edges with an endpoint in the displaced node.

pub fn remove_edge(&mut self, e: EdgeIndex) -> Option<E>

Removes an edge and returns its edge weight, or None if it didn’t exist.

Invalidates the edge index e, but not any other indices.

Computes in O(e’) time, where e’ is the size of four particular edge lists, for the vertices of e and the vertices of another affected edge.

pub fn neighbors(&self, a: NodeIndex) -> Neighbors<'_, E>

Returns an iterator of all nodes with an edge connected to a.

Produces an empty iterator if the node doesn’t exist.

The iterator element type is NodeIndex.

pub fn edges(&self, a: NodeIndex) -> Edges<'_, E>

Returns an iterator of all edges connected to a.

Produces an empty iterator if the node doesn’t exist.

The iterator element type is EdgeReference<E>.

pub fn edges_between(&self, a: NodeIndex, b: NodeIndex) -> EdgesBetween<'_, E>

Returns an iterator over all edges between a and b.

The iterator element type is EdgeReference<E>.

pub fn contains_edge(&self, a: NodeIndex, b: NodeIndex) -> bool

Looks up if there is an edge from a to b.

Computes in O(e’) time, where e’ is the number of edges connected to a (and b, if the graph edges are undirected).

pub fn find_edge(&self, a: NodeIndex, b: NodeIndex) -> Option<EdgeIndex>

Looks up an edge from a to b.

Computes in O(e’) time, where e’ is the number of edges connected to a (and b, if the graph edges are undirected).

pub fn edge_weights(&self, a: NodeIndex) -> EdgeWeights<'_, E>

Returns an iterator yielding immutable access to edge weights for edges from or to a.

pub fn edge_weights_mut( &mut self, a: NodeIndex, ) -> FilterMap<EdgeWeightsMut<'_, Option<N>, Option<E>>, fn(&mut Option<E>) -> Option<&mut E>>

where N: Copy,

Returns an iterator yielding mutable access to edge weights for edges from or to a.

pub fn all_edge_weights(&self) -> impl Iterator<Item = &E>

Returns an iterator yielding immutable access to all edge weights.

The order in which weights are yielded matches the order of their edge indices.

pub fn all_edge_weights_mut(&mut self) -> impl Iterator<Item = &mut E>

Returns an iterator yielding mutable access to all edge weights.

The order in which weights are yielded matches the order of their edge indices.

pub fn raw_edges(&self) -> &[Edge<Option<E>>]

Accesses the internal edge array.

Note that this also includes vacant edges.

pub fn raw_edges_mut(&mut self) -> &mut [Edge<Option<E>>]

Accesses the internal edge array mutably.

Note that this also includes vacant edges.

pub fn clear(&mut self)

Removes all nodes and edges.

pub fn clear_edges(&mut self)

Removes all edges.

pub fn nodes_capacity(&self) -> usize

Returns the current node capacity of the graph.

pub fn edges_capacity(&self) -> usize

Returns the current edge capacity of the graph.

Trait Implementations

impl<N: Clone, E: Clone> Clone for StableUnGraph<N, E>

fn clone(&self) -> StableUnGraph<N, E>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<N: Debug, E: Debug> Debug for StableUnGraph<N, E>

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

Formats the value using the given formatter.

impl<N, E> Default for StableUnGraph<N, E>

fn default() -> Self

Returns the “default value” for a type.