Struct UnGraph

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

A graph with undirected edges.

For example, an edge between 1 and 2 is equivalent to an edge between 2 and 1.

Implementations

impl<N, E> UnGraph<N, E>

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

Creates a new UnGraph 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.

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(E),

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

Apart from a, this invalidates the last node index in the graph (that node will adopt the removed node index). 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.

Apart from e, this invalidates the last edge index in the graph (that edge will adopt the removed edge index).

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_mut(&mut self, a: NodeIndex) -> EdgesMut<'_, N, E>

Returns a mutable 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 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 node_indices(&self) -> impl DoubleEndedIterator<Item = NodeIndex>

Returns an iterator over the node indices of the graph.

pub fn edge_indices(&self) -> impl DoubleEndedIterator<Item = EdgeIndex>

Returns an iterator over the edge indices of the graph

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) -> EdgeWeightsMut<'_, N, E>

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

pub fn all_edge_weights(&self) -> AllEdgeWeights<'_, 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) -> AllEdgeWeightsMut<'_, 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_nodes(&self) -> &[Node<N>]

Accesses the internal node array.

pub fn raw_nodes_mut(&mut self) -> &mut [Node<N>]

Accesses the internal node array mutably.

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

Accesses the internal edge array.

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

Accesses the internal edge array mutably.

pub fn first_edge(&self, a: NodeIndex, dir: EdgeDirection) -> Option<EdgeIndex>

Accessor for data structure internals: returns the first edge in the given direction.

pub fn next_edge(&self, e: EdgeIndex, dir: EdgeDirection) -> Option<EdgeIndex>

Accessor for data structure internals: returns the next edge for the given direction.

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.

pub fn reserve_nodes(&mut self, additional: usize)

Reserves capacity for at least additional more nodes to be inserted in the graph. Graph may reserve more space to avoid frequent reallocations.

Panics

Panics if the new capacity overflows usize.

pub fn reserve_edges(&mut self, additional: usize)

Reserves capacity for at least additional more edges to be inserted in the graph. Graph may reserve more space to avoid frequent reallocations.

Panics

Panics if the new capacity overflows usize.

pub fn retain_nodes<F>(&mut self, visit: F)

where F: FnMut(&Self, NodeIndex) -> bool,

Keep all nodes that return true from the visit closure, remove the others.

visit is provided a proxy reference to the graph, so that the graph can be walked and associated data modified.

The order nodes are visited is not specified.

pub fn retain_edges<F>(&mut self, visit: F)

where F: FnMut(&Self, EdgeIndex) -> bool,

Keep all edges that return true from the visit closure, remove the others.

visit is provided a proxy reference to the graph, so that the graph can be walked and associated data modified.

The order edges are visited is not specified.

Trait Implementations

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

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

Returns a copy of the value.

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

Performs copy-assignment from source.

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

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

Formats the value using the given formatter.

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

fn default() -> Self

Returns the “default value” for a type.

impl<N, E> Index<EdgeIndex> for UnGraph<N, E>

Indexes the UnGraph by EdgeIndex to access edge weights.

Panics

Panics if the edge doesn’t exist.

type Output = E

The returned type after indexing.

fn index(&self, index: EdgeIndex) -> &E

Performs the indexing (container[index]) operation.

impl<N, E> Index<NodeIndex> for UnGraph<N, E>

Indexes the UnGraph by NodeIndex to access node weights.

Panics

Panics if the node doesn’t exist.

type Output = N

The returned type after indexing.

fn index(&self, index: NodeIndex) -> &N

Performs the indexing (container[index]) operation.

impl<N, E> IndexMut<EdgeIndex> for UnGraph<N, E>

Indexes the UnGraph by EdgeIndex to access edge weights.

Panics

Panics if the edge doesn’t exist.

fn index_mut(&mut self, index: EdgeIndex) -> &mut E

Performs the mutable indexing (container[index]) operation.

impl<N, E> IndexMut<NodeIndex> for UnGraph<N, E>

Indexes the UnGraph by NodeIndex to access node weights.

Panics

Panics if the node doesn’t exist.

fn index_mut(&mut self, index: NodeIndex) -> &mut N

Performs the mutable indexing (container[index]) operation.