Struct petgraph::stable_graph::StableGraph

pub struct StableGraph<N, E, Ty = Directed, Ix = DefaultIx> { /* fields omitted */ }

StableGraph<N, E, Ty, Ix> is a graph datastructure using an adjacency list representation.

The graph does not invalidate any unrelated node or edge indices when items are removed.

StableGraph is parameterized over:

• Associated data N for nodes and E for edges, also called weights. The associated data can be of arbitrary type.
• Edge type Ty that determines whether the graph edges are directed or undirected.
• Index type Ix, which determines the maximum size of the graph.

The graph uses O(|V| + |E|) space, and allows fast node and edge insert and efficient graph search.

It implements O(e') edge lookup and edge and node removals, where e' is some local measure of edge count.

• Nodes and edges are each numbered in an interval from 0 to some number m, but not all indices in the range are valid, since gaps are formed by deletions.

• You can select graph index integer type after the size of the graph. A smaller size may have better performance.

• Using indices allows mutation while traversing the graph, see Dfs.

• The StableGraph is a regular rust collection and is Send and Sync (as long as associated data N and E are).

• Indices don't allow as much compile time checking as references.

Depends on crate feature stable_graph (default). This is a new feature in petgraph. You can contribute to help it achieve parity with Graph.

Methods

impl<N, E> StableGraph<N, E, Directed>

fn new() -> Self

Create a new StableGraph with directed edges.

This is a convenience method. See StableGraph::with_capacity or StableGraph::default for a constructor that is generic in all the type parameters of StableGraph.

impl<N, E, Ty, Ix> StableGraph<N, E, Ty, Ix> where
    Ty: EdgeType,
    Ix: IndexType, 

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

Create a new StableGraph with estimated capacity.

fn capacity(&self) -> (usize, usize)

Return the current node and edge capacity of the graph.

fn clear(&mut self)

Remove all nodes and edges

fn node_count(&self) -> usize

Return the number of nodes (vertices) in the graph.

Computes in O(1) time.

fn edge_count(&self) -> usize

Return the number of edges in the graph.

Computes in O(1) time.

fn is_directed(&self) -> bool

Whether the graph has directed edges or not.

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

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

Computes in O(1) time.

Return the index of the new node.

Panics if the Graph is at the maximum number of nodes for its index type.

fn remove_node(&mut self, a: NodeIndex<Ix>) -> Option<N>

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

The node index a is invalidated, but none other. 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.

fn contains_node(&self, a: NodeIndex<Ix>) -> bool

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

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

Return the index of the new edge.

Computes in O(1) time.

Panics if any of the nodes don't exist.
Panics if the Graph is at the maximum number of edges for its index type.

Note: StableGraph allows adding parallel (“duplicate”) edges.

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

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

Return 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 if any of the nodes don't exist.

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

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

Invalidates the edge index e but no other.

Computes in O(e') time, where e' is the number of edges conneced to the same endpoints as e.

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

Access the weight for node a.

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

fn node_weight_mut(&mut self, a: NodeIndex<Ix>) -> Option<&mut N>

Access the weight for node a, mutably.

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

fn node_indices(&self) -> NodeIndices<N, Ix>

Return an iterator over the node indices of the graph

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

Access the weight for edge e.

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

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

Access the weight for edge e, mutably

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

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

Access the source and target nodes for e.

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

Lookup 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).

fn neighbors(&self, a: NodeIndex<Ix>) -> Neighbors<E, Ix>

Return an iterator of all nodes with an edge starting from a.

• Directed: Outgoing edges from a.
• Undirected: All edges connected to a.

Produces an empty iterator if the node doesn't exist.
Iterator element type is NodeIndex<Ix>.

Use .neighbors(a).detach() to get a neighbor walker that does not borrow from the graph.

fn neighbors_directed(
    &self,
    a: NodeIndex<Ix>,
    dir: Direction
) -> Neighbors<E, Ix>

Return an iterator of all neighbors that have an edge between them and a, in the specified direction. If the graph's edges are undirected, this is equivalent to .neighbors(a).

• Directed, Outgoing: All edges from a.
• Directed, Incoming: All edges to a.
• Undirected: All edges connected to a.

Produces an empty iterator if the node doesn't exist.
Iterator element type is NodeIndex<Ix>.

Use .neighbors_directed(a, dir).detach() to get a neighbor walker that does not borrow from the graph.

fn neighbors_undirected(&self, a: NodeIndex<Ix>) -> Neighbors<E, Ix>

Return an iterator of all neighbors that have an edge between them and a, in either direction. If the graph's edges are undirected, this is equivalent to .neighbors(a).

• Directed and Undirected: All edges connected to a.

Produces an empty iterator if the node doesn't exist.
Iterator element type is NodeIndex<Ix>.

Use .neighbors_undirected(a).detach() to get a neighbor walker that does not borrow from the graph.

fn edges(&self, a: NodeIndex<Ix>) -> Edges<E, Ty, Ix>

Return an iterator of all edges of a.

• Directed: Outgoing edges from a.
• Undirected: All edges connected to a.

Produces an empty iterator if the node doesn't exist.
Iterator element type is EdgeReference<E, Ix>.

fn edges_directed(&self, a: NodeIndex<Ix>, dir: Direction) -> Edges<E, Ty, Ix>

Return an iterator of all edges of a, in the specified direction.

• Directed, Outgoing: All edges from a.
• Directed, Incoming: All edges to a.
• Undirected: All edges connected to a.

Produces an empty iterator if the node a doesn't exist.
Iterator element type is EdgeReference<E, Ix>.

fn index_twice_mut<T, U>(
    &mut self,
    i: T,
    j: U
) -> (&mut Self::Output, &mut Self::Output) where
    Self: IndexMut<T> + IndexMut<U>,
    T: GraphIndex,
    U: GraphIndex, 

Index the Graph by two indices, any combination of node or edge indices is fine.

Panics if the indices are equal or if they are out of bounds.

fn retain_nodes<F>(&mut self, visit: F) where
    F: FnMut(Frozen<Self>, NodeIndex<Ix>) -> 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.

The node indices of the removed nodes are invalidated, but none other. Edge indices are invalidated as they would be following the removal of each edge with an endpoint in a removed node.

Computes in O(n + e') time, where n is the number of node indices and 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 removed node.

fn from_edges<I>(iterable: I) -> Self where
    I: IntoIterator,
    I::Item: IntoWeightedEdge<E>,
    <I::Item as IntoWeightedEdge<E>>::NodeId: Into<NodeIndex<Ix>>,
    N: Default, 

Create a new StableGraph from an iterable of edges.

Node weights N are set to default values. Edge weights E may either be specified in the list, or they are filled with default values.

Nodes are inserted automatically to match the edges.

use petgraph::stable_graph::StableGraph;

let gr = StableGraph::<(), i32>::from_edges(&[
    (0, 1), (0, 2), (0, 3),
    (1, 2), (1, 3),
    (2, 3),
]);

fn extend_with_edges<I>(&mut self, iterable: I) where
    I: IntoIterator,
    I::Item: IntoWeightedEdge<E>,
    <I::Item as IntoWeightedEdge<E>>::NodeId: Into<NodeIndex<Ix>>,
    N: Default, 

Extend the graph from an iterable of edges.

Node weights N are set to default values. Edge weights E may either be specified in the list, or they are filled with default values.

Nodes are inserted automatically to match the edges.

Trait Implementations

impl<'a, N, E: 'a, Ty, Ix> IntoNeighbors for &'a StableGraph<N, E, Ty, Ix> where
    Ty: EdgeType,
    Ix: IndexType, 

type Neighbors = Neighbors<'a, E, Ix>

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

Return an iterator of the neighbors of node a.

impl<'a, N, E: 'a, Ty, Ix> IntoNeighborsDirected for &'a StableGraph<N, E, Ty, Ix> where
    Ty: EdgeType,
    Ix: IndexType, 

type NeighborsDirected = Neighbors<'a, E, Ix>

fn neighbors_directed(
    self,
    n: NodeIndex<Ix>,
    d: Direction
) -> Self::NeighborsDirected

impl<'a, N, E: 'a, Ty, Ix> IntoNodeIdentifiers for &'a StableGraph<N, E, Ty, Ix> where
    Ty: EdgeType,
    Ix: IndexType, 

type NodeIdentifiers = NodeIndices<'a, N, Ix>

fn node_identifiers(self) -> Self::NodeIdentifiers

impl<N, E, Ty, Ix> NodeCount for StableGraph<N, E, Ty, Ix> where
    Ty: EdgeType,
    Ix: IndexType, 

fn node_count(&self) -> usize

impl<N, E, Ty, Ix> GraphProp for StableGraph<N, E, Ty, Ix> where
    Ty: EdgeType,
    Ix: IndexType, 

type EdgeType = Ty

The kind edges in the graph.

fn is_directed(&self) -> bool

impl<N, E, Ty, Ix> GraphBase for StableGraph<N, E, Ty, Ix> where
    Ix: IndexType, 

type NodeId = NodeIndex<Ix>

node identifier

type EdgeId = EdgeIndex<Ix>

edge identifier

impl<N, E, Ty, Ix> Visitable for StableGraph<N, E, Ty, Ix> where
    Ty: EdgeType,
    Ix: IndexType, 

type Map = FixedBitSet

The associated map type

fn visit_map(&self) -> FixedBitSet

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<N, E, Ty, Ix> Data for StableGraph<N, E, Ty, Ix> where
    Ty: EdgeType,
    Ix: IndexType, 

type NodeWeight = N

type EdgeWeight = E

impl<N, E, Ty, Ix> DataMap for StableGraph<N, E, Ty, Ix> where
    Ty: EdgeType,
    Ix: IndexType, 

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

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

impl<N, E, Ty, Ix> DataMapMut for StableGraph<N, E, Ty, Ix> where
    Ty: EdgeType,
    Ix: IndexType, 

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<N, E, Ty, Ix> Build for StableGraph<N, E, Ty, Ix> where
    Ty: EdgeType,
    Ix: 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<N, E, Ty, Ix> Create for StableGraph<N, E, Ty, Ix> where
    Ty: EdgeType,
    Ix: IndexType, 

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

impl<N, E, Ty, Ix> FromElements for StableGraph<N, E, Ty, Ix> where
    Ty: EdgeType,
    Ix: IndexType, 

fn from_elements<I>(iterable: I) -> Self where
    Self: Sized,
    I: IntoIterator<Item = Element<Self::NodeWeight, Self::EdgeWeight>>, 

impl<N, E, Ty, Ix> Debug for StableGraph<N, E, Ty, Ix> where
    N: Debug,
    E: Debug,
    Ty: EdgeType,
    Ix: IndexType, 

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

Formats the value using the given formatter.

impl<N, E, Ty, Ix: IndexType> Clone for StableGraph<N, E, Ty, Ix> where
    N: Clone,
    E: Clone, 

The resulting cloned graph has the same graph indices as self.

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<N, E, Ty, Ix> Index<NodeIndex<Ix>> for StableGraph<N, E, Ty, Ix> where
    Ty: EdgeType,
    Ix: IndexType, 

Index the StableGraph by NodeIndex to access node weights.

Panics if the node doesn't exist.

type Output = N

The returned type after indexing

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

The method for the indexing (container[index]) operation

impl<N, E, Ty, Ix> IndexMut<NodeIndex<Ix>> for StableGraph<N, E, Ty, Ix> where
    Ty: EdgeType,
    Ix: IndexType, 

Index the StableGraph by NodeIndex to access node weights.

Panics if the node doesn't exist.

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

The method for the mutable indexing (container[index]) operation

impl<N, E, Ty, Ix> Index<EdgeIndex<Ix>> for StableGraph<N, E, Ty, Ix> where
    Ty: EdgeType,
    Ix: IndexType, 

Index the StableGraph by EdgeIndex to access edge weights.

Panics if the edge doesn't exist.

type Output = E

The returned type after indexing

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

The method for the indexing (container[index]) operation

impl<N, E, Ty, Ix> IndexMut<EdgeIndex<Ix>> for StableGraph<N, E, Ty, Ix> where
    Ty: EdgeType,
    Ix: IndexType, 

Index the StableGraph by EdgeIndex to access edge weights.

Panics if the edge doesn't exist.

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

The method for the mutable indexing (container[index]) operation

impl<N, E, Ty, Ix> Default for StableGraph<N, E, Ty, Ix> where
    Ty: EdgeType,
    Ix: IndexType, 

Create a new empty StableGraph.

fn default() -> Self

Returns the "default value" for a type.

impl<'a, N, E, Ty, Ix> IntoEdges for &'a StableGraph<N, E, Ty, Ix> where
    Ty: EdgeType,
    Ix: IndexType, 

type Edges = Edges<'a, E, Ty, Ix>

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

impl<'a, N: 'a, E: 'a, Ty, Ix> IntoEdgeReferences for &'a StableGraph<N, E, Ty, Ix> where
    Ty: EdgeType,
    Ix: IndexType, 

type EdgeRef = EdgeReference<'a, E, Ix>

type EdgeReferences = EdgeReferences<'a, E, Ix>

fn edge_references(self) -> Self::EdgeReferences

Create an iterator over all edges in the graph, in indexed order.

Iterator element type is EdgeReference<E, Ix>.

impl<N, E, Ty, Ix> NodeIndexable for StableGraph<N, E, Ty, Ix> where
    Ty: EdgeType,
    Ix: IndexType, 

fn node_bound(&self) -> usize

Return an upper bound of the node indices in the graph

fn to_index(&self, ix: NodeIndex<Ix>) -> usize

Convert a to an integer index.

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

Convert i to a node index

impl<N, E, Ty, Ix> GetAdjacencyMatrix for StableGraph<N, E, Ty, Ix> where
    Ty: EdgeType,
    Ix: IndexType, 

The adjacency matrix for Graph is a bitmap that's computed by .adjacency_matrix().

type AdjMatrix = FixedBitSet

The associated adjacency matrix type

fn adjacency_matrix(&self) -> FixedBitSet

Create the adjacency matrix

fn is_adjacent(
    &self,
    matrix: &FixedBitSet,
    a: NodeIndex<Ix>,
    b: NodeIndex<Ix>
) -> bool

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