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 the node weight N
, edge weight E
,
edge type Ty
that determines whether the graph has directed edges or not,
and Ix
which is the index type used.
Based on the graph implementation 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. Removing nodes or edges may shift
other indices. Adding to the graph keeps
all indices stable, but 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 are numbered in a compact interval from 0 to n - 1 simplifies some graph algorithms.
You can select graph index integer type after the size of the graph. A smaller size has better performance due to cache effects.
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 isSend + Sync
(as long asN
andE
are).
Methods
impl<N, E> Graph<N, E, Directed>
[src]
fn new() -> Self
Create a new Graph
with directed edges.
impl<N, E> Graph<N, E, Undirected>
[src]
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
[src]
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.
fn edge_count(&self) -> usize
Return the number of edges in the graph.
Computes in O(1) time.
fn clear(&mut self)
Remove all nodes and edges
fn is_directed(&self) -> bool
Return whether the graph has directed edges or not.
fn into_edge_type<NewTy>(self) -> Graph<N, E, NewTy, Ix> where NewTy: EdgeType
Cast the graph as either undirected or directed. No edge adjustments are done.
Computes in O(1) time.
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 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>, &'a 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>, &'a 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>, &'a E)
.
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 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
.
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.
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 reverse(&mut self)
Reverse the direction of all edges
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_weights_mut<'a>(&'a mut self) -> NodeWeightsMut<'a, 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_weights_mut<'a>(&'a mut self) -> EdgeWeightsMut<'a, 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.);
Trait Implementations
impl<N, E, Ty, Ix: IndexType> Clone for Graph<N, E, Ty, Ix> where N: Clone, E: Clone
[src]
fn clone(&self) -> Self
Returns a copy of the value. Read more
fn clone_from(&mut self, source: &Self)
1.0.0
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<'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 = 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
[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().