Struct AdjacencyList 

pub struct AdjacencyList<N, W = f64> { /* private fields */ }

A sparse graph representation backed by an adjacency list.

Node data is stored in a Vec<N>. Outgoing edges for each node are stored in a Vec<Vec<(NodeId, W)>> indexed by node position.

Directed vs Undirected

Use AdjacencyList::directed or AdjacencyList::undirected. For an undirected graph, add_edge(u, v, w) inserts both v into u’s list and u into v’s list automatically.

Complexity

Operation	Time
add_node	O(1) amortised
add_edge	O(1) amortised
neighbors	O(out-degree)
contains_edge	O(out-degree)
node_count	O(1)
edge_count	O(1)

Examples

use graph_core::{AdjacencyList, Graph};

let mut g: AdjacencyList<&str, f64> = AdjacencyList::directed();
let a = g.add_node("A");
let b = g.add_node("B");
let c = g.add_node("C");

g.add_edge(a, b, 1.0).unwrap();
g.add_edge(b, c, 2.0).unwrap();

assert_eq!(g.node_count(), 3);
assert_eq!(g.edge_count(), 2);
assert!(g.contains_edge(a, b));
assert!(!g.contains_edge(c, a));

Implementations

impl<N, W> AdjacencyList<N, W>

pub fn directed() -> Self

Creates an empty directed adjacency-list graph.

Examples

use graph_core::{AdjacencyList, Graph};

let g: AdjacencyList<()> = AdjacencyList::directed();
assert!(g.is_empty());

pub fn undirected() -> Self

Creates an empty undirected adjacency-list graph.

Examples

use graph_core::{AdjacencyList, Graph};

let mut g: AdjacencyList<()> = AdjacencyList::undirected();
let u = g.add_node(());
let v = g.add_node(());
g.add_edge(u, v, 1.0).unwrap();

// Both directions exist.
assert!(g.contains_edge(u, v));
assert!(g.contains_edge(v, u));

pub fn is_directed(&self) -> bool

Returns true if this graph is directed.

Examples

use graph_core::AdjacencyList;

let d: AdjacencyList<()> = AdjacencyList::directed();
assert!(d.is_directed());

let u: AdjacencyList<()> = AdjacencyList::undirected();
assert!(!u.is_directed());

impl<N, W> AdjacencyList<N, W>

pub fn node_data(&self, id: NodeId) -> Option<&N>

Returns a reference to the data stored at id, or None if not found.

Examples

use graph_core::{AdjacencyList, Graph};

let mut g: AdjacencyList<&str> = AdjacencyList::directed();
let id = g.add_node("hello");
assert_eq!(g.node_data(id), Some(&"hello"));

pub fn node_data_mut(&mut self, id: NodeId) -> Option<&mut N>

Returns a mutable reference to the data stored at id, or None if not found.

Examples

use graph_core::{AdjacencyList, Graph};

let mut g: AdjacencyList<u32> = AdjacencyList::directed();
let id = g.add_node(1);
*g.node_data_mut(id).unwrap() = 42;
assert_eq!(g.node_data(id), Some(&42));

Trait Implementations

impl<N: Clone, W: Clone> Clone for AdjacencyList<N, W>

fn clone(&self) -> AdjacencyList<N, W>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<N: Debug, W: Debug> Debug for AdjacencyList<N, W>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<N, W: Clone> Graph for AdjacencyList<N, W>

type NodeData = N

Data stored at each node (e.g. String, (), coordinates).

type Weight = W

Edge-weight type (e.g. f64, u32, ()).

type NodeIter<'a> = NodeIter where Self: 'a

Iterator over all NodeIds in the graph.

type NeighborIter<'a> = NeighborIter<'a, W> where Self: 'a

Iterator over (neighbour_id, &weight) pairs for one node.

fn add_node(&mut self, data: N) -> NodeId

Adds a node with the given data and returns its NodeId.

fn add_edge( &mut self, from: NodeId, to: NodeId, weight: W, ) -> Result<(), GraphError>

Adds a directed edge from from to to with weight.

fn remove_node(&mut self, id: NodeId) -> Option<N>

Removes the node at id and all edges incident to it.

fn node_count(&self) -> usize

Returns the number of nodes.

fn edge_count(&self) -> usize

Returns the number of directed edges.

fn contains_node(&self, id: NodeId) -> bool

Returns true if the graph contains a node with this id.

fn contains_edge(&self, from: NodeId, to: NodeId) -> bool

Returns true if there is a directed edge from from to to.

fn degree(&self, id: NodeId) -> usize

Returns the out-degree of node id (number of outgoing edges).

fn nodes(&self) -> NodeIter

Returns an iterator over all NodeIds in the graph.

fn neighbors(&self, id: NodeId) -> NeighborIter<'_, W>

Returns an iterator over (neighbour_id, &weight) for all outgoing edges of id.

fn all_edges(&self) -> Vec<Edge<Self::Weight>>

where Self::Weight: Clone,

Returns all edges in the graph as Edge<W> values.

fn is_empty(&self) -> bool

Returns true if the graph has no nodes.