Struct Graph 

pub struct Graph<Metadata = ()> {
    pub adj_list: Vec<HashMap<usize, Metadata>>,
}

A generic undirected graph data structure.

The graph is represented using an adjacency list, where each vertex maps to a HashMap of its neighbors. The Metadata type parameter allows associating arbitrary data with each edge. If no metadata is needed, () can be used as the Metadata type.

Examples

use libgraph::Graph;

let graph: Graph<()> = Graph::new(3)
    .add_edge((0, 1))
    .add_edge((1, 2));

assert_eq!(graph.num_vertices(), 3);
assert!(graph.has_edge((0, 1)));

Graph with metadata:

use libgraph::Graph;

let graph_with_weights = Graph::new(3)
    .add_edge_with_metadata((0, 1), 10)
    .add_edge_with_metadata((1, 2), 20);

assert_eq!(graph_with_weights.get_edge_metadata((0, 1)), Some(&10));

Fields

adj_list: Vec<HashMap<usize, Metadata>>

Implementations

impl<T> Graph<T>

pub fn new(num_vertices: usize) -> Self

Creates a new graph with num_vertices vertices and no edges.

Each vertex is initially isolated.

Arguments

• num_vertices - The number of vertices this graph should contain.

Examples

use libgraph::Graph;

let graph: Graph<()> = Graph::new(5);
assert_eq!(graph.num_vertices(), 5);
assert_eq!(graph.edges().count(), 0);

pub fn edges(&self) -> impl Iterator<Item = Edge>

Returns an iterator over all unique undirected edges in the graph.

Each edge (u, v) is returned only once, where u < v.

Examples

use libgraph::Graph;

let graph = Graph::new(3)
    .add_edge((0, 1))
    .add_edge((1, 2));

let mut edges: Vec<(usize, usize)> = graph.edges().collect();
edges.sort();
assert_eq!(edges, vec![(0, 1), (1, 2)]);

pub fn num_vertices(&self) -> usize

Returns the number of vertices in the graph.

Examples

use libgraph::Graph;

let graph: Graph<()> = Graph::new(10);
assert_eq!(graph.num_vertices(), 10);

pub fn has_edge(&self, edge: Edge) -> bool

Checks if an undirected edge (u, v) exists in the graph.

The order of u and v does not matter, i.e., has_edge((u, v)) is equivalent to has_edge((v, u)).

Arguments

• edge - A tuple (u, v) representing the two vertices of the edge.

Examples

use libgraph::Graph;

let graph = Graph::new(3).add_edge((0, 1));

assert!(graph.has_edge((0, 1)));
assert!(graph.has_edge((1, 0))); // Order does not matter
assert!(!graph.has_edge((0, 2)));

pub fn get_edge_metadata(&self, edge: Edge) -> Option<&T>

Returns a reference to the metadata associated with the edge (u, v), if the edge exists.

The order of u and v does not matter.

Arguments

• edge - A tuple (u, v) representing the two vertices of the edge.

Returns

An Option<&T> which is Some(metadata) if the edge exists, and None otherwise.

Examples

use libgraph::Graph;

let graph = Graph::new(3).add_edge_with_metadata((0, 1), "weight_1".to_string());

assert_eq!(graph.get_edge_metadata((0, 1)), Some(&"weight_1".to_string()));
assert_eq!(graph.get_edge_metadata((1, 0)), Some(&"weight_1".to_string()));
assert_eq!(graph.get_edge_metadata((0, 2)), None);

impl<Metadata> Graph<Metadata>

where Metadata: Clone,

pub fn add_edge_with_metadata(self, (u, v): Edge, metadata: Metadata) -> Self

Adds an undirected edge between vertices u and v with associated metadata.

If an edge already exists between u and v, its metadata will be updated. Self-loops (edges from a vertex to itself) are not supported and will be ignored.

Arguments

• edge - A tuple (u, v) representing the two vertices of the edge.
• metadata - The metadata to associate with the edge.

Returns

The Graph instance, allowing for method chaining.

Panics

Panics if u or v are out of bounds for the graph’s number of vertices.

Examples

use libgraph::Graph;

let graph = Graph::new(3)
    .add_edge_with_metadata((0, 1), 10)
    .add_edge_with_metadata((1, 2), 20);

assert_eq!(graph.get_edge_metadata((0, 1)), Some(&10));
assert_eq!(graph.get_edge_metadata((1, 2)), Some(&20));

// Update metadata for an existing edge
let updated_graph = graph.add_edge_with_metadata((0, 1), 100);
assert_eq!(updated_graph.get_edge_metadata((0, 1)), Some(&100));

pub fn edges_with_metadata(&self) -> impl Iterator<Item = (Edge, Metadata)>

Returns an iterator over all unique undirected edges and their associated metadata.

Each edge (u, v) and its metadata is returned only once, where u < v.

Examples

use libgraph::Graph;

let graph = Graph::new(3)
    .add_edge_with_metadata((0, 1), 10)
    .add_edge_with_metadata((1, 2), 20);

let mut edges_with_meta: Vec<((usize, usize), i32)> = graph.edges_with_metadata().collect();
edges_with_meta.sort_by_key(|k| k.0);
assert_eq!(edges_with_meta, vec![((0, 1), 10), ((1, 2), 20)]);

impl Graph<()>

pub fn hamiltonian_cycle(num_vertices: usize, rng: &mut impl Rng) -> Self

Generates a graph that forms a Hamiltonian cycle with num_vertices vertices.

A Hamiltonian cycle visits every vertex exactly once and returns to the starting vertex.

Arguments

• num_vertices - The number of vertices in the cycle.
• rng - A mutable reference to a random number generator implementing rand::Rng.

Returns

A Graph<()> instance representing a Hamiltonian cycle.

Examples

use libgraph::Graph;
use rand::rngs::StdRng;
use rand::SeedableRng;

let mut rng = StdRng::seed_from_u64(42);
let graph = Graph::hamiltonian_cycle(5, &mut rng);
assert_eq!(graph.num_vertices(), 5);
assert_eq!(graph.edges().count(), 5);
// Further checks could ensure it's a valid cycle.

pub fn minimum_spanning_tree(num_vertices: usize, rng: &mut impl Rng) -> Self

Generates a minimum spanning tree (MST) graph with num_vertices vertices using a randomized Prufer sequence approach.

A minimum spanning tree connects all vertices with the minimum possible total edge weight. In this unweighted context, it’s any tree spanning all vertices.

Arguments

• num_vertices - The number of vertices in the tree.
• rng - A mutable reference to a random number generator implementing rand::Rng.

Returns

A Graph<()> instance representing a minimum spanning tree.

Examples

use libgraph::Graph;
use rand::rngs::StdRng;
use rand::SeedableRng;

let mut rng = StdRng::seed_from_u64(42);
let graph = Graph::minimum_spanning_tree(5, &mut rng);
assert_eq!(graph.num_vertices(), 5);
assert_eq!(graph.edges().count(), 4); // A tree with N vertices has N-1 edges

pub fn full(num_vertices: usize) -> Self

Generates a full (complete) graph with num_vertices vertices.

In a complete graph, every distinct pair of vertices is connected by a unique edge.

Arguments

• num_vertices - The number of vertices in the graph.

Returns

A Graph<()> instance representing a complete graph.

Examples

use libgraph::Graph;

let graph = Graph::full(4);
assert_eq!(graph.num_vertices(), 4);
// A complete graph with N vertices has N*(N-1)/2 edges
assert_eq!(graph.edges().count(), 6); // 4 * 3 / 2 = 6

pub fn random(num_vertices: usize, density: f64, rng: &mut impl Rng) -> Self

Generates a random graph using the Erdos-Renyi G(n, p) model.

Each possible edge is included in the graph with probability density.

Arguments

• num_vertices - The number of vertices in the graph.
• density - The probability p (between 0.0 and 1.0) for each edge to exist.
• rng - A mutable reference to a random number generator implementing rand::Rng.

Returns

A Graph<()> instance representing a random graph.

Examples

use libgraph::Graph;
use rand::rngs::StdRng;
use rand::SeedableRng;

let mut rng = StdRng::seed_from_u64(42);
let graph = Graph::random(10, 0.3, &mut rng);
assert_eq!(graph.num_vertices(), 10);
// Number of edges will vary based on random generation, but can be checked.
println!("Random graph with 10 vertices and 0.3 density has {} edges.", graph.edges().count());

pub fn add_edge(self, (u, v): Edge) -> Self

Adds an undirected edge between vertices u and v without any metadata.

This is a convenience method for Graph<()> instances. If an edge already exists, this method does nothing. Self-loops (edges from a vertex to itself) are not supported and will be ignored.

Arguments

• edge - A tuple (u, v) representing the two vertices of the edge.

Returns

The Graph instance, allowing for method chaining.

Panics

Panics if u or v are out of bounds for the graph’s number of vertices.

Examples

use libgraph::Graph;

let graph = Graph::new(3)
    .add_edge((0, 1))
    .add_edge((1, 2));

assert!(graph.has_edge((0, 1)));
assert!(graph.has_edge((1, 2)));
assert!(!graph.has_edge((0, 2)));

Trait Implementations

impl<'de, Metadata> Deserialize<'de> for Graph<Metadata>

where Metadata: Deserialize<'de>,

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<Metadata> Serialize for Graph<Metadata>

where Metadata: Serialize,

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.