Struct petgraph::graph::Graph [−][src]
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 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.
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 isSend
andSync
(as long as associated dataN
andE
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]
impl<N, E> Graph<N, E, Directed>
pub fn new() > Self
[src]
pub 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]
impl<N, E> Graph<N, E, Undirected>
pub fn new_undirected() > Self
[src]
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
.
impl<N, E, Ty, Ix> Graph<N, E, Ty, Ix> where
Ty: EdgeType,
Ix: IndexType,
[src]
impl<N, E, Ty, Ix> Graph<N, E, Ty, Ix> where
Ty: EdgeType,
Ix: IndexType,
pub fn with_capacity(nodes: usize, edges: usize) > Self
[src]
pub fn with_capacity(nodes: usize, edges: usize) > Self
Create a new Graph
with estimated capacity.
pub fn node_count(&self) > usize
[src]
pub fn node_count(&self) > usize
Return the number of nodes (vertices) in the graph.
Computes in O(1) time.
pub fn edge_count(&self) > usize
[src]
pub fn edge_count(&self) > usize
Return the number of edges in the graph.
Computes in O(1) time.
pub fn is_directed(&self) > bool
[src]
pub fn is_directed(&self) > bool
Whether the graph has directed edges or not.
pub fn add_node(&mut self, weight: N) > NodeIndex<Ix>
[src]
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).
pub fn node_weight(&self, a: NodeIndex<Ix>) > Option<&N>
[src]
pub fn node_weight(&self, a: NodeIndex<Ix>) > Option<&N>
Access the weight for node a
.
Also available with indexing syntax: &graph[a]
.
pub fn node_weight_mut(&mut self, a: NodeIndex<Ix>) > Option<&mut N>
[src]
pub 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]
.
pub fn add_edge(
&mut self,
a: NodeIndex<Ix>,
b: NodeIndex<Ix>,
weight: E
) > EdgeIndex<Ix>
[src]
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.
pub fn update_edge(
&mut self,
a: NodeIndex<Ix>,
b: NodeIndex<Ix>,
weight: E
) > EdgeIndex<Ix>
[src]
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 don't exist.
pub fn edge_weight(&self, e: EdgeIndex<Ix>) > Option<&E>
[src]
pub fn edge_weight(&self, e: EdgeIndex<Ix>) > Option<&E>
Access the weight for edge e
.
Also available with indexing syntax: &graph[e]
.
pub fn edge_weight_mut(&mut self, e: EdgeIndex<Ix>) > Option<&mut E>
[src]
pub 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]
.
pub fn edge_endpoints(
&self,
e: EdgeIndex<Ix>
) > Option<(NodeIndex<Ix>, NodeIndex<Ix>)>
[src]
pub fn edge_endpoints(
&self,
e: EdgeIndex<Ix>
) > Option<(NodeIndex<Ix>, NodeIndex<Ix>)>
Access the source and target nodes for e
.
pub fn remove_node(&mut self, a: NodeIndex<Ix>) > Option<N>
[src]
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.
pub fn remove_edge(&mut self, e: EdgeIndex<Ix>) > Option<E>
[src]
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.
ⓘImportant traits for Neighbors<'a, E, Ix>pub fn neighbors(&self, a: NodeIndex<Ix>) > Neighbors<E, Ix>
[src]
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.
ⓘImportant traits for Neighbors<'a, E, Ix>pub fn neighbors_directed(
&self,
a: NodeIndex<Ix>,
dir: Direction
) > Neighbors<E, Ix>
[src]
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.
ⓘImportant traits for Neighbors<'a, E, Ix>pub fn neighbors_undirected(&self, a: NodeIndex<Ix>) > Neighbors<E, Ix>
[src]
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.
ⓘImportant traits for Edges<'a, E, Ty, Ix>pub fn edges(&self, a: NodeIndex<Ix>) > Edges<E, Ty, Ix>
[src]
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>
.
ⓘImportant traits for Edges<'a, E, Ty, Ix>pub fn edges_directed(
&self,
a: NodeIndex<Ix>,
dir: Direction
) > Edges<E, Ty, Ix>
[src]
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
: All edges connected toa
.
Produces an empty iterator if the node a
doesn't exist.
Iterator element type is EdgeReference<E, Ix>
.
pub fn contains_edge(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) > bool
[src]
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).
pub fn find_edge(
&self,
a: NodeIndex<Ix>,
b: NodeIndex<Ix>
) > Option<EdgeIndex<Ix>>
[src]
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).
pub fn find_edge_undirected(
&self,
a: NodeIndex<Ix>,
b: NodeIndex<Ix>
) > Option<(EdgeIndex<Ix>, Direction)>
[src]
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.
ⓘImportant traits for Externals<'a, N, Ty, Ix>pub fn externals(&self, dir: Direction) > Externals<N, Ty, Ix>
[src]
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.
ⓘImportant traits for NodeIndices<Ix>pub fn node_indices(&self) > NodeIndices<Ix>
[src]
pub fn node_indices(&self) > NodeIndices<Ix>
Return an iterator over the node indices of the graph
ⓘImportant traits for NodeWeightsMut<'a, N, Ix>pub fn node_weights_mut(&mut self) > NodeWeightsMut<N, Ix>
[src]
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.
ⓘImportant traits for EdgeIndices<Ix>pub fn edge_indices(&self) > EdgeIndices<Ix>
[src]
pub fn edge_indices(&self) > EdgeIndices<Ix>
Return an iterator over the edge indices of the graph
ⓘImportant traits for EdgeReferences<'a, E, Ix>pub fn edge_references(&self) > EdgeReferences<E, Ix>
[src]
pub fn edge_references(&self) > EdgeReferences<E, Ix>
Create an iterator over all edges, in indexed order.
Iterator element type is EdgeReference<E, Ix>
.
ⓘImportant traits for EdgeWeightsMut<'a, E, Ix>pub fn edge_weights_mut(&mut self) > EdgeWeightsMut<E, Ix>
[src]
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.
pub fn raw_nodes(&self) > &[Node<N, Ix>]
[src]
pub fn raw_nodes(&self) > &[Node<N, Ix>]
Access the internal node array.
pub fn raw_edges(&self) > &[Edge<E, Ix>]
[src]
pub fn raw_edges(&self) > &[Edge<E, Ix>]
Access the internal edge array.
pub fn into_nodes_edges(self) > (Vec<Node<N, Ix>>, Vec<Edge<E, Ix>>)
[src]
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
pub fn first_edge(
&self,
a: NodeIndex<Ix>,
dir: Direction
) > Option<EdgeIndex<Ix>>
[src]
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.
pub fn next_edge(
&self,
e: EdgeIndex<Ix>,
dir: Direction
) > Option<EdgeIndex<Ix>>
[src]
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.
pub 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,
[src]
pub 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, 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.);
pub fn reverse(&mut self)
[src]
pub fn reverse(&mut self)
Reverse the direction of all edges
pub fn clear(&mut self)
[src]
pub fn clear(&mut self)
Remove all nodes and edges
pub fn clear_edges(&mut self)
[src]
pub fn clear_edges(&mut self)
Remove all edges
pub fn capacity(&self) > (usize, usize)
[src]
pub fn capacity(&self) > (usize, usize)
Return the current node and edge capacity of the graph.
pub fn reserve_nodes(&mut self, additional: usize)
[src]
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
.
pub fn reserve_edges(&mut self, additional: usize)
[src]
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
.
pub fn reserve_exact_nodes(&mut self, additional: usize)
[src]
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
.
pub fn reserve_exact_edges(&mut self, additional: usize)
[src]
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
.
pub fn shrink_to_fit_nodes(&mut self)
[src]
pub fn shrink_to_fit_nodes(&mut self)
Shrinks the capacity of the underlying nodes collection as much as possible.
pub fn shrink_to_fit_edges(&mut self)
[src]
pub fn shrink_to_fit_edges(&mut self)
Shrinks the capacity of the underlying edges collection as much as possible.
pub fn shrink_to_fit(&mut self)
[src]
pub fn shrink_to_fit(&mut self)
Shrinks the capacity of the graph as much as possible.
pub fn retain_nodes<F>(&mut self, visit: F) where
F: FnMut(Frozen<Self>, NodeIndex<Ix>) > bool,
[src]
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.
pub fn retain_edges<F>(&mut self, visit: F) where
F: FnMut(Frozen<Self>, EdgeIndex<Ix>) > bool,
[src]
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.
pub 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,
[src]
pub 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 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), ]);
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,
[src]
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.
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,
[src]
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
.
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>,
[src]
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
.
pub fn into_edge_type<NewTy>(self) > Graph<N, E, NewTy, Ix> where
NewTy: EdgeType,
[src]
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
impl<'a, N, E: 'a, Ty, Ix> IntoNeighbors for &'a Graph<N, E, Ty, Ix> where
Ty: EdgeType,
Ix: IndexType,
[src]
impl<'a, N, E: 'a, Ty, Ix> IntoNeighbors for &'a Graph<N, E, Ty, Ix> where
Ty: EdgeType,
Ix: IndexType,
type Neighbors = Neighbors<'a, E, Ix>
ⓘImportant traits for Neighbors<'a, E, Ix>fn neighbors(self, n: NodeIndex<Ix>) > Neighbors<'a, E, Ix>
[src]
fn neighbors(self, n: NodeIndex<Ix>) > Neighbors<'a, E, Ix>
Return an iterator of the neighbors of node a
.
impl<'a, N, E: 'a, Ty, Ix> IntoNeighborsDirected for &'a Graph<N, E, Ty, Ix> where
Ty: EdgeType,
Ix: IndexType,
[src]
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>
ⓘImportant traits for Neighbors<'a, E, Ix>fn neighbors_directed(
self,
n: NodeIndex<Ix>,
d: Direction
) > Neighbors<'a, E, Ix>
[src]
fn neighbors_directed(
self,
n: NodeIndex<Ix>,
d: Direction
) > Neighbors<'a, E, Ix>
impl<'a, N, E: 'a, Ty, Ix> IntoNodeIdentifiers for &'a Graph<N, E, Ty, Ix> where
Ty: EdgeType,
Ix: IndexType,
[src]
impl<'a, N, E: 'a, Ty, Ix> IntoNodeIdentifiers for &'a Graph<N, E, Ty, Ix> where
Ty: EdgeType,
Ix: IndexType,
type NodeIdentifiers = NodeIndices<Ix>
ⓘImportant traits for NodeIndices<Ix>fn node_identifiers(self) > NodeIndices<Ix>
[src]
fn node_identifiers(self) > NodeIndices<Ix>
impl<N, E, Ty, Ix> NodeCount for Graph<N, E, Ty, Ix> where
Ty: EdgeType,
Ix: IndexType,
[src]
impl<N, E, Ty, Ix> NodeCount for Graph<N, E, Ty, Ix> where
Ty: EdgeType,
Ix: IndexType,
fn node_count(&self) > usize
[src]
fn node_count(&self) > usize
impl<N, E, Ty, Ix> GraphProp for Graph<N, E, Ty, Ix> where
Ty: EdgeType,
Ix: IndexType,
[src]
impl<N, E, Ty, Ix> GraphProp for 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,
[src]
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
[src]
fn edge_references(self) > Self::EdgeReferences
impl<N, E, Ty, Ix> NodeIndexable for Graph<N, E, Ty, Ix> where
Ty: EdgeType,
Ix: IndexType,
[src]
impl<N, E, Ty, Ix> NodeIndexable for Graph<N, E, Ty, Ix> where
Ty: EdgeType,
Ix: IndexType,
fn node_bound(&self) > usize
[src]
fn node_bound(&self) > usize
Return an upper bound of the node indices in the graph (suitable for the size of a bitmap). Read more
fn to_index(&self, ix: NodeIndex<Ix>) > usize
[src]
fn to_index(&self, ix: NodeIndex<Ix>) > usize
Convert a
to an integer index.
fn from_index(&self, ix: usize) > Self::NodeId
[src]
fn from_index(&self, ix: usize) > Self::NodeId
Convert i
to a node index
impl<N, E, Ty, Ix> NodeCompactIndexable for Graph<N, E, Ty, Ix> where
Ty: EdgeType,
Ix: IndexType,
[src]
impl<N, E, Ty, Ix> NodeCompactIndexable for Graph<N, E, Ty, Ix> where
Ty: EdgeType,
Ix: IndexType,
impl<N, E, Ty, Ix> GraphBase for Graph<N, E, Ty, Ix> where
Ix: IndexType,
[src]
impl<N, E, Ty, Ix> GraphBase for Graph<N, E, Ty, Ix> where
Ix: IndexType,
impl<N, E, Ty, Ix> Visitable for Graph<N, E, Ty, Ix> where
Ty: EdgeType,
Ix: IndexType,
[src]
impl<N, E, Ty, Ix> Visitable for Graph<N, E, Ty, Ix> where
Ty: EdgeType,
Ix: IndexType,
type Map = FixedBitSet
The associated map type
fn visit_map(&self) > FixedBitSet
[src]
fn visit_map(&self) > FixedBitSet
Create a new visitor map
fn reset_map(&self, map: &mut Self::Map)
[src]
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 Graph<N, E, Ty, Ix> where
Ix: IndexType,
[src]
impl<N, E, Ty, Ix> Data for Graph<N, E, Ty, Ix> where
Ix: IndexType,
type NodeWeight = N
type EdgeWeight = E
impl<N, E, Ty, Ix> DataMap for Graph<N, E, Ty, Ix> where
Ty: EdgeType,
Ix: IndexType,
[src]
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>
[src]
fn node_weight(&self, id: Self::NodeId) > Option<&Self::NodeWeight>
fn edge_weight(&self, id: Self::EdgeId) > Option<&Self::EdgeWeight>
[src]
fn edge_weight(&self, id: Self::EdgeId) > Option<&Self::EdgeWeight>
impl<N, E, Ty, Ix> DataMapMut for Graph<N, E, Ty, Ix> where
Ty: EdgeType,
Ix: IndexType,
[src]
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>
[src]
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>
[src]
fn edge_weight_mut(&mut self, id: Self::EdgeId) > Option<&mut Self::EdgeWeight>
impl<N, E, Ty, Ix> Build for Graph<N, E, Ty, Ix> where
Ty: EdgeType,
Ix: IndexType,
[src]
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
[src]
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>
[src]
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
. Read more
fn update_edge(
&mut self,
a: Self::NodeId,
b: Self::NodeId,
weight: Self::EdgeWeight
) > Self::EdgeId
[src]
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. Read more
impl<N, E, Ty, Ix> Create for Graph<N, E, Ty, Ix> where
Ty: EdgeType,
Ix: IndexType,
[src]
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
[src]
fn with_capacity(nodes: usize, edges: usize) > Self
impl<N, E, Ty, Ix> FromElements for Graph<N, E, Ty, Ix> where
Ty: EdgeType,
Ix: IndexType,
[src]
impl<N, E, Ty, Ix> FromElements for Graph<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>>,
[src]
fn from_elements<I>(iterable: I) > Self where
Self: Sized,
I: IntoIterator<Item = Element<Self::NodeWeight, Self::EdgeWeight>>,
impl<N, E, Ty, Ix> Serialize for Graph<N, E, Ty, Ix> where
Ty: EdgeType,
Ix: IndexType + Serialize,
N: Serialize,
E: Serialize,
[src]
impl<N, E, Ty, Ix> Serialize for Graph<N, E, Ty, Ix> where
Ty: EdgeType,
Ix: IndexType + Serialize,
N: Serialize,
E: Serialize,
Requires crate feature "serde1"
fn serialize<S>(&self, serializer: S) > Result<S::Ok, S::Error> where
S: Serializer,
[src]
fn serialize<S>(&self, serializer: S) > Result<S::Ok, S::Error> where
S: Serializer,
Serialize this value into the given Serde serializer. Read more
impl<'de, N, E, Ty, Ix> Deserialize<'de> for Graph<N, E, Ty, Ix> where
Ty: EdgeType,
Ix: IndexType + Deserialize<'de>,
N: Deserialize<'de>,
E: Deserialize<'de>,
[src]
impl<'de, N, E, Ty, Ix> Deserialize<'de> for Graph<N, E, Ty, Ix> where
Ty: EdgeType,
Ix: IndexType + Deserialize<'de>,
N: Deserialize<'de>,
E: Deserialize<'de>,
Requires crate feature "serde1"
fn deserialize<D>(deserializer: D) > Result<Self, D::Error> where
D: Deserializer<'de>,
[src]
fn deserialize<D>(deserializer: D) > Result<Self, D::Error> where
D: Deserializer<'de>,
Deserialize this value from the given Serde deserializer. Read more
impl<N, E, Ty, Ix> From<Graph<N, E, Ty, Ix>> for StableGraph<N, E, Ty, Ix> where
Ty: EdgeType,
Ix: IndexType,
[src]
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.
impl<N, E, Ty, Ix> From<StableGraph<N, E, Ty, Ix>> for Graph<N, E, Ty, Ix> where
Ty: EdgeType,
Ix: IndexType,
[src]
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.
fn from(graph: StableGraph<N, E, Ty, Ix>) > Self
[src]
fn from(graph: StableGraph<N, E, Ty, Ix>) > Self
Performs the conversion.
impl<N, E, Ty, Ix: IndexType> Clone for Graph<N, E, Ty, Ix> where
N: Clone,
E: Clone,
[src]
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
.
fn clone(&self) > Self
[src]
fn clone(&self) > Self
Returns a copy of the value. Read more
fn clone_from(&mut self, rhs: &Self)
[src]
fn clone_from(&mut self, rhs: &Self)
Performs copyassignment 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> Debug for Graph<N, E, Ty, Ix> where
N: Debug,
E: Debug,
Ty: EdgeType,
Ix: IndexType,
fn fmt(&self, f: &mut Formatter) > Result
[src]
fn fmt(&self, f: &mut Formatter) > Result
Formats the value using the given formatter. Read more
impl<'a, N, E, Ty, Ix> IntoEdges for &'a Graph<N, E, Ty, Ix> where
Ty: EdgeType,
Ix: IndexType,
[src]
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> IntoEdgesDirected for &'a Graph<N, E, Ty, Ix> where
Ty: EdgeType,
Ix: IndexType,
[src]
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
[src]
fn edges_directed(self, a: Self::NodeId, dir: Direction) > Self::EdgesDirected
impl<N, E, Ty, Ix> Index<NodeIndex<Ix>> for Graph<N, E, Ty, Ix> where
Ty: EdgeType,
Ix: IndexType,
[src]
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
[src]
fn index(&self, index: NodeIndex<Ix>) > &N
Performs the indexing (container[index]
) operation.
impl<N, E, Ty, Ix> IndexMut<NodeIndex<Ix>> for Graph<N, E, Ty, Ix> where
Ty: EdgeType,
Ix: IndexType,
[src]
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
[src]
fn index_mut(&mut self, index: NodeIndex<Ix>) > &mut N
Performs the mutable indexing (container[index]
) operation.
impl<N, E, Ty, Ix> Index<EdgeIndex<Ix>> for Graph<N, E, Ty, Ix> where
Ty: EdgeType,
Ix: IndexType,
[src]
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
[src]
fn index(&self, index: EdgeIndex<Ix>) > &E
Performs the indexing (container[index]
) operation.
impl<N, E, Ty, Ix> IndexMut<EdgeIndex<Ix>> for Graph<N, E, Ty, Ix> where
Ty: EdgeType,
Ix: IndexType,
[src]
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
[src]
fn index_mut(&mut self, index: EdgeIndex<Ix>) > &mut E
Performs the mutable indexing (container[index]
) operation.
impl<N, E, Ty, Ix> Default for Graph<N, E, Ty, Ix> where
Ty: EdgeType,
Ix: IndexType,
[src]
impl<N, E, Ty, Ix> Default for Graph<N, E, Ty, Ix> where
Ty: EdgeType,
Ix: IndexType,
Create a new empty Graph
.
impl<'a, N, E, Ty, Ix> IntoNodeReferences for &'a Graph<N, E, Ty, Ix> where
Ty: EdgeType,
Ix: IndexType,
[src]
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
[src]
fn node_references(self) > Self::NodeReferences
impl<N, E, Ty, Ix> GetAdjacencyMatrix for Graph<N, E, Ty, Ix> where
Ty: EdgeType,
Ix: IndexType,
[src]
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
The associated adjacency matrix type
fn adjacency_matrix(&self) > FixedBitSet
[src]
fn adjacency_matrix(&self) > FixedBitSet
Create the adjacency matrix
fn is_adjacent(
&self,
matrix: &FixedBitSet,
a: NodeIndex<Ix>,
b: NodeIndex<Ix>
) > bool
[src]
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. Read more
impl<N, E, Ty, Ix> Arbitrary for Graph<N, E, Ty, Ix> where
N: Arbitrary,
E: Arbitrary,
Ty: EdgeType + Send + 'static,
Ix: IndexType + Send,
[src]
impl<N, E, Ty, Ix> Arbitrary for Graph<N, E, Ty, Ix> where
N: Arbitrary,
E: Arbitrary,
Ty: EdgeType + Send + 'static,
Ix: IndexType + Send,
Arbitrary
for Graph
creates a graph by selecting a node count
and a probability for each possible edge to exist.
The result will be simple graph or digraph, self loops possible, no parallel edges.
The exact properties of the produced graph is subject to change.
Requires crate feature "quickcheck"