Struct petgraph::graphmap::GraphMap [−][src]
pub struct GraphMap<N, E, Ty> { /* fields omitted */ }
Expand description
GraphMap<N, E, Ty>
is a graph datastructure using an associative array
of its node weights N
.
It uses an combined adjacency list and sparse adjacency matrix representation, using O(|V| + |E|) space, and allows testing for edge existence in constant time.
GraphMap
is parameterized over:
- Associated data
N
for nodes andE
for edges, called weights. - The node weight
N
must implementCopy
and will be used as node identifier, duplicated into several places in the data structure. It must be suitable as a hash table key (implementingEq + Hash
). The node type must also implementOrd
so that the implementation can order the pair (a
,b
) for an edge connecting any two nodesa
andb
. E
can be of arbitrary type.- Edge type
Ty
that determines whether the graph edges are directed or undirected.
You can use the type aliases UnGraphMap
and DiGraphMap
for convenience.
GraphMap
does not allow parallel edges, but self loops are allowed.
Depends on crate feature graphmap
(default).
Implementations
Create a new GraphMap
with estimated capacity.
Return the current node and edge capacity of the graph.
Whether the graph has directed edges.
pub fn from_edges<I>(iterable: I) -> Self where
I: IntoIterator,
I::Item: IntoWeightedEdge<E, NodeId = N>,
pub fn from_edges<I>(iterable: I) -> Self where
I: IntoIterator,
I::Item: IntoWeightedEdge<E, NodeId = N>,
Create a new GraphMap
from an iterable of edges.
Node values are taken directly from the list.
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::graphmap::UnGraphMap; // Create a new undirected GraphMap. // Use a type hint to have `()` be the edge weight type. let gr = UnGraphMap::<_, ()>::from_edges(&[ (0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3), ]);
Return the number of nodes in the graph.
Return the number of edges in the graph.
Return true
if node n
was removed.
Computes in O(V) time, due to the removal of edges with other nodes.
Return true
if the node is contained in the graph.
Add an edge connecting a
and b
to the graph, with associated
data weight
. For a directed graph, the edge is directed from a
to b
.
Inserts nodes a
and/or b
if they aren’t already part of the graph.
Return None
if the edge did not previously exist, otherwise,
the associated data is updated and the old value is returned
as Some(old_weight)
.
// Create a GraphMap with directed edges, and add one edge to it use petgraph::graphmap::DiGraphMap; let mut g = DiGraphMap::new(); g.add_edge("x", "y", -1); assert_eq!(g.node_count(), 2); assert_eq!(g.edge_count(), 1); assert!(g.contains_edge("x", "y")); assert!(!g.contains_edge("y", "x"));
Remove edge from a
to b
from the graph and return the edge weight.
Return None
if the edge didn’t exist.
// Create a GraphMap with undirected edges, and add and remove an edge. use petgraph::graphmap::UnGraphMap; let mut g = UnGraphMap::new(); g.add_edge("x", "y", -1); let edge_data = g.remove_edge("y", "x"); assert_eq!(edge_data, Some(-1)); assert_eq!(g.edge_count(), 0);
Return true
if the edge connecting a
with b
is contained in the graph.
Return an iterator over the nodes of the graph.
Iterator element type is N
.
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 N
.
pub fn neighbors_directed(
&self,
a: N,
dir: Direction
) -> NeighborsDirected<'_, N, Ty>ⓘNotable traits for NeighborsDirected<'a, N, Ty>
impl<'a, N, Ty> Iterator for NeighborsDirected<'a, N, Ty> where
N: NodeTrait,
Ty: EdgeType, type Item = N;
pub fn neighbors_directed(
&self,
a: N,
dir: Direction
) -> NeighborsDirected<'_, N, Ty>ⓘNotable traits for NeighborsDirected<'a, N, Ty>
impl<'a, N, Ty> Iterator for NeighborsDirected<'a, N, Ty> where
N: NodeTrait,
Ty: EdgeType, type Item = N;
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 N
.
Return an iterator of target nodes with an edge starting from a
,
paired with their respective edge weights.
Directed
: Outgoing edges froma
.Undirected
: All edges from or toa
.
Produces an empty iterator if the node doesn’t exist.
Iterator element type is (N, &E)
.
pub fn edges_directed(
&self,
from: N,
dir: Direction
) -> EdgesDirected<'_, N, E, Ty>ⓘNotable traits for EdgesDirected<'a, N, E, Ty>
impl<'a, N, E, Ty> Iterator for EdgesDirected<'a, N, E, Ty> where
N: 'a + NodeTrait,
E: 'a,
Ty: EdgeType, type Item = (N, N, &'a E);
pub fn edges_directed(
&self,
from: N,
dir: Direction
) -> EdgesDirected<'_, N, E, Ty>ⓘNotable traits for EdgesDirected<'a, N, E, Ty>
impl<'a, N, E, Ty> Iterator for EdgesDirected<'a, N, E, Ty> where
N: 'a + NodeTrait,
E: 'a,
Ty: EdgeType, type Item = (N, N, &'a E);
Return an iterator of target nodes with an edge starting from a
,
paired with their respective edge weights.
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 doesn’t exist.
Iterator element type is (N, &E)
.
Return a reference to the edge weight connecting a
with b
, or
None
if the edge does not exist in the graph.
Return a mutable reference to the edge weight connecting a
with b
, or
None
if the edge does not exist in the graph.
Return an iterator over all edges of the graph with their weight in arbitrary order.
Iterator element type is (N, N, &E)
pub fn all_edges_mut(&mut self) -> AllEdgesMut<'_, N, E, Ty>ⓘNotable traits for AllEdgesMut<'a, N, E, Ty>
impl<'a, N, E, Ty> Iterator for AllEdgesMut<'a, N, E, Ty> where
N: 'a + NodeTrait,
E: 'a,
Ty: EdgeType, type Item = (N, N, &'a mut E);
pub fn all_edges_mut(&mut self) -> AllEdgesMut<'_, N, E, Ty>ⓘNotable traits for AllEdgesMut<'a, N, E, Ty>
impl<'a, N, E, Ty> Iterator for AllEdgesMut<'a, N, E, Ty> where
N: 'a + NodeTrait,
E: 'a,
Ty: EdgeType, type Item = (N, N, &'a mut E);
Return an iterator over all edges of the graph in arbitrary order, with a mutable reference to their weight.
Iterator element type is (N, N, &mut E)
Return a Graph
that corresponds to this GraphMap
.
- Note that node and edge indices in the
Graph
have nothing in common with theGraphMap
s node weightsN
. The node weightsN
are used as node weights in the resultingGraph
, too. - Note that the index type is user-chosen.
Computes in O(|V| + |E|) time (average).
Panics if the number of nodes or edges does not fit with the resulting graph’s index type.
Trait Implementations
Arbitrary
for GraphMap
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 features "quickcheck"
and "graphmap"
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
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
type NodeWeight = N
type EdgeWeight = E
Create a new empty GraphMap
.
Return the number of edges in the graph.
Return an upper bound of the edge indices in the graph (suitable for the size of a bitmap). Read more
Convert i
to an edge index. i
must be a valid value in the graph.
Extend the graph from an iterable of edges.
Nodes are inserted automatically to match the edges.
Extends a collection with the contents of an iterator. Read more
extend_one
)Extends a collection with exactly one element.
extend_one
)Reserves capacity in a collection for the given number of additional elements. Read more
fn from_elements<I>(iterable: I) -> Self where
Self: Sized,
I: IntoIterator<Item = Element<Self::NodeWeight, Self::EdgeWeight>>,
impl<N, E, Ty, Item> FromIterator<Item> for GraphMap<N, E, Ty> where
Item: IntoWeightedEdge<E, NodeId = N>,
N: NodeTrait,
Ty: EdgeType,
impl<N, E, Ty, Item> FromIterator<Item> for GraphMap<N, E, Ty> where
Item: IntoWeightedEdge<E, NodeId = N>,
N: NodeTrait,
Ty: EdgeType,
Create a new GraphMap
from an iterable of edges.
Creates a value from an iterator. Read more
The GraphMap
keeps an adjacency matrix internally.
Create the adjacency matrix
Return true if there is an edge from a
to b
, false otherwise. Read more
type EdgeType = Ty
type EdgeType = Ty
The kind edges in the graph.
Index GraphMap
by node pairs to access edge weights.
Index GraphMap
by node pairs to access edge weights.
impl<'a, N: 'a, E: 'a, Ty> IntoEdgeReferences for &'a GraphMap<N, E, Ty> where
N: NodeTrait,
Ty: EdgeType,
impl<'a, N: 'a, E: 'a, Ty> IntoEdgeReferences for &'a GraphMap<N, E, Ty> where
N: NodeTrait,
Ty: EdgeType,
type EdgeReferences = AllEdges<'a, N, E, Ty>
impl<'a, N: 'a, E: 'a, Ty> IntoEdgesDirected for &'a GraphMap<N, E, Ty> where
N: NodeTrait,
Ty: EdgeType,
impl<'a, N: 'a, E: 'a, Ty> IntoEdgesDirected for &'a GraphMap<N, E, Ty> where
N: NodeTrait,
Ty: EdgeType,
type EdgesDirected = EdgesDirected<'a, N, E, Ty>
type NeighborsDirected = NeighborsDirected<'a, N, Ty>
impl<'a, N, E: 'a, Ty> IntoNodeIdentifiers for &'a GraphMap<N, E, Ty> where
N: NodeTrait,
Ty: EdgeType,
impl<'a, N, E: 'a, Ty> IntoNodeIdentifiers for &'a GraphMap<N, E, Ty> where
N: NodeTrait,
Ty: EdgeType,
type NodeIdentifiers = NodeIdentifiers<'a, N, E, Ty>
impl<'a, N, E, Ty> IntoNodeReferences for &'a GraphMap<N, E, Ty> where
N: NodeTrait,
Ty: EdgeType,
impl<'a, N, E, Ty> IntoNodeReferences for &'a GraphMap<N, E, Ty> where
N: NodeTrait,
Ty: EdgeType,
type NodeReferences = NodeReferences<'a, N, E, Ty>
Return an upper bound of the node indices in the graph (suitable for the size of a bitmap). Read more
Convert i
to a node index. i
must be a valid value in the graph.
Auto Trait Implementations
impl<N, E, Ty> RefUnwindSafe for GraphMap<N, E, Ty> where
E: RefUnwindSafe,
N: RefUnwindSafe,
Ty: RefUnwindSafe,
impl<N, E, Ty> UnwindSafe for GraphMap<N, E, Ty> where
E: UnwindSafe,
N: UnwindSafe,
Ty: UnwindSafe,
Blanket Implementations
Mutably borrows from an owned value. Read more