Struct AdjacencyMatrix 

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

A dense graph representation backed by a 2-D adjacency matrix.

Edge existence and weight are stored in a Vec<Vec<Option<W>>> matrix where matrix[i][j] is Some(weight) if there is an edge from i to j, or None otherwise.

When to prefer this over AdjacencyList

Property	AdjacencyList	AdjacencyMatrix
Space	O(V + E)	O(V²)
add_edge	O(1)	O(1)
contains_edge	O(deg)	O(1)
neighbors	O(deg)	O(V)

Use AdjacencyMatrix for dense graphs (many edges relative to V²) or when O(1) edge lookup is critical (e.g. Floyd-Warshall).

Examples

use graph_core::{AdjacencyMatrix, Graph};

let mut g: AdjacencyMatrix<&str, u32> = AdjacencyMatrix::directed();
let a = g.add_node("A");
let b = g.add_node("B");
g.add_edge(a, b, 5).unwrap();

assert!(g.contains_edge(a, b));
assert!(!g.contains_edge(b, a));

Implementations

impl<N, W> AdjacencyMatrix<N, W>

pub fn directed() -> AdjacencyMatrix<N, W>

Creates an empty directed adjacency-matrix graph.

Examples

use graph_core::{AdjacencyMatrix, Graph};

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

pub fn undirected() -> AdjacencyMatrix<N, W>

Creates an empty undirected adjacency-matrix graph.

Examples

use graph_core::{AdjacencyMatrix, Graph};

let mut g: AdjacencyMatrix<()> = AdjacencyMatrix::undirected();
let u = g.add_node(());
let v = g.add_node(());
g.add_edge(u, v, 1.0).unwrap();
assert!(g.contains_edge(v, u)); // symmetric

pub fn is_directed(&self) -> bool

Returns true if this graph is directed.

pub fn edge_weight(&self, from: NodeId, to: NodeId) -> Option<&W>

Returns a reference to the weight of edge from → to, or None if no such edge exists.

Examples

use graph_core::{AdjacencyMatrix, Graph};

let mut g: AdjacencyMatrix<()> = AdjacencyMatrix::directed();
let a = g.add_node(());
let b = g.add_node(());
g.add_edge(a, b, 3.0).unwrap();
assert_eq!(g.edge_weight(a, b), Some(&3.0));
assert_eq!(g.edge_weight(b, a), None);

Trait Implementations

impl<N, W> Clone for AdjacencyMatrix<N, W>

where N: Clone, W: Clone,

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

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<N, W> Debug for AdjacencyMatrix<N, W>

where N: Debug, W: Debug,

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

Formats the value using the given formatter.

impl<N, W> Graph for AdjacencyMatrix<N, W>

where W: Clone,

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 AdjacencyMatrix<N, W>: 'a

Iterator over all NodeIds in the graph.

type NeighborIter<'a> = NeighborIter<'a, W> where AdjacencyMatrix<N, W>: '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.