pub struct Graph<N, E, Ty = Directed, Ix = DefaultIx> { /* private fields */ }
Expand description
Graph<N, E, Ty, Ix>
is a graph datastructure using an adjacency list representation.
Graph
is parameterized over:
 Associated data
N
for nodes andE
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
is a regular Rust collection and is Send
and Sync
(as long
as associated data N
and E
are).
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 (see
Dot
):
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:
 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.
 Adding nodes or edges keeps indices stable.
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
.

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.

Indices don’t allow as much compile time checking as references.
Implementations§
source§impl<N, E> Graph<N, E, Undirected>
impl<N, E> Graph<N, E, Undirected>
sourcepub fn new_undirected() > Self
pub 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
.
source§impl<N, E, Ty, Ix> Graph<N, E, Ty, Ix>where
Ty: EdgeType,
Ix: IndexType,
impl<N, E, Ty, Ix> Graph<N, E, Ty, Ix>where Ty: EdgeType, Ix: IndexType,
sourcepub fn with_capacity(nodes: usize, edges: usize) > Self
pub fn with_capacity(nodes: usize, edges: usize) > Self
Create a new Graph
with estimated capacity.
sourcepub fn node_count(&self) > usize
pub fn node_count(&self) > usize
Return the number of nodes (vertices) in the graph.
Computes in O(1) time.
sourcepub fn edge_count(&self) > usize
pub fn edge_count(&self) > usize
Return the number of edges in the graph.
Computes in O(1) time.
sourcepub fn is_directed(&self) > bool
pub fn is_directed(&self) > bool
Whether the graph has directed edges or not.
sourcepub fn add_node(&mut self, weight: N) > NodeIndex<Ix>
pub 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).
sourcepub fn node_weight(&self, a: NodeIndex<Ix>) > Option<&N>
pub fn node_weight(&self, a: NodeIndex<Ix>) > Option<&N>
Access the weight for node a
.
If node a
doesn’t exist in the graph, return None
.
Also available with indexing syntax: &graph[a]
.
sourcepub fn node_weight_mut(&mut self, a: NodeIndex<Ix>) > Option<&mut N>
pub fn node_weight_mut(&mut self, a: NodeIndex<Ix>) > Option<&mut N>
Access the weight for node a
, mutably.
If node a
doesn’t exist in the graph, return None
.
Also available with indexing syntax: &mut graph[a]
.
sourcepub fn add_edge(
&mut self,
a: NodeIndex<Ix>,
b: NodeIndex<Ix>,
weight: E
) > EdgeIndex<Ix>
pub 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.
sourcepub fn update_edge(
&mut self,
a: NodeIndex<Ix>,
b: NodeIndex<Ix>,
weight: E
) > EdgeIndex<Ix>
pub 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 doesn’t exist.
sourcepub fn edge_weight(&self, e: EdgeIndex<Ix>) > Option<&E>
pub fn edge_weight(&self, e: EdgeIndex<Ix>) > Option<&E>
Access the weight for edge e
.
If edge e
doesn’t exist in the graph, return None
.
Also available with indexing syntax: &graph[e]
.
sourcepub fn edge_weight_mut(&mut self, e: EdgeIndex<Ix>) > Option<&mut E>
pub fn edge_weight_mut(&mut self, e: EdgeIndex<Ix>) > Option<&mut E>
Access the weight for edge e
, mutably.
If edge e
doesn’t exist in the graph, return None
.
Also available with indexing syntax: &mut graph[e]
.
sourcepub fn edge_endpoints(
&self,
e: EdgeIndex<Ix>
) > Option<(NodeIndex<Ix>, NodeIndex<Ix>)>
pub fn edge_endpoints( &self, e: EdgeIndex<Ix> ) > Option<(NodeIndex<Ix>, NodeIndex<Ix>)>
Access the source and target nodes for e
.
If edge e
doesn’t exist in the graph, return None
.
sourcepub fn remove_node(&mut self, a: NodeIndex<Ix>) > Option<N>
pub 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.
sourcepub fn remove_edge(&mut self, e: EdgeIndex<Ix>) > Option<E>
pub 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.
sourcepub fn neighbors(&self, a: NodeIndex<Ix>) > Neighbors<'_, E, Ix> ⓘ
pub fn neighbors(&self, a: NodeIndex<Ix>) > Neighbors<'_, E, Ix> ⓘ
Return an iterator of all nodes with an edge starting from a
.
Directed
: Outgoing edges froma
.Undirected
: All edges from or toa
.
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.
sourcepub fn neighbors_directed(
&self,
a: NodeIndex<Ix>,
dir: Direction
) > Neighbors<'_, E, Ix> ⓘ
pub 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 froma
.Directed
,Incoming
: All edges toa
.Undirected
: All edges from or toa
.
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.
sourcepub fn neighbors_undirected(&self, a: NodeIndex<Ix>) > Neighbors<'_, E, Ix> ⓘ
pub 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
andUndirected
: All edges from or toa
.
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.
sourcepub fn edges(&self, a: NodeIndex<Ix>) > Edges<'_, E, Ty, Ix> ⓘ
pub fn edges(&self, a: NodeIndex<Ix>) > Edges<'_, E, Ty, Ix> ⓘ
Return an iterator of all edges of a
.
Directed
: Outgoing edges froma
.Undirected
: All edges connected toa
.
Produces an empty iterator if the node doesn’t exist.
Iterator element type is EdgeReference<E, Ix>
.
sourcepub fn edges_directed(
&self,
a: NodeIndex<Ix>,
dir: Direction
) > Edges<'_, E, Ty, Ix> ⓘ
pub 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 froma
.Directed
,Incoming
: All edges toa
.Undirected
,Outgoing
: All edges connected toa
, witha
being the source of each edge.Undirected
,Incoming
: All edges connected toa
, witha
being the target of each edge.
Produces an empty iterator if the node a
doesn’t exist.
Iterator element type is EdgeReference<E, Ix>
.
sourcepub fn edges_connecting(
&self,
a: NodeIndex<Ix>,
b: NodeIndex<Ix>
) > EdgesConnecting<'_, E, Ty, Ix> ⓘ
pub fn edges_connecting( &self, a: NodeIndex<Ix>, b: NodeIndex<Ix> ) > EdgesConnecting<'_, E, Ty, Ix> ⓘ
Return an iterator over all the edges connecting a
and b
.
Directed
: Outgoing edges froma
.Undirected
: All edges connected toa
.
Iterator element type is EdgeReference<E, Ix>
.
sourcepub fn contains_edge(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) > bool
pub fn contains_edge(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) > bool
Lookup 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).
sourcepub fn find_edge(
&self,
a: NodeIndex<Ix>,
b: NodeIndex<Ix>
) > Option<EdgeIndex<Ix>>
pub 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).
sourcepub fn find_edge_undirected(
&self,
a: NodeIndex<Ix>,
b: NodeIndex<Ix>
) > Option<(EdgeIndex<Ix>, Direction)>
pub fn find_edge_undirected( &self, a: NodeIndex<Ix>, b: NodeIndex<Ix> ) > Option<(EdgeIndex<Ix>, Direction)>
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.
sourcepub fn externals(&self, dir: Direction) > Externals<'_, N, Ty, Ix> ⓘ
pub fn externals(&self, dir: Direction) > 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.
sourcepub fn node_indices(&self) > NodeIndices<Ix> ⓘ
pub fn node_indices(&self) > NodeIndices<Ix> ⓘ
Return an iterator over the node indices of the graph.
For example, in a rare case where a graph algorithm were not applicable, the following code will iterate through all nodes to find a specific index:
let index = g.node_indices().find(i g[*i] == "book").unwrap();
sourcepub fn node_weights_mut(&mut self) > NodeWeightsMut<'_, N, Ix> ⓘ
pub 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.
sourcepub fn node_weights(&self) > NodeWeights<'_, N, Ix>
pub fn node_weights(&self) > NodeWeights<'_, N, Ix>
Return an iterator yielding immutable access to all node weights.
The order in which weights are yielded matches the order of their node indices.
sourcepub fn edge_indices(&self) > EdgeIndices<Ix> ⓘ
pub fn edge_indices(&self) > EdgeIndices<Ix> ⓘ
Return an iterator over the edge indices of the graph
sourcepub fn edge_references(&self) > EdgeReferences<'_, E, Ix> ⓘ
pub fn edge_references(&self) > EdgeReferences<'_, E, Ix> ⓘ
Create an iterator over all edges, in indexed order.
Iterator element type is EdgeReference<E, Ix>
.
sourcepub fn edge_weights(&self) > EdgeWeights<'_, E, Ix>
pub fn edge_weights(&self) > EdgeWeights<'_, E, Ix>
Return an iterator yielding immutable access to all edge weights.
The order in which weights are yielded matches the order of their edge indices.
sourcepub fn edge_weights_mut(&mut self) > EdgeWeightsMut<'_, E, Ix> ⓘ
pub 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.
sourcepub fn into_nodes_edges(self) > (Vec<Node<N, Ix>>, Vec<Edge<E, Ix>>)
pub 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
sourcepub fn first_edge(
&self,
a: NodeIndex<Ix>,
dir: Direction
) > Option<EdgeIndex<Ix>>
pub fn first_edge( &self, a: NodeIndex<Ix>, dir: Direction ) > Option<EdgeIndex<Ix>>
Accessor for data structure internals: the first edge in the given direction.
sourcepub fn next_edge(
&self,
e: EdgeIndex<Ix>,
dir: Direction
) > Option<EdgeIndex<Ix>>
pub fn next_edge( &self, e: EdgeIndex<Ix>, dir: Direction ) > Option<EdgeIndex<Ix>>
Accessor for data structure internals: the next edge for the given direction.
sourcepub fn index_twice_mut<T, U>(
&mut self,
i: T,
j: U
) > (&mut <Self as Index<T>>::Output, &mut <Self as Index<U>>::Output)where
Self: IndexMut<T> + IndexMut<U>,
T: GraphIndex,
U: GraphIndex,
pub fn index_twice_mut<T, U>( &mut self, i: T, j: U ) > (&mut <Self as Index<T>>::Output, &mut <Self as Index<U>>::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, Incoming};
use petgraph::visit::Dfs;
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.);
sourcepub fn clear_edges(&mut self)
pub fn clear_edges(&mut self)
Remove all edges
sourcepub fn capacity(&self) > (usize, usize)
pub fn capacity(&self) > (usize, usize)
Return the current node and edge capacity of the graph.
sourcepub fn reserve_nodes(&mut self, additional: usize)
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 if the new capacity overflows usize
.
sourcepub fn reserve_edges(&mut self, additional: 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 if the new capacity overflows usize
.
sourcepub fn reserve_exact_nodes(&mut self, additional: usize)
pub fn reserve_exact_nodes(&mut self, additional: usize)
Reserves the minimum capacity for exactly additional
more nodes to be
inserted in the graph. Does nothing if the capacity is already
sufficient.
Prefer reserve_nodes
if future insertions are expected.
Panics if the new capacity overflows usize
.
sourcepub fn reserve_exact_edges(&mut self, additional: usize)
pub fn reserve_exact_edges(&mut self, additional: usize)
Reserves the minimum capacity for exactly additional
more edges to be
inserted in the graph.
Does nothing if the capacity is already sufficient.
Prefer reserve_edges
if future insertions are expected.
Panics if the new capacity overflows usize
.
sourcepub fn shrink_to_fit_nodes(&mut self)
pub fn shrink_to_fit_nodes(&mut self)
Shrinks the capacity of the underlying nodes collection as much as possible.
sourcepub fn shrink_to_fit_edges(&mut self)
pub fn shrink_to_fit_edges(&mut self)
Shrinks the capacity of the underlying edges collection as much as possible.
sourcepub fn shrink_to_fit(&mut self)
pub fn shrink_to_fit(&mut self)
Shrinks the capacity of the graph as much as possible.
sourcepub fn retain_nodes<F>(&mut self, visit: F)where
F: FnMut(Frozen<'_, Self>, NodeIndex<Ix>) > bool,
pub 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.
sourcepub fn retain_edges<F>(&mut self, visit: F)where
F: FnMut(Frozen<'_, Self>, EdgeIndex<Ix>) > bool,
pub fn retain_edges<F>(&mut self, visit: F)where F: FnMut(Frozen<'_, Self>, EdgeIndex<Ix>) > 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.
sourcepub fn from_edges<I>(iterable: I) > Selfwhere
I: IntoIterator,
I::Item: IntoWeightedEdge<E>,
<I::Item as IntoWeightedEdge<E>>::NodeId: Into<NodeIndex<Ix>>,
N: Default,
pub fn from_edges<I>(iterable: I) > Selfwhere I: IntoIterator, I::Item: IntoWeightedEdge<E>, <I::Item as IntoWeightedEdge<E>>::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),
]);
sourcepub 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,
pub 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.
sourcepub 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,
pub 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
.
sourcepub 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>,
pub 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
.
sourcepub fn into_edge_type<NewTy>(self) > Graph<N, E, NewTy, Ix>where
NewTy: EdgeType,
pub 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§
source§impl<N, E, Ty, Ix> Build for Graph<N, E, Ty, Ix>where
Ty: EdgeType,
Ix: IndexType,
impl<N, E, Ty, Ix> Build for Graph<N, E, Ty, Ix>where Ty: EdgeType, Ix: IndexType,
fn add_node(&mut self, weight: Self::NodeWeight) > Self::NodeId
source§fn add_edge(
&mut self,
a: Self::NodeId,
b: Self::NodeId,
weight: Self::EdgeWeight
) > Option<Self::EdgeId>
fn add_edge( &mut self, a: Self::NodeId, b: Self::NodeId, weight: Self::EdgeWeight ) > Option<Self::EdgeId>
None
.source§fn update_edge(
&mut self,
a: Self::NodeId,
b: Self::NodeId,
weight: Self::EdgeWeight
) > Self::EdgeId
fn update_edge( &mut self, a: Self::NodeId, b: Self::NodeId, weight: Self::EdgeWeight ) > Self::EdgeId
a
to b
. Return the id of the affected
edge.source§impl<N, E, Ty, Ix: IndexType> Clone for Graph<N, E, Ty, Ix>where
N: Clone,
E: Clone,
impl<N, E, Ty, Ix: IndexType> Clone for Graph<N, E, Ty, Ix>where N: Clone, E: Clone,
The resulting cloned graph has the same graph indices as self
.
source§impl<N, E, Ty, Ix> Create for Graph<N, E, Ty, Ix>where
Ty: EdgeType,
Ix: IndexType,
impl<N, E, Ty, Ix> Create for Graph<N, E, Ty, Ix>where Ty: EdgeType, Ix: IndexType,
fn with_capacity(nodes: usize, edges: usize) > Self
source§impl<N, E, Ty, Ix> Data for Graph<N, E, Ty, Ix>where
Ix: IndexType,
impl<N, E, Ty, Ix> Data for Graph<N, E, Ty, Ix>where Ix: IndexType,
type NodeWeight = N
type EdgeWeight = E
source§impl<N, E, Ty, Ix> DataMap for Graph<N, E, Ty, Ix>where
Ty: EdgeType,
Ix: IndexType,
impl<N, E, Ty, Ix> DataMap for Graph<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>
source§impl<N, E, Ty, Ix> DataMapMut for Graph<N, E, Ty, Ix>where
Ty: EdgeType,
Ix: IndexType,
impl<N, E, Ty, Ix> DataMapMut for Graph<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>
source§impl<N, E, Ty, Ix> Debug for Graph<N, E, Ty, Ix>where
N: Debug,
E: Debug,
Ty: EdgeType,
Ix: IndexType,
impl<N, E, Ty, Ix> Debug for Graph<N, E, Ty, Ix>where N: Debug, E: Debug, Ty: EdgeType, Ix: IndexType,
source§impl<N, E, Ty, Ix> Default for Graph<N, E, Ty, Ix>where
Ty: EdgeType,
Ix: IndexType,
impl<N, E, Ty, Ix> Default for Graph<N, E, Ty, Ix>where Ty: EdgeType, Ix: IndexType,
Create a new empty Graph
.
source§impl<N, E, Ty, Ix> EdgeCount for Graph<N, E, Ty, Ix>where
Ty: EdgeType,
Ix: IndexType,
impl<N, E, Ty, Ix> EdgeCount for Graph<N, E, Ty, Ix>where Ty: EdgeType, Ix: IndexType,
source§fn edge_count(&self) > usize
fn edge_count(&self) > usize
source§impl<N, E, Ty, Ix> EdgeIndexable for Graph<N, E, Ty, Ix>where
Ty: EdgeType,
Ix: IndexType,
impl<N, E, Ty, Ix> EdgeIndexable for Graph<N, E, Ty, Ix>where Ty: EdgeType, Ix: IndexType,
source§fn edge_bound(&self) > usize
fn edge_bound(&self) > usize
source§fn from_index(&self, ix: usize) > Self::EdgeId
fn from_index(&self, ix: usize) > Self::EdgeId
i
to an edge index. i
must be a valid value in the graph.source§impl<N, E, Ty, Ix> From<Graph<N, E, Ty, Ix>> for StableGraph<N, E, Ty, Ix>where
Ty: EdgeType,
Ix: IndexType,
impl<N, E, Ty, Ix> From<Graph<N, E, Ty, Ix>> for StableGraph<N, E, Ty, Ix>where Ty: EdgeType, Ix: IndexType,
Convert a Graph
into a StableGraph
Computes in O(V + E) time.
The resulting graph has the same node and edge indices as the original graph.
source§impl<N, E, Ty, Ix> From<StableGraph<N, E, Ty, Ix>> for Graph<N, E, Ty, Ix>where
Ty: EdgeType,
Ix: IndexType,
impl<N, E, Ty, Ix> From<StableGraph<N, E, Ty, Ix>> for Graph<N, E, Ty, Ix>where Ty: EdgeType, Ix: IndexType,
Convert a StableGraph
into a Graph
Computes in O(V + E) time.
This translates the stable graph into a graph with node and edge indices in
a compact interval without holes (like Graph
s always are).
Only if the stable graph had no vacancies after deletions (if node bound was equal to node count, and the same for edges), would the resulting graph have the same node and edge indices as the input.
source§fn from(graph: StableGraph<N, E, Ty, Ix>) > Self
fn from(graph: StableGraph<N, E, Ty, Ix>) > Self
source§impl<N, E, Ty, Ix> FromElements for Graph<N, E, Ty, Ix>where
Ty: EdgeType,
Ix: IndexType,
impl<N, E, Ty, Ix> FromElements for Graph<N, E, Ty, Ix>where Ty: EdgeType, Ix: IndexType,
fn from_elements<I>(iterable: I) > Selfwhere Self: Sized, I: IntoIterator<Item = Element<Self::NodeWeight, Self::EdgeWeight>>,
source§impl<N, E, Ty, Ix> GetAdjacencyMatrix for Graph<N, E, Ty, Ix>where
Ty: EdgeType,
Ix: IndexType,
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
type AdjMatrix = FixedBitSet
source§fn adjacency_matrix(&self) > FixedBitSet
fn adjacency_matrix(&self) > FixedBitSet
source§fn is_adjacent(
&self,
matrix: &FixedBitSet,
a: NodeIndex<Ix>,
b: NodeIndex<Ix>
) > bool
fn is_adjacent( &self, matrix: &FixedBitSet, a: NodeIndex<Ix>, b: NodeIndex<Ix> ) > bool
source§impl<N, E, Ty, Ix> Index<EdgeIndex<Ix>> for Graph<N, E, Ty, Ix>where
Ty: EdgeType,
Ix: IndexType,
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.
source§impl<N, E, Ty, Ix> Index<NodeIndex<Ix>> for Graph<N, E, Ty, Ix>where
Ty: EdgeType,
Ix: IndexType,
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.
source§impl<N, E, Ty, Ix> IndexMut<EdgeIndex<Ix>> for Graph<N, E, Ty, Ix>where
Ty: EdgeType,
Ix: IndexType,
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.
source§impl<N, E, Ty, Ix> IndexMut<NodeIndex<Ix>> for Graph<N, E, Ty, Ix>where
Ty: EdgeType,
Ix: IndexType,
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.
source§impl<'a, N: 'a, E: 'a, Ty, Ix> IntoEdgeReferences for &'a Graph<N, E, Ty, Ix>where
Ty: EdgeType,
Ix: IndexType,
impl<'a, N: 'a, E: 'a, Ty, Ix> IntoEdgeReferences for &'a Graph<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
source§impl<'a, N, E, Ty, Ix> IntoEdges for &'a Graph<N, E, Ty, Ix>where
Ty: EdgeType,
Ix: IndexType,
impl<'a, N, E, Ty, Ix> IntoEdges for &'a Graph<N, E, Ty, Ix>where Ty: EdgeType, Ix: IndexType,
source§impl<'a, N, E, Ty, Ix> IntoEdgesDirected for &'a Graph<N, E, Ty, Ix>where
Ty: EdgeType,
Ix: IndexType,
impl<'a, N, E, Ty, Ix> IntoEdgesDirected for &'a Graph<N, E, Ty, Ix>where Ty: EdgeType, Ix: IndexType,
type EdgesDirected = Edges<'a, E, Ty, Ix>
fn edges_directed(self, a: Self::NodeId, dir: Direction) > Self::EdgesDirected
source§impl<'a, N, E: 'a, Ty, Ix> IntoNeighbors for &'a Graph<N, E, Ty, Ix>where
Ty: EdgeType,
Ix: IndexType,
impl<'a, N, E: 'a, Ty, Ix> IntoNeighbors for &'a Graph<N, E, Ty, Ix>where Ty: EdgeType, Ix: IndexType,
source§impl<'a, N, E: 'a, Ty, Ix> IntoNeighborsDirected for &'a Graph<N, E, Ty, Ix>where
Ty: EdgeType,
Ix: IndexType,
impl<'a, N, E: 'a, Ty, Ix> IntoNeighborsDirected for &'a Graph<N, E, Ty, Ix>where Ty: EdgeType, Ix: IndexType,
type NeighborsDirected = Neighbors<'a, E, Ix>
fn neighbors_directed( self, n: NodeIndex<Ix>, d: Direction ) > Neighbors<'a, E, Ix> ⓘ
source§impl<'a, N, E: 'a, Ty, Ix> IntoNodeIdentifiers for &'a Graph<N, E, Ty, Ix>where
Ty: EdgeType,
Ix: IndexType,
impl<'a, N, E: 'a, Ty, Ix> IntoNodeIdentifiers for &'a Graph<N, E, Ty, Ix>where Ty: EdgeType, Ix: IndexType,
type NodeIdentifiers = NodeIndices<Ix>
fn node_identifiers(self) > NodeIndices<Ix> ⓘ
source§impl<'a, N, E, Ty, Ix> IntoNodeReferences for &'a Graph<N, E, Ty, Ix>where
Ty: EdgeType,
Ix: IndexType,
impl<'a, N, E, Ty, Ix> IntoNodeReferences for &'a Graph<N, E, Ty, Ix>where Ty: EdgeType, Ix: IndexType,
type NodeRef = (NodeIndex<Ix>, &'a N)
type NodeReferences = NodeReferences<'a, N, Ix>
fn node_references(self) > Self::NodeReferences
source§impl<N, E, Ty, Ix> NodeCount for Graph<N, E, Ty, Ix>where
Ty: EdgeType,
Ix: IndexType,
impl<N, E, Ty, Ix> NodeCount for Graph<N, E, Ty, Ix>where Ty: EdgeType, Ix: IndexType,
fn node_count(&self) > usize
source§impl<N, E, Ty, Ix> NodeIndexable for Graph<N, E, Ty, Ix>where
Ty: EdgeType,
Ix: IndexType,
impl<N, E, Ty, Ix> NodeIndexable for Graph<N, E, Ty, Ix>where Ty: EdgeType, Ix: IndexType,
source§fn node_bound(&self) > usize
fn node_bound(&self) > usize
source§fn from_index(&self, ix: usize) > Self::NodeId
fn from_index(&self, ix: usize) > Self::NodeId
i
to a node index. i
must be a valid value in the graph.