Struct Graph

Source

pub struct Graph<N, E, Ty = Directed> { /* private fields */ }

Expand description

Graph<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 existance in constant time.

§`Graph` 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 alias UndirectedGraph for convenience.

Graph does not allow parallel edges, but self loops are allowed.

Implementations§

Source §

impl<N, E, Ty> Graph<N, E, Ty>
where N: NodeTrait, Ty: EdgeType,

Source

pub fn new() -> Self

Create a new Graph instance.

§Examples

use safe_graph::Graph;

let graph: Graph<i32, f32> = Graph::new();

Source

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

Create a new Graph with estimated capacity.

Source

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

Return the current node and edge capacity of the graph.

Source

pub fn edge_key(a: N, b: N) -> (N, N)

Use their natural order to map the node pair (a, b) to a canonical edge id.

Source

pub fn is_directed(&self) -> bool

Whether the graph has directed edges.

Source

pub fn from_edges(iterable: I) -> Self
where I: IntoIterator, I::Item: IntoWeightedEdge<E, NodeId = N>,

Create a new Graph 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.

§Examples

use safe_graph::Graph;

// Create a new directed Graph.
// Use a type hint to have `()` be the edge weight type.
let gr = Graph::<_, ()>::from_edges(&[
    (0, 1), (0, 2), (0, 3),
    (1, 2), (1, 3),
    (2, 3),
]);

Source

pub fn node_count(&self) -> usize

Return the number of nodes in the graph.

Source

pub fn edge_count(&self) -> usize

Return the number of edges in the graph.

Source

pub fn clear(&mut self)

Remove all nodes and edges

Source

pub fn add_node(&mut self, n: N) -> N

Add node n to the graph.

Source

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>

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

§Examples

// Create a Graph with directed edges, and add one edge to it
use safe_graph::Graph;

let mut g: Graph<_, _> = Graph::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 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> ⓘ

Return an iterator over the nodes of the graph.

Iterator element type is N.

Source

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>

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