`pub struct GraphMap<N, E, Ty> { /* 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 and`E`

for edges, called*weights*. - The node weight
`N`

must implement`Copy`

and will be used as node identifier, duplicated into several places in the data structure. It must be suitable as a hash table key (implementing`Eq + Hash`

). The node type must also implement`Ord`

so that the implementation can order the pair (`a`

,`b`

) for an edge connecting any two nodes`a`

and`b`

. `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> GraphMap<N, E, Ty>where
N: NodeTrait,
Ty: EdgeType,

### impl<N, E, Ty> GraphMap<N, E, Ty>where N: NodeTrait, Ty: EdgeType,

source#### pub fn with_capacity(nodes: usize, edges: usize) -> Self

#### pub fn with_capacity(nodes: usize, edges: usize) -> Self

Create a new `GraphMap`

with estimated capacity.

source#### pub fn capacity(&self) -> (usize, usize)

#### pub fn capacity(&self) -> (usize, usize)

Return the current node and edge capacity of the graph.

source#### pub fn is_directed(&self) -> bool

#### pub fn is_directed(&self) -> bool

Whether the graph has directed edges.

source#### pub fn from_edges<I>(iterable: I) -> Selfwhere
I: IntoIterator,
I::Item: IntoWeightedEdge<E, NodeId = N>,

#### pub fn from_edges<I>(iterable: I) -> Selfwhere 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),
]);
```

source#### pub fn node_count(&self) -> usize

#### pub fn node_count(&self) -> usize

Return the number of nodes in the graph.

source#### pub fn edge_count(&self) -> usize

#### pub fn edge_count(&self) -> usize

Return the number of edges in the graph.

source#### pub 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.

source#### pub 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.

source#### pub 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"));
```

source#### pub 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);
```

source#### pub 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.

source#### pub 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`

.

source#### pub 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 from`a`

.`Undirected`

: All edges from or to`a`

.

Produces an empty iterator if the node doesn’t exist.

Iterator element type is `N`

.

source#### pub 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 from`a`

.`Directed`

,`Incoming`

: All edges to`a`

.`Undirected`

: All edges from or to`a`

.

Produces an empty iterator if the node doesn’t exist.

Iterator element type is `N`

.

source#### pub fn edges(&self, a: N) -> Edges<'_, N, E, Ty> ⓘ

#### pub fn edges(&self, a: N) -> Edges<'_, N, E, Ty> ⓘ

Return an iterator of target nodes with an edge starting from `a`

,
paired with their respective edge weights.

`Directed`

: Outgoing edges from`a`

.`Undirected`

: All edges from or to`a`

.

Produces an empty iterator if the node doesn’t exist.

Iterator element type is `(N, N, &E)`

.

source#### pub fn edges_directed(
&self,
a: N,
dir: Direction
) -> EdgesDirected<'_, N, E, Ty> ⓘ

#### pub fn edges_directed( &self, a: N, dir: Direction ) -> EdgesDirected<'_, N, E, Ty> ⓘ

Return an iterator of target nodes with an edge starting from `a`

,
paired with their respective edge weights.

`Directed`

,`Outgoing`

: All edges from`a`

.`Directed`

,`Incoming`

: All edges to`a`

.`Undirected`

,`Outgoing`

: All edges connected to`a`

, with`a`

being the source of each edge.`Undirected`

,`Incoming`

: All edges connected to`a`

, with`a`

being the target of each edge.

Produces an empty iterator if the node doesn’t exist.

Iterator element type is `(N, N, &E)`

.

source#### pub 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.

source#### pub 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.

source#### pub 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)`

source#### pub 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)`

source#### pub 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 the`GraphMap`

s node weights`N`

. The node weights`N`

are used as node weights in the resulting`Graph`

, 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.

source#### pub fn from_graph<Ix>(graph: Graph<N, E, Ty, Ix>) -> Selfwhere
Ix: IndexType,
E: Clone,

#### pub fn from_graph<Ix>(graph: Graph<N, E, Ty, Ix>) -> Selfwhere Ix: IndexType, E: Clone,

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>where
Ty: EdgeType,
N: NodeTrait,

### impl<N, E, Ty> Build for GraphMap<N, E, Ty>where Ty: EdgeType, N: NodeTrait,

#### 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> Create for GraphMap<N, E, Ty>where
Ty: EdgeType,
N: NodeTrait,

### impl<N, E, Ty> Create for GraphMap<N, E, Ty>where Ty: EdgeType, N: NodeTrait,

#### fn with_capacity(nodes: usize, edges: usize) -> Self

source§### impl<N, E, Ty> Data for GraphMap<N, E, Ty>where
N: Copy + PartialEq,
Ty: EdgeType,

### impl<N, E, Ty> Data for GraphMap<N, E, Ty>where N: Copy + PartialEq, Ty: EdgeType,

#### type NodeWeight = N

#### type EdgeWeight = E

source§### impl<N, E, Ty> Default for GraphMap<N, E, Ty>where
N: NodeTrait,
Ty: EdgeType,

### impl<N, E, Ty> Default for GraphMap<N, E, Ty>where N: NodeTrait, Ty: EdgeType,

Create a new empty `GraphMap`

.

source§### impl<N, E, Ty> EdgeCount for GraphMap<N, E, Ty>where
N: NodeTrait,
Ty: EdgeType,

### impl<N, E, Ty> EdgeCount for GraphMap<N, E, Ty>where N: NodeTrait, Ty: EdgeType,

source§#### fn edge_count(&self) -> usize

#### fn edge_count(&self) -> usize

source§### impl<N, E, Ty> EdgeIndexable for GraphMap<N, E, Ty>where
N: NodeTrait,
Ty: EdgeType,

### impl<N, E, Ty> EdgeIndexable for GraphMap<N, E, Ty>where N: NodeTrait, Ty: EdgeType,

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> Extend<Item> for GraphMap<N, E, Ty>where
Item: IntoWeightedEdge<E, NodeId = N>,
N: NodeTrait,
Ty: EdgeType,

### impl<N, E, Ty, Item> Extend<Item> for GraphMap<N, E, Ty>where Item: IntoWeightedEdge<E, NodeId = N>, N: NodeTrait, Ty: EdgeType,

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>where
Ty: EdgeType,
N: NodeTrait,

### impl<N, E, Ty> FromElements for GraphMap<N, E, Ty>where Ty: EdgeType, N: NodeTrait,

#### fn from_elements<I>(iterable: I) -> Selfwhere Self: Sized, I: IntoIterator<Item = Element<Self::NodeWeight, Self::EdgeWeight>>,

source§### 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.

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> GetAdjacencyMatrix for GraphMap<N, E, Ty>where
N: Copy + Ord + Hash,
Ty: EdgeType,

### impl<N, E, Ty> GetAdjacencyMatrix for GraphMap<N, E, Ty>where N: Copy + Ord + Hash, Ty: EdgeType,

The `GraphMap`

keeps an adjacency matrix internally.

source§### impl<N, E, Ty> Index<(N, N)> for GraphMap<N, E, Ty>where
N: NodeTrait,
Ty: EdgeType,

### impl<N, E, Ty> Index<(N, N)> for GraphMap<N, E, Ty>where N: NodeTrait, Ty: EdgeType,

Index `GraphMap`

by node pairs to access edge weights.

source§### impl<N, E, Ty> IndexMut<(N, N)> for GraphMap<N, E, Ty>where
N: NodeTrait,
Ty: EdgeType,

### impl<N, E, Ty> IndexMut<(N, N)> for GraphMap<N, E, Ty>where N: NodeTrait, Ty: EdgeType,

Index `GraphMap`

by node pairs to access edge weights.

source§### impl<'a, N, E: 'a, Ty> IntoEdgeReferences for &'a GraphMap<N, E, Ty>where
N: NodeTrait + 'a,
Ty: EdgeType,

### impl<'a, N, E: 'a, Ty> IntoEdgeReferences for &'a GraphMap<N, E, Ty>where N: NodeTrait + 'a, Ty: EdgeType,

#### 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> IntoEdges for &'a GraphMap<N, E, Ty>where
N: NodeTrait + 'a,
Ty: EdgeType,

### impl<'a, N, E: 'a, Ty> IntoEdges for &'a GraphMap<N, E, Ty>where N: NodeTrait + 'a, Ty: EdgeType,

source§### impl<'a, N, E: 'a, Ty> IntoEdgesDirected for &'a GraphMap<N, E, Ty>where
N: NodeTrait + 'a,
Ty: EdgeType,

### impl<'a, N, E: 'a, Ty> IntoEdgesDirected for &'a GraphMap<N, E, Ty>where N: NodeTrait + 'a, Ty: EdgeType,

#### type EdgesDirected = EdgesDirected<'a, N, E, Ty>

#### fn edges_directed(self, a: Self::NodeId, dir: Direction) -> Self::EdgesDirected

source§### impl<'a, N, E, Ty> IntoNeighbors for &'a GraphMap<N, E, Ty>where
N: Copy + Ord + Hash + 'a,
Ty: EdgeType,

### impl<'a, N, E, Ty> IntoNeighbors for &'a GraphMap<N, E, Ty>where N: Copy + Ord + Hash + 'a, Ty: EdgeType,

source§### impl<'a, N, E, Ty> IntoNeighborsDirected for &'a GraphMap<N, E, Ty>where
N: Copy + Ord + Hash + 'a,
Ty: EdgeType,

### impl<'a, N, E, Ty> IntoNeighborsDirected for &'a GraphMap<N, E, Ty>where N: Copy + Ord + Hash + 'a, Ty: EdgeType,

#### type NeighborsDirected = NeighborsDirected<'a, N, Ty>

#### fn neighbors_directed(self, n: N, dir: Direction) -> Self::NeighborsDirected

source§### 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>

#### fn node_identifiers(self) -> Self::NodeIdentifiers

source§### 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 NodeRef = (N, &'a N)

#### type NodeReferences = NodeReferences<'a, N, E, Ty>

#### fn node_references(self) -> Self::NodeReferences

source§### impl<N, E, Ty> NodeCount for GraphMap<N, E, Ty>where
N: NodeTrait,
Ty: EdgeType,

### impl<N, E, Ty> NodeCount for GraphMap<N, E, Ty>where N: NodeTrait, Ty: EdgeType,

#### fn node_count(&self) -> usize

source§### impl<N, E, Ty> NodeIndexable for GraphMap<N, E, Ty>where
N: NodeTrait,
Ty: EdgeType,

### impl<N, E, Ty> NodeIndexable for GraphMap<N, E, Ty>where N: NodeTrait, Ty: EdgeType,

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.