libgraph

libgraph is a Rust crate providing a generic graph data structure and fundamental graph algorithms. It supports undirected graphs with optional metadata associated with edges, and includes various graph generation methods as well as common traversal algorithms like Depth-First Search.

Features

• Generic Graph Structure: Graph<Metadata> allows associating custom data with edges.
• Flexible Edge Handling: Add edges with or without metadata, check for existence, and retrieve metadata.
• Graph Generators: Create Hamiltonian cycles, minimum spanning trees, full (complete) graphs, and random graphs with specified density.
• Depth-First Search (DFS): Traverse graphs with a customizable visitor function.
• Tree Traversal: Specialized traversal for tree structures with a customizable visitor function.

Usage

Here's a simple example of creating a graph and performing a DFS:

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

fn main() {
    // Create a graph with 4 vertices
    let mut graph: Graph<()> = Graph::new(4)
        .add_edge((0, 1))
        .add_edge((0, 2))
        .add_edge((1, 3));

    println!("Graph has {} vertices", graph.num_vertices());

    // Perform a DFS starting from vertex 0
    let mut visited_vertices = Vec::new();
    dfs(&graph, 0, |v: Vertex| {
        visited_vertices.push(v);
        false // Continue traversal
    });

    println!("DFS from vertex 0 visited: {:?}", visited_vertices);

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

    if let Some(weight) = graph_with_weights.get_edge_metadata((0, 1)) {
        println!("Weight of edge (0, 1): {}", weight);
    }

    // Generate a random graph
    let mut rng = StdRng::seed_from_u64(42);
    let random_graph = Graph::random(5, 0.5, &mut rng);
    println!("Random graph has {} edges.", random_graph.edges().count());
}

Dependencies

This crate depends on:

• itertools
• rand
• serde

License

This project is licensed under the MIT License. See the LICENSE file for details.