# Struct petgraph::graph::Graph
[−]
[src]

pub struct Graph<N, E, Ty = Directed, Ix: IndexType = DefIndex> { // some fields omitted }

**Graph<N, E, Ty, Ix>** is a graph datastructure using an adjacency list representation.

**Graph** is parameterized over the node weight **N**, edge weight **E**,
edge type **Ty** that determines whether the graph has directed edges or not,
and **Ix** which is the index type used.

Based on the graph implementation in rustc.

The graph maintains unique indices for nodes and edges, and node and edge weights may be accessed mutably.

**NodeIndex** and **EdgeIndex** are types that act as references to nodes and edges,
but these are only stable across certain operations. **Removing nodes or edges may shift
other indices**. Adding to the graph keeps
all indices stable, but removing a node will force the last node to shift its index to
take its place. Similarly, removing an edge shifts the index of the last edge.

The fact that the node and edge indices in the graph are numbered in a compact interval from
0 to *n* - 1 simplifies some graph algorithms.

The **Ix** parameter is **u32** by default. The goal is that you can ignore this parameter
completely unless you need a very big graph -- then you can use **usize**.

## Methods

`impl<N, E> Graph<N, E, Directed>`

`fn new() -> Self`

Create a new **Graph** with directed edges.

`impl<N, E> Graph<N, E, Undirected>`

`fn new_undirected() -> Self`

Create a new **Graph** with undirected edges.

`impl<N, E, Ty = Directed, Ix = DefIndex> Graph<N, E, Ty, Ix> where Ty: EdgeType, Ix: IndexType`

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

Create a new **Graph** with estimated capacity.

`fn node_count(&self) -> usize`

Return the number of nodes (vertices) in the graph.

`fn edge_count(&self) -> usize`

Return the number of edges in the graph.

Computes in **O(1)** time.

`fn clear(&mut self)`

Remove all nodes and edges

`fn is_directed(&self) -> bool`

Return whether the graph has directed edges or not.

`fn into_edge_type<NewTy>(self) -> Graph<N, E, NewTy, Ix> where NewTy: EdgeType`

Cast the graph as either undirected or directed. No edge adjustments are done.

Computes in **O(1)** time.

`fn add_node(&mut self, w: N) -> NodeIndex<Ix>`

Add a node (also called vertex) with weight **w** 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 node_weight(&self, a: NodeIndex<Ix>) -> Option<&N>`

Access node weight for node **a**.

`fn node_weight_mut(&mut self, a: NodeIndex<Ix>) -> Option<&mut N>`

Access node weight for node **a**.

`fn neighbors(&self, a: NodeIndex<Ix>) -> Neighbors<E, Ix>`

Return an iterator of all nodes with an edge starting from **a**.

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

Iterator element type is **NodeIndex**.

`fn neighbors_directed(&self, a: NodeIndex<Ix>, dir: EdgeDirection) -> Neighbors<E, Ix>`

Return an iterator of all neighbors that have an edge between them and **a**,
in the specified direction.
If the graph is undirected, this is equivalent to *.neighbors(a)*.

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

Iterator element type is **NodeIndex**.

`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 is undirected, this is equivalent to *.neighbors(a)*.

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

Iterator element type is **NodeIndex**.

`fn edges(&self, a: NodeIndex<Ix>) -> Edges<E, Ix>`

Return an iterator over the neighbors of node **a**, paired with their respective edge
weights.

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

Iterator element type is **(NodeIndex , &'a E)**.

`fn edges_both(&self, a: NodeIndex<Ix>) -> Edges<E, Ix>`

Return an iterator over the edgs from **a** to its neighbors, then *to* **a** from its
neighbors.

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

Iterator element type is **(NodeIndex , &'a E)**.

`fn add_edge(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>, weight: E) -> EdgeIndex<Ix>`

Add an edge from **a** to **b** to the graph, with its edge weight.

**Note:** **Graph** allows adding parallel (“duplicate”) edges. If you want
to avoid this, use *.update_edge(a, b, weight)* instead.

Computes in **O(1)** time.

Return the index of the new edge.

**Panics** if any of the nodes don't exist.

**Panics** if the Graph is at the maximum number of edges for its index
type.

`fn update_edge(&mut self, 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.

Computes in **O(e')** time, where **e'** is the number of edges
connected to the vertices **a** (and **b**).

Return the index of the affected edge.

**Panics** if any of the nodes don't exist.

`fn edge_weight(&self, e: EdgeIndex<Ix>) -> Option<&E>`

Access the edge weight for **e**.

`fn edge_weight_mut(&mut self, e: EdgeIndex<Ix>) -> Option<&mut E>`

Access the edge weight for **e** mutably.

`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**.

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

Computes in **O(e')** time, where **e'** is the size of four particular edge lists, for
the vertices of **e** and the vertices of another affected edge.

`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 the vertices **a** (and **b**).

`fn find_edge_undirected(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> Option<(EdgeIndex<Ix>, EdgeDirection)>`

Lookup an edge between **a** and **b**, in either direction.

If the graph is undirected, then this is equivalent to *.find_edge()*.

Return the edge index and its directionality, with *Outgoing* meaning
from **a** to **b** and *Incoming* the reverse,
or **None** if the edge does not exist.

`fn reverse(&mut self)`

Reverse the direction of all edges

`fn raw_nodes(&self) -> &[Node<N, Ix>]`

Access the internal node array

`fn raw_edges(&self) -> &[Edge<E, Ix>]`

Access the internal edge array

`fn first_edge(&self, a: NodeIndex<Ix>, dir: EdgeDirection) -> Option<EdgeIndex<Ix>>`

Accessor for data structure internals: the first edge in the given direction.

`fn next_edge(&self, e: EdgeIndex<Ix>, dir: EdgeDirection) -> Option<EdgeIndex<Ix>>`

Accessor for data structure internals: the next edge for the given direction.

`fn without_edges(&self, dir: EdgeDirection) -> WithoutEdges<N, Ty, Ix>`

Return an iterator over either the nodes without edges to them or from them.

The nodes in *.without_edges(Incoming)* are the initial nodes and
*.without_edges(Outgoing)* are the terminals.

For an undirected graph, the initials/terminals are just the vertices without edges.

The whole iteration computes in **O(|V|)** time.

## Trait Implementations

`impl<N, E, Ty, Ix> Debug for Graph<N, E, Ty, Ix> where N: Debug, E: Debug, Ty: EdgeType, Ix: IndexType`

`impl<N, E, Ty, Ix> Index<NodeIndex<Ix>> for Graph<N, E, Ty, Ix> where Ty: EdgeType, Ix: IndexType`

Index the **Graph** by **NodeIndex** to access node weights.

**Panics** if the node doesn't exist.

`impl<N, E, Ty, Ix> IndexMut<NodeIndex<Ix>> for Graph<N, E, Ty, Ix> where Ty: EdgeType, Ix: IndexType`

Index the **Graph** by **NodeIndex** to access node weights.

**Panics** if the node doesn't exist.

`impl<N, E, Ty, Ix> Index<EdgeIndex<Ix>> for Graph<N, E, Ty, Ix> where Ty: EdgeType, Ix: IndexType`

Index the **Graph** by **EdgeIndex** to access edge weights.

**Panics** if the edge doesn't exist.

`impl<N, E, Ty, Ix> IndexMut<EdgeIndex<Ix>> for Graph<N, E, Ty, Ix> where Ty: EdgeType, Ix: IndexType`

Index the **Graph** by **EdgeIndex** to access edge weights.

**Panics** if the edge doesn't exist.