Struct petgraph::stable_graph::StableGraph
[−]
[src]
pub struct StableGraph<N, E, Ty = Directed, Ix = DefaultIx> { /* fields omitted */ }
StableGraph<N, E, Ty, Ix>
is a graph datastructure using an adjacency
list representation.
The graph does not invalidate any unrelated node or edge indices when items are removed.
StableGraph
is parameterized over:
- Associated data
N
for nodes andE
for edges, also called weights. The associated data can be of arbitrary type. - Edge type
Ty
that determines whether the graph edges are directed or undirected. - Index type
Ix
, which determines the maximum size of the graph.
The graph uses O(|V| + |E|) space, and allows fast node and edge insert and efficient graph search.
It implements O(e') edge lookup and edge and node removals, where e' is some local measure of edge count.
Nodes and edges are each numbered in an interval from 0 to some number m, but not all indices in the range are valid, since gaps are formed by deletions.
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
.The
StableGraph
is a regular rust collection and isSend
andSync
(as long as associated dataN
andE
are).Indices don't allow as much compile time checking as references.
Depends on crate feature stable_graph
(default). This is a new feature in
petgraph. You can contribute to help it achieve parity with Graph.
Methods
impl<N, E> StableGraph<N, E, Directed>
[src]
fn new() -> Self
Create a new StableGraph
with directed edges.
This is a convenience method. See StableGraph::with_capacity
or StableGraph::default
for a constructor that is generic in all the
type parameters of StableGraph
.
impl<N, E, Ty, Ix> StableGraph<N, E, Ty, Ix> where Ty: EdgeType, Ix: IndexType
[src]
fn with_capacity(nodes: usize, edges: usize) -> Self
Create a new StableGraph
with estimated capacity.
fn capacity(&self) -> (usize, usize)
Return the current node and edge capacity of the graph.
fn clear(&mut self)
Remove all nodes and edges
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.
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
.
The node index a
is invalidated, but none other.
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
.
fn contains_node(&self, a: NodeIndex<Ix>) -> bool
fn add_edge(&mut self,
a: NodeIndex<Ix>,
b: NodeIndex<Ix>,
weight: E)
-> EdgeIndex<Ix>
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.
Note: StableGraph
allows adding parallel (“duplicate”) edges.
fn update_edge(&mut self,
a: NodeIndex<Ix>,
b: NodeIndex<Ix>,
weight: E)
-> EdgeIndex<Ix>
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 remove_edge(&mut self, e: EdgeIndex<Ix>) -> Option<E>
Remove an edge and return its edge weight, or None
if it didn't exist.
Invalidates the edge index e
but no other.
Computes in O(e') time, where e' is the number of edges
conneced to the same endpoints as e
.
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 node_indices(&self) -> NodeIndices<N, Ix>
Return an iterator over the node indices of the graph
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>)>
e: EdgeIndex<Ix>)
-> Option<(NodeIndex<Ix>, NodeIndex<Ix>)>
Access the source and target nodes for 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 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 connected 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.
fn neighbors_directed(&self,
a: NodeIndex<Ix>,
dir: Direction)
-> Neighbors<E, Ix>
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 connected toa
.
Produces an empty iterator if the node doesn't exist.
Iterator element type is NodeIndex<Ix>
.
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).
Directed
andUndirected
: All edges connected 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.
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>
.
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>
.
fn from_edges<I>(iterable: I) -> Self where I: IntoIterator,
I::Item: IntoWeightedEdge<E>,
I::Item::NodeId: Into<NodeIndex<Ix>>,
N: Default
I::Item: IntoWeightedEdge<E>,
I::Item::NodeId: Into<NodeIndex<Ix>>,
N: Default
Create a new StableGraph
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::stable_graph::StableGraph; let gr = StableGraph::<(), 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
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.
Trait Implementations
impl<'a, N, E: 'a, Ty, Ix> IntoNeighbors for &'a StableGraph<N, E, Ty, Ix> where Ty: EdgeType,
Ix: IndexType
[src]
Ix: IndexType
type Neighbors = Neighbors<'a, E, Ix>
fn neighbors(self, n: Self::NodeId) -> Self::Neighbors
Return an iterator of the neighbors of node a
.
impl<'a, N, E: 'a, Ty, Ix> IntoNeighborsDirected for &'a StableGraph<N, E, Ty, Ix> where Ty: EdgeType,
Ix: IndexType
[src]
Ix: IndexType
type NeighborsDirected = Neighbors<'a, E, Ix>
fn neighbors_directed(self,
n: NodeIndex<Ix>,
d: Direction)
-> Self::NeighborsDirected
n: NodeIndex<Ix>,
d: Direction)
-> Self::NeighborsDirected
impl<'a, N, E: 'a, Ty, Ix> IntoNodeIdentifiers for &'a StableGraph<N, E, Ty, Ix> where Ty: EdgeType,
Ix: IndexType
[src]
Ix: IndexType
type NodeIdentifiers = NodeIndices<'a, N, Ix>
fn node_identifiers(self) -> Self::NodeIdentifiers
impl<N, E, Ty, Ix> NodeCount for StableGraph<N, E, Ty, Ix> where Ty: EdgeType,
Ix: IndexType
[src]
Ix: IndexType
fn node_count(&self) -> usize
impl<N, E, Ty, Ix> GraphProp for StableGraph<N, E, Ty, Ix> where Ty: EdgeType,
Ix: IndexType
[src]
Ix: IndexType
impl<N, E, Ty, Ix> GraphBase for StableGraph<N, E, Ty, Ix> where Ix: IndexType
[src]
impl<N, E, Ty, Ix> Visitable for StableGraph<N, E, Ty, Ix> where Ty: EdgeType,
Ix: IndexType
[src]
Ix: IndexType
type Map = FixedBitSet
The associated map type
fn visit_map(&self) -> FixedBitSet
Create a new visitor map
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 StableGraph<N, E, Ty, Ix> where Ty: EdgeType,
Ix: IndexType
[src]
Ix: IndexType
type NodeWeight = N
type EdgeWeight = E
impl<N, E, Ty, Ix> DataMap for StableGraph<N, E, Ty, Ix> where Ty: EdgeType,
Ix: IndexType
[src]
Ix: IndexType
fn node_weight(&self, id: Self::NodeId) -> Option<&Self::NodeWeight>
fn edge_weight(&self, id: Self::EdgeId) -> Option<&Self::EdgeWeight>
impl<N, E, Ty, Ix> DataMapMut for StableGraph<N, E, Ty, Ix> where Ty: EdgeType,
Ix: IndexType
[src]
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>
impl<N, E, Ty, Ix> Build for StableGraph<N, E, Ty, Ix> where Ty: EdgeType,
Ix: IndexType
[src]
Ix: IndexType
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>
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
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 StableGraph<N, E, Ty, Ix> where Ty: EdgeType,
Ix: IndexType
[src]
Ix: IndexType
fn with_capacity(nodes: usize, edges: usize) -> Self
impl<N, E, Ty, Ix> FromElements for StableGraph<N, E, Ty, Ix> where Ty: EdgeType,
Ix: IndexType
[src]
Ix: IndexType
fn from_elements<I>(iterable: I) -> Self where Self: Sized,
I: IntoIterator<Item=Element<Self::NodeWeight, Self::EdgeWeight>>
I: IntoIterator<Item=Element<Self::NodeWeight, Self::EdgeWeight>>
impl<N, E, Ty, Ix> Debug for StableGraph<N, E, Ty, Ix> where N: Debug,
E: Debug,
Ty: EdgeType,
Ix: IndexType
[src]
E: Debug,
Ty: EdgeType,
Ix: IndexType
impl<N, E, Ty, Ix: IndexType> Clone for StableGraph<N, E, Ty, Ix> where N: Clone,
E: Clone
[src]
E: Clone
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> Index<NodeIndex<Ix>> for StableGraph<N, E, Ty, Ix> where Ty: EdgeType,
Ix: IndexType
[src]
Ix: IndexType
Index the StableGraph
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 (container[index]
) operation
impl<N, E, Ty, Ix> IndexMut<NodeIndex<Ix>> for StableGraph<N, E, Ty, Ix> where Ty: EdgeType,
Ix: IndexType
[src]
Ix: IndexType
Index the StableGraph
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 mutable indexing (container[index]
) operation
impl<N, E, Ty, Ix> Index<EdgeIndex<Ix>> for StableGraph<N, E, Ty, Ix> where Ty: EdgeType,
Ix: IndexType
[src]
Ix: IndexType
Index the StableGraph
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 (container[index]
) operation
impl<N, E, Ty, Ix> IndexMut<EdgeIndex<Ix>> for StableGraph<N, E, Ty, Ix> where Ty: EdgeType,
Ix: IndexType
[src]
Ix: IndexType
Index the StableGraph
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 mutable indexing (container[index]
) operation
impl<N, E, Ty, Ix> Default for StableGraph<N, E, Ty, Ix> where Ty: EdgeType,
Ix: IndexType
[src]
Ix: IndexType
Create a new empty StableGraph
.
impl<'a, N, E, Ty, Ix> IntoEdges for &'a StableGraph<N, E, Ty, Ix> where Ty: EdgeType,
Ix: IndexType
[src]
Ix: IndexType
impl<'a, N: 'a, E: 'a, Ty, Ix> IntoEdgeReferences for &'a StableGraph<N, E, Ty, Ix> where Ty: EdgeType,
Ix: IndexType
[src]
Ix: IndexType
type EdgeRef = EdgeReference<'a, E, Ix>
type EdgeReferences = EdgeReferences<'a, E, Ix>
fn edge_references(self) -> Self::EdgeReferences
Create an iterator over all edges in the graph, in indexed order.
Iterator element type is EdgeReference<E, Ix>
.
impl<N, E, Ty, Ix> NodeIndexable for StableGraph<N, E, Ty, Ix> where Ty: EdgeType,
Ix: IndexType
[src]
Ix: IndexType
fn node_bound(&self) -> usize
Return an upper bound of the node indices in the graph
fn to_index(&self, ix: NodeIndex<Ix>) -> usize
Convert a
to an integer index.
fn from_index(&self, ix: usize) -> Self::NodeId
Convert i
to a node index
impl<N, E, Ty, Ix> GetAdjacencyMatrix for StableGraph<N, E, Ty, Ix> where Ty: EdgeType,
Ix: IndexType
[src]
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
Create the adjacency matrix
fn is_adjacent(&self,
matrix: &FixedBitSet,
a: NodeIndex<Ix>,
b: NodeIndex<Ix>)
-> bool
matrix: &FixedBitSet,
a: NodeIndex<Ix>,
b: NodeIndex<Ix>)
-> bool
Return true if there is an edge from a
to b
, false otherwise. Read more