# Struct petgraph::graph::Graph
[−]
[src]

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, 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,
efficient graph search and graph algorithms.
It implements **O(e')** edge lookup and edge and node removals, where **e'**
is some local measure of edge count.
Based on the graph datastructure used in rustc.

Here's an example of building a graph with directed edges, and below an illustration of how it could be rendered with graphviz (graphviz rendering is not a part of petgraph):

use petgraph::Graph; let mut deps = Graph::<&str, &str>::new(); let pg = deps.add_node("petgraph"); let fb = deps.add_node("fixedbitset"); let qc = deps.add_node("quickcheck"); let rand = deps.add_node("rand"); let libc = deps.add_node("libc"); deps.extend_with_edges(&[ (pg, fb), (pg, qc), (qc, rand), (rand, libc), (qc, libc), ]);

### Graph Indices

The graph maintains indices for nodes and edges, and node and edge
weights may be accessed mutably. Indices range in a compact interval, for
example for *n* nodes indices are 0 to *n* - 1 inclusive.

`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`

.

### Pros and Cons of 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`

, and`.neighbors(a).detach()`

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

[src]

`fn new() -> Self`

Create a new `Graph`

with directed edges.

This is a convenience method. Use `Graph::with_capacity`

or `Graph::default`

for
a constructor that is generic in all the type parameters of `Graph`

.

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

[src]

`fn new_undirected() -> Self`

Create a new `Graph`

with undirected edges.

This is a convenience method. Use `Graph::with_capacity`

or `Graph::default`

for
a constructor that is generic in all the type parameters of `Graph`

.

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

[src]

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

Create a new `Graph`

with estimated capacity.

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

Return the current node and edge capacity of the graph.

`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 (N/A if usize).

`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 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 (N/A if usize).

**Note:** `Graph`

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

instead.

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

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.

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

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

.

`Undirected`

: All edges from or to`a`

.`Directed`

: Outgoing edges from`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: 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's edges are undirected, this is equivalent to *.neighbors(a)*.

`Undirected`

: All edges from or to`a`

.`Directed`

,`Outgoing`

: All edges from`a`

.`Directed`

,`Incoming`

: All edges to`a`

.

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

Iterator element type is `NodeIndex<Ix>`

.

For a `Directed`

graph, neighbors are listed in reverse order of their
addition to the graph, so the most recently added edge's neighbor is
listed first. The order in an `Undirected`

graph is arbitrary.

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

`Undirected`

and`Directed`

: All edges from or 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, 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's edges are 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 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 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 externals(&self, dir: EdgeDirection) -> Externals<N, Ty, Ix>`

Return an iterator over either the nodes without edges to them
(`Incoming`

) or from them (`Outgoing`

).

An *internal* node has both incoming and outgoing edges.
The nodes in `.externals(Incoming)`

are the source nodes and
`.externals(Outgoing)`

are the sinks of the graph.

For a graph with undirected edges, both the sinks and the sources are just the nodes 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 into_nodes_edges(self) -> (Vec<Node<N, Ix>>, Vec<Edge<E, Ix>>)`

Convert the graph into a vector of Nodes and a vector of Edges

`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>`

**Deprecated:** Use `.neighbors_directed(a, dir).detach()`

instead.

Return a “walker” object that can be used to step through the directed
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.

`Directed`

,`Outgoing`

: All edges from`a`

.`Directed`

,`Incoming`

: All edges to`a`

.

`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) { // use a walker -- a detached neighbors iterator let mut edges = gr.neighbors_directed(node, Incoming).detach(); while let Some(edge) = edges.next_edge(&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`

Keep all nodes that return `true`

from the `visit`

closure,
remove the others.

`visit`

is provided 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`

Keep all edges that return `true`

from the `visit`

closure,
remove the others.

`visit`

is provided 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>(iterable: I) -> Self where I: IntoIterator, I::Item: IntoWeightedEdge<E>, I::Item::NodeId: 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>(&mut self, iterable: I) where I: IntoIterator, I::Item: IntoWeightedEdge<E>, I::Item::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.

`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 to new values.

The resulting graph has the same structure and 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.

The resulting graph has the structure of a subgraph of the original graph.
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`

[src]

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

.

`fn clone(&self) -> Self`

Returns a copy of the value. Read more

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

Performs copy-assignment from `source`

. Read more

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

[src]

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

[src]

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`

[src]

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`

[src]

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`

[src]

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<N, E, Ty, Ix> Default for Graph<N, E, Ty, Ix> where Ty: EdgeType, Ix: IndexType`

[src]

Create a new empty `Graph`

.

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

[src]

`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`

[src]

`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`

[src]

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

`fn externals(&'a self, d: EdgeDirection) -> Externals<'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`

[src]

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

[src]

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

[src]

`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`

[src]

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