# Struct swc_fast_graph::digraph::FastGraphMap

source · `pub struct FastGraphMap<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> FastGraphMap<N, E, Ty>where
N: NodeTrait,
Ty: EdgeType,

### impl<N, E, Ty> FastGraphMap<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, from: N) -> Edges<'_, N, E, Ty> ⓘ

#### pub fn edges(&self, from: 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, &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.

## Trait Implementations§

source§### impl<N: Clone, E: Clone, Ty: Clone> Clone for FastGraphMap<N, E, Ty>

### impl<N: Clone, E: Clone, Ty: Clone> Clone for FastGraphMap<N, E, Ty>

source§#### fn clone(&self) -> FastGraphMap<N, E, Ty>

#### fn clone(&self) -> FastGraphMap<N, E, Ty>

1.0.0 · source§#### fn clone_from(&mut self, source: &Self)

#### fn clone_from(&mut self, source: &Self)

`source`

. Read moresource§### impl<N, E, Ty> Default for FastGraphMap<N, E, Ty>where
N: NodeTrait,
Ty: EdgeType,

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

Create a new empty `GraphMap`

.

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

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

### impl<N, E, Ty, Item> FromIterator<Item> for FastGraphMap<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<'a, N, E, Ty> IntoNeighbors for &'a FastGraphMap<N, E, Ty>where
N: Copy + Ord + Hash + 'a,
Ty: EdgeType,

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

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

### impl<'a, N, E, Ty> IntoNeighborsDirected for &'a FastGraphMap<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 FastGraphMap<N, E, Ty>where
N: NodeTrait,
Ty: EdgeType,

### impl<'a, N, E: 'a, Ty> IntoNodeIdentifiers for &'a FastGraphMap<N, E, Ty>where N: NodeTrait, Ty: EdgeType,

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

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

source§### impl<N, E, Ty> NodeCount for FastGraphMap<N, E, Ty>where
N: Copy + PartialEq,

### impl<N, E, Ty> NodeCount for FastGraphMap<N, E, Ty>where N: Copy + PartialEq,

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

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

### impl<N, E, Ty> NodeIndexable for FastGraphMap<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.