pub struct GraphMap<N, E, Ty, S = RandomState>where
S: BuildHasher,{ /* private fields */ }
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§
source§impl<N, E, Ty, S> GraphMap<N, E, Ty, S>
impl<N, E, Ty, S> GraphMap<N, E, Ty, S>
sourcepub fn with_capacity(nodes: usize, edges: usize) -> Selfwhere
S: Default,
pub fn with_capacity(nodes: usize, edges: usize) -> Selfwhere
S: Default,
Create a new GraphMap
with estimated capacity.
sourcepub fn with_capacity_and_hasher(nodes: usize, edges: usize, hasher: S) -> Selfwhere
S: Clone,
pub fn with_capacity_and_hasher(nodes: usize, edges: usize, hasher: S) -> Selfwhere
S: Clone,
Create a new GraphMap
with estimated capacity, and specified hasher.
sourcepub fn capacity(&self) -> (usize, usize)
pub fn capacity(&self) -> (usize, usize)
Return the current node and edge capacity of the graph.
sourcepub fn is_directed(&self) -> bool
pub fn is_directed(&self) -> bool
Whether the graph has directed edges.
sourcepub fn from_edges<I>(iterable: I) -> Self
pub fn from_edges<I>(iterable: I) -> Self
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),
]);
sourcepub fn node_count(&self) -> usize
pub fn node_count(&self) -> usize
Return the number of nodes in the graph.
sourcepub fn edge_count(&self) -> usize
pub fn edge_count(&self) -> usize
Return the number of edges in the graph.
sourcepub fn remove_node(&mut self, n: N) -> bool
pub fn remove_node(&mut self, n: N) -> bool
Return true
if node n
was removed.
Computes in O(V) time, due to the removal of edges with other nodes.
sourcepub fn contains_node(&self, n: N) -> bool
pub fn contains_node(&self, n: N) -> bool
Return true
if the node is contained in the graph.
sourcepub fn add_edge(&mut self, a: N, b: N, weight: E) -> Option<E>
pub fn add_edge(&mut self, a: N, b: N, weight: E) -> Option<E>
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"));
sourcepub fn remove_edge(&mut self, a: N, b: N) -> Option<E>
pub fn remove_edge(&mut self, a: N, b: N) -> Option<E>
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);
sourcepub fn contains_edge(&self, a: N, b: N) -> bool
pub fn contains_edge(&self, a: N, b: N) -> bool
Return true
if the edge connecting a
with b
is contained in the graph.
sourcepub fn nodes(&self) -> Nodes<'_, N> ⓘ
pub fn nodes(&self) -> Nodes<'_, N> ⓘ
Return an iterator over the nodes of the graph.
Iterator element type is N
.
sourcepub fn neighbors(&self, a: N) -> Neighbors<'_, N, Ty> ⓘ
pub fn neighbors(&self, a: N) -> Neighbors<'_, N, Ty> ⓘ
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
.
sourcepub fn neighbors_directed(
&self,
a: N,
dir: Direction,
) -> NeighborsDirected<'_, N, Ty> ⓘ
pub fn neighbors_directed( &self, a: N, dir: Direction, ) -> NeighborsDirected<'_, N, Ty> ⓘ
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
.
sourcepub fn edges(&self, a: N) -> Edges<'_, N, E, Ty, S> ⓘ
pub fn edges(&self, a: N) -> Edges<'_, N, E, Ty, S> ⓘ
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, N, &E)
.
sourcepub fn edges_directed(
&self,
a: N,
dir: Direction,
) -> EdgesDirected<'_, N, E, Ty, S> ⓘ
pub fn edges_directed( &self, a: N, dir: Direction, ) -> EdgesDirected<'_, N, E, Ty, S> ⓘ
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, N, &E)
.
sourcepub fn edge_weight(&self, a: N, b: N) -> Option<&E>
pub fn edge_weight(&self, a: N, b: N) -> Option<&E>
Return a reference to the edge weight connecting a
with b
, or
None
if the edge does not exist in the graph.
sourcepub fn edge_weight_mut(&mut self, a: N, b: N) -> Option<&mut E>
pub fn edge_weight_mut(&mut self, a: N, b: N) -> Option<&mut E>
Return a mutable reference to the edge weight connecting a
with b
, or
None
if the edge does not exist in the graph.
sourcepub fn all_edges(&self) -> AllEdges<'_, N, E, Ty> ⓘ
pub fn all_edges(&self) -> AllEdges<'_, N, E, Ty> ⓘ
Return an iterator over all edges of the graph with their weight in arbitrary order.
Iterator element type is (N, N, &E)
sourcepub fn all_edges_mut(&mut self) -> AllEdgesMut<'_, N, E, Ty> ⓘ
pub fn all_edges_mut(&mut self) -> AllEdgesMut<'_, N, E, Ty> ⓘ
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)
sourcepub fn into_graph<Ix>(self) -> Graph<N, E, Ty, Ix>where
Ix: IndexType,
pub fn into_graph<Ix>(self) -> Graph<N, E, Ty, Ix>where
Ix: IndexType,
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.
sourcepub fn from_graph<Ix>(graph: Graph<N, E, Ty, Ix>) -> Self
pub fn from_graph<Ix>(graph: Graph<N, E, Ty, Ix>) -> Self
Creates a GraphMap
that corresponds to the given Graph
.
Warning: Nodes with the same weight are merged and only the last parallel edge
is kept. Node and edge indices of the Graph
are lost. Only use this function
if the node weights are distinct and there are no parallel edges.
Computes in O(|V| + |E|) time (average).
Trait Implementations§
source§impl<N, E, Ty> Build for GraphMap<N, E, Ty>
impl<N, E, Ty> Build for GraphMap<N, E, Ty>
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: Clone, E: Clone, Ty: Clone, S> Clone for GraphMap<N, E, Ty, S>where
S: BuildHasher + Clone,
impl<N: Clone, E: Clone, Ty: Clone, S> Clone for GraphMap<N, E, Ty, S>where
S: BuildHasher + Clone,
source§impl<N, E, Ty> Create for GraphMap<N, E, Ty>
impl<N, E, Ty> Create for GraphMap<N, E, Ty>
fn with_capacity(nodes: usize, edges: usize) -> Self
source§impl<N, E, Ty, S> Data for GraphMap<N, E, Ty, S>
impl<N, E, Ty, S> Data for GraphMap<N, E, Ty, S>
type NodeWeight = N
type EdgeWeight = E
source§impl<N: Eq + Hash + Debug, E: Debug, Ty: EdgeType, S: BuildHasher> Debug for GraphMap<N, E, Ty, S>
impl<N: Eq + Hash + Debug, E: Debug, Ty: EdgeType, S: BuildHasher> Debug for GraphMap<N, E, Ty, S>
source§impl<N, E, Ty, S> EdgeCount for GraphMap<N, E, Ty, S>
impl<N, E, Ty, S> EdgeCount for GraphMap<N, E, Ty, S>
source§fn edge_count(&self) -> usize
fn edge_count(&self) -> usize
source§impl<N, E, Ty, S> EdgeIndexable for GraphMap<N, E, Ty, S>
impl<N, E, Ty, S> EdgeIndexable for GraphMap<N, E, Ty, S>
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, Item, S> Extend<Item> for GraphMap<N, E, Ty, S>
impl<N, E, Ty, Item, S> Extend<Item> for GraphMap<N, E, Ty, S>
Extend the graph from an iterable of edges.
Nodes are inserted automatically to match the edges.
source§fn extend<I>(&mut self, iterable: I)where
I: IntoIterator<Item = Item>,
fn extend<I>(&mut self, iterable: I)where
I: IntoIterator<Item = Item>,
source§fn extend_one(&mut self, item: A)
fn extend_one(&mut self, item: A)
extend_one
)source§fn extend_reserve(&mut self, additional: usize)
fn extend_reserve(&mut self, additional: usize)
extend_one
)source§impl<N, E, Ty> FromElements for GraphMap<N, E, Ty>
impl<N, E, Ty> FromElements for GraphMap<N, E, Ty>
fn from_elements<I>(iterable: I) -> Self
source§impl<N, E, Ty, Item, S> FromIterator<Item> for GraphMap<N, E, Ty, S>
impl<N, E, Ty, Item, S> FromIterator<Item> for GraphMap<N, E, Ty, S>
Create a new GraphMap
from an iterable of edges.
source§fn from_iter<I>(iterable: I) -> Selfwhere
I: IntoIterator<Item = Item>,
fn from_iter<I>(iterable: I) -> Selfwhere
I: IntoIterator<Item = Item>,
source§impl<N, E, Ty, S> GetAdjacencyMatrix for GraphMap<N, E, Ty, S>
impl<N, E, Ty, S> GetAdjacencyMatrix for GraphMap<N, E, Ty, S>
The GraphMap
keeps an adjacency matrix internally.
source§impl<N, E, Ty, S> Index<(N, N)> for GraphMap<N, E, Ty, S>
impl<N, E, Ty, S> Index<(N, N)> for GraphMap<N, E, Ty, S>
Index GraphMap
by node pairs to access edge weights.
source§impl<N, E, Ty, S> IndexMut<(N, N)> for GraphMap<N, E, Ty, S>
impl<N, E, Ty, S> IndexMut<(N, N)> for GraphMap<N, E, Ty, S>
Index GraphMap
by node pairs to access edge weights.
source§impl<'a, N, E: 'a, Ty, S> IntoEdgeReferences for &'a GraphMap<N, E, Ty, S>
impl<'a, N, E: 'a, Ty, S> IntoEdgeReferences for &'a GraphMap<N, E, Ty, S>
type EdgeRef = (N, N, &'a E)
type EdgeReferences = AllEdges<'a, N, E, Ty>
fn edge_references(self) -> Self::EdgeReferences
source§impl<'a, N, E: 'a, Ty, S> IntoEdgesDirected for &'a GraphMap<N, E, Ty, S>
impl<'a, N, E: 'a, Ty, S> IntoEdgesDirected for &'a GraphMap<N, E, Ty, S>
type EdgesDirected = EdgesDirected<'a, N, E, Ty, S>
fn edges_directed(self, a: Self::NodeId, dir: Direction) -> Self::EdgesDirected
source§impl<'a, N, E, Ty, S> IntoNeighbors for &'a GraphMap<N, E, Ty, S>
impl<'a, N, E, Ty, S> IntoNeighbors for &'a GraphMap<N, E, Ty, S>
source§impl<'a, N, E, Ty, S> IntoNeighborsDirected for &'a GraphMap<N, E, Ty, S>
impl<'a, N, E, Ty, S> IntoNeighborsDirected for &'a GraphMap<N, E, Ty, S>
type NeighborsDirected = NeighborsDirected<'a, N, Ty>
fn neighbors_directed(self, n: N, dir: Direction) -> Self::NeighborsDirected
source§impl<'a, N, E: 'a, Ty, S> IntoNodeIdentifiers for &'a GraphMap<N, E, Ty, S>
impl<'a, N, E: 'a, Ty, S> IntoNodeIdentifiers for &'a GraphMap<N, E, Ty, S>
type NodeIdentifiers = NodeIdentifiers<'a, N, E, Ty>
fn node_identifiers(self) -> Self::NodeIdentifiers
source§impl<'a, N, E, Ty, S> IntoNodeReferences for &'a GraphMap<N, E, Ty, S>
impl<'a, N, E, Ty, S> IntoNodeReferences for &'a GraphMap<N, E, Ty, S>
type NodeRef = (N, &'a N)
type NodeReferences = NodeReferences<'a, N, E, Ty>
fn node_references(self) -> Self::NodeReferences
source§impl<N, E, Ty, S> NodeIndexable for GraphMap<N, E, Ty, S>
impl<N, E, Ty, S> NodeIndexable for GraphMap<N, E, Ty, S>
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.impl<N, E, Ty, S> NodeCompactIndexable for GraphMap<N, E, Ty, S>
Auto Trait Implementations§
impl<N, E, Ty, S> Freeze for GraphMap<N, E, Ty, S>where
S: Freeze,
impl<N, E, Ty, S> RefUnwindSafe for GraphMap<N, E, Ty, S>
impl<N, E, Ty, S> Send for GraphMap<N, E, Ty, S>
impl<N, E, Ty, S> Sync for GraphMap<N, E, Ty, S>
impl<N, E, Ty, S> Unpin for GraphMap<N, E, Ty, S>
impl<N, E, Ty, S> UnwindSafe for GraphMap<N, E, Ty, S>
Blanket Implementations§
source§impl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere
T: ?Sized,
source§fn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
source§impl<T> CloneToUninit for Twhere
T: Clone,
impl<T> CloneToUninit for Twhere
T: Clone,
source§default unsafe fn clone_to_uninit(&self, dst: *mut T)
default unsafe fn clone_to_uninit(&self, dst: *mut T)
clone_to_uninit
)