Struct petgraph::graph::Graph

pub struct Graph<N, E, Ty = Directed, Ix: IndexType = DefIndex> {
    // some fields omitted
}

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

Graph 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.

Based on the graph datastructure used in rustc.

Graph Indices

The graph maintains unique indices for nodes and edges, and node and edge weights may be accessed mutably.

NodeIndex and EdgeIndex are types that act as references to nodes and edges, but these are only stable across certain operations. Adding nodes or edges keeps indices stable. Removing nodes or edges may shift other indices. Removing a node will force the last node to shift its index to take its place. Similarly, removing an edge shifts the index of the last edge.

The Ix parameter is u32 by default. The goal is that you can ignore this parameter completely unless you need a very big graph -- then you can use usize.

Tradeoffs With Indices

• The fact that the node and edge indices in the graph each are numbered in compact intervals (from 0 to n - 1 for n nodes) simplifies some graph algorithms.

• 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.

• You can create several graphs using the equal node indices but with differing weights or differing edges.

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

• Some indices shift during node or edge removal, so that is a drawback of removing elements. Indices don't allow as much compile time checking as references.

Methods

impl<N, E> Graph<N, E, Directed>

fn new() -> Self

Create a new Graph with directed edges.

impl<N, E> Graph<N, E, Undirected>

fn new_undirected() -> Self

Create a new Graph with undirected edges.

impl<N, E, Ty = Directed, Ix = DefIndex> Graph<N, E, Ty, Ix> where Ty: EdgeType, Ix: IndexType

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

Create a new Graph with estimated capacity.

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, w: N) -> NodeIndex<Ix>

Add a node (also called vertex) with weight w 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 node_weight(&self, a: NodeIndex<Ix>) -> Option<&N>

Access node weight for node a.

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

Access node weight for node a.

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 edge weight.

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

Computes in O(1) time.

Return the index of the new edge.

Panics if any of the nodes don't exist.

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

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.

Computes in O(e') time, where e' is the number of edges connected to the vertices a (and b).

Return the index of the affected edge.

Panics if any of the nodes don't exist.

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

Access the edge weight for e.

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

Access the edge weight for e mutably.

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

Access the source and target nodes for e.

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.

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.

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.

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.

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

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

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

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

Iterator element type is NodeIndex<Ix>.

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

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

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

Iterator element type is NodeIndex<Ix>.

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 is undirected, this is equivalent to .neighbors(a).

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

Iterator element type is NodeIndex<Ix>.

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

Return an iterator over the neighbors of node a, paired with their respective edge weights.

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

Iterator element type is (NodeIndex<Ix>, &E).

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

Return an iterator of all neighbors that have an edge between them and a, in the specified direction, paired with the respective edge weights.

If the graph is undirected, this is equivalent to .edges(a).

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

Iterator element type is (NodeIndex<Ix>, &E).

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

Return an iterator over the edgs from a to its neighbors, then to a from its neighbors.

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

Iterator element type is (NodeIndex<Ix>, &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 the vertices a (and b).

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

Lookup an edge between a and b, in either direction.

If the graph is undirected, then this is equivalent to .find_edge().

Return the edge index and its directionality, with Outgoing meaning from a to b and Incoming the reverse, or None if the edge does not exist.

fn without_edges(&self, dir: EdgeDirection) -> WithoutEdges<N, Ty, Ix>

Return an iterator over either the nodes without edges to them or from them.

The nodes in .without_edges(Incoming) are the source nodes and .without_edges(Outgoing) are the sinks.

For an undirected graph, the sinks/sources are just the vertices without edges.

The whole iteration computes in O(|V|) time.

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

Return an iterator over the node indices of the graph

fn node_weights_mut(&mut self) -> NodeWeightsMut<N, Ix>

Return an iterator yielding mutable access to all node weights.

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

fn edge_indices(&self) -> EdgeIndices<Ix>

Return an iterator over the edge indices of the graph

fn edge_weights_mut(&mut self) -> EdgeWeightsMut<E, Ix>

Return an iterator yielding mutable access to all edge weights.

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

fn raw_nodes(&self) -> &[Node<N, Ix>]

Access the internal node array.

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

Access the internal edge array.

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

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

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

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

fn walk_edges_directed(&self, a: NodeIndex<Ix>, dir: EdgeDirection) -> WalkEdges<Ix>

Return a “walker” object that can be used to step through the edges of the node a in direction dir.

Note: The walker does not borrow from the graph, this is to allow mixing edge walking with mutating the graph's weights.

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.

use petgraph::{Graph, Dfs, Incoming};

let mut gr = Graph::new();
let a = gr.add_node(0.);
let b = gr.add_node(0.);
let c = gr.add_node(0.);
gr.add_edge(a, b, 3.);
gr.add_edge(b, c, 2.);
gr.add_edge(c, b, 1.);

// walk the graph and sum incoming edges into the node weight
let mut dfs = Dfs::new(&gr, a);
while let Some(node) = dfs.next(&gr) {
    let mut edges = gr.walk_edges_directed(node, Incoming);
    while let Some(edge) = edges.next(&gr) {
        let (nw, ew) = gr.index_twice_mut(node, edge);
        *nw += *ew;
    }
}

// check the result
assert_eq!(gr[a], 0.);
assert_eq!(gr[b], 4.);
assert_eq!(gr[c], 2.);

fn reverse(&mut self)

Reverse the direction of all edges

fn clear(&mut self)

Remove all nodes and edges

fn clear_edges(&mut self)

Remove all edges

fn retain_nodes<F>(&mut self, visit: F) where F: FnMut(&mut Self, NodeIndex<Ix>) -> bool

Remove all nodes that return false from the visit closure.

visit provides a mutable reference to the graph, so that the graph can be walked and associated data modified. You should not add or remove nodes.

The order nodes are visited is not specified.

fn retain_edges<F>(&mut self, visit: F) where F: FnMut(&mut Self, EdgeIndex<Ix>) -> bool

Remove all edges that return false from the visit closure.

visit provides a mutable reference to the graph, so that the graph can be walked and associated data modified. You should not add or remove nodes or edges.

The order edges are visited is not specified.

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

Create a new 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.

use petgraph::Graph;

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

fn extend_with_edges<I, J>(&mut self, iterable: I) where I: IntoIterator, I::Item: IntoWeightedEdge<J, E>, J: 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.

fn map<'a, F, G, N2, E2>(&'a self, node_map: F, edge_map: G) -> Graph<N2, E2, Ty, Ix> where F: FnMut(NodeIndex<Ix>, &'a N) -> N2, G: FnMut(EdgeIndex<Ix>, &'a E) -> E2

Create a new Graph by mapping node and edge weights.

The resulting graph has the same graph indices as self.

fn filter_map<'a, F, G, N2, E2>(&'a self, node_map: F, edge_map: G) -> Graph<N2, E2, Ty, Ix> where F: FnMut(NodeIndex<Ix>, &'a N) -> Option<N2>, G: FnMut(EdgeIndex<Ix>, &'a E) -> Option<E2>

Create a new Graph by mapping nodes and edges. A node or edge may be mapped to None to exclude it from the resulting graph.

Nodes are mapped first with the node_map closure, then edge_map is called for the edges that have not had any endpoint removed.

If no nodes are removed, the resulting graph has compatible node indices; if neither nodes nor edges are removed, the result has the same graph indices as self.

fn into_edge_type<NewTy>(self) -> Graph<N, E, NewTy, Ix> where NewTy: EdgeType

Convert the graph into either undirected or directed. No edge adjustments are done, so you may want to go over the result to remove or add edges.

Computes in O(1) time.

Trait Implementations

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

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<N, E, Ty, Ix> Debug for Graph<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> Index<NodeIndex<Ix>> for Graph<N, E, Ty, Ix> where Ty: EdgeType, Ix: IndexType

Index the Graph 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 (Foo[Bar]) operation

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

Index the Graph 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 indexing (Foo[Bar]) operation

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

Index the Graph 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 (Foo[Bar]) operation

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

Index the Graph 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 indexing (Foo[Bar]) operation

impl<'a, N, E: 'a, Ty, Ix> NeighborIter<'a> for Graph<N, E, Ty, Ix> where Ty: EdgeType, Ix: IndexType

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

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

Return an iterator that visits all neighbors of the node n.

impl<'a, N, E: 'a, Ty, Ix> NeighborsDirected<'a> for Graph<N, E, Ty, Ix> where Ty: EdgeType, Ix: IndexType

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

fn neighbors_directed(&'a self, n: NodeIndex<Ix>, d: EdgeDirection) -> Neighbors<'a, E, Ix>

Return an iterator that visits all neighbors of the node n.

impl<'a, N: 'a, E, Ty, Ix> Externals<'a> for Graph<N, E, Ty, Ix> where Ty: EdgeType, Ix: IndexType

type Externals = WithoutEdges<'a, N, Ty, Ix>

fn externals(&'a self, d: EdgeDirection) -> WithoutEdges<'a, N, Ty, Ix>

Return an iterator of all nodes with no edges in the given direction

impl<N, E, Ty, Ix> Graphlike for Graph<N, E, Ty, Ix> where Ix: IndexType

type NodeId = NodeIndex<Ix>

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

type Map = FixedBitSet

fn visit_map(&self) -> FixedBitSet

impl<N, E, Ty, Ix> Revisitable for Graph<N, E, Ty, Ix> where Ty: EdgeType, Ix: IndexType

fn reset_map(&self, map: &mut Self::Map)

impl<N, E, Ty, Ix> GetAdjacencyMatrix for Graph<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

fn adjacency_matrix(&self) -> FixedBitSet

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