In this tutorial, we will cover the following aspects of implementing a graph in Rust:

  1. Defining the graph structure.
  2. Adding vertices and edges.
  3. Implementing graph traversal methods (Depth-First Search and Breadth-First Search).
  4. Displaying the graph.

Let’s dive into the implementation.

Defining the Graph Structure

We will start by defining a Graph struct that holds vertices and edges. The vertices will be stored in a HashMap, where each vertex points to a vector of its adjacent vertices.

use std::collections::HashMap;

#[derive(Debug)]
struct Graph {
    edges: HashMap<String, Vec<String>>,
}

impl Graph {
    fn new() -> Self {
        Graph {
            edges: HashMap::new(),
        }
    }

    fn add_vertex(&mut self, vertex: String) {
        self.edges.entry(vertex).or_insert(Vec::new());
    }

    fn add_edge(&mut self, from: String, to: String) {
        self.edges.entry(from.clone()).or_insert(Vec::new()).push(to);
        self.edges.entry(to).or_insert(Vec::new()); // Ensure the destination vertex exists
    }
}

Explanation

  • The Graph struct contains a HashMap called edges, where the key is a vertex and the value is a vector of adjacent vertices.
  • The add_vertex method adds a vertex to the graph.
  • The add_edge method adds a directed edge from one vertex to another.

Adding Vertices and Edges

Now that we have our basic graph structure, let’s see how to add vertices and edges.

fn main() {
    let mut graph = Graph::new();

    graph.add_vertex("A".to_string());
    graph.add_vertex("B".to_string());
    graph.add_vertex("C".to_string());

    graph.add_edge("A".to_string(), "B".to_string());
    graph.add_edge("A".to_string(), "C".to_string());
    graph.add_edge("B".to_string(), "C".to_string());

    println!("{:?}", graph);
}

Output

When you run the above code, the output will be a representation of the graph:

Graph { edges: {"A": ["B", "C"], "B": ["C"], "C": []} }

Implementing Graph Traversal Methods

Depth-First Search (DFS)

DFS is a common algorithm used to traverse or search through a graph. Below is an implementation of DFS for our graph.

impl Graph {
    fn dfs(&self, start: &str, visited: &mut HashMap<String, bool>) {
        visited.insert(start.to_string(), true);
        println!("{}", start);

        if let Some(neighbors) = self.edges.get(start) {
            for neighbor in neighbors {
                if !visited.get(neighbor).unwrap_or(&false) {
                    self.dfs(neighbor, visited);
                }
            }
        }
    }

    fn depth_first_search(&self, start: &str) {
        let mut visited = HashMap::new();
        self.dfs(start, &mut visited);
    }
}

Breadth-First Search (BFS)

BFS explores all neighbors at the present depth before moving on to nodes at the next depth level. Here’s how we can implement BFS:

use std::collections::VecDeque;

impl Graph {
    fn breadth_first_search(&self, start: &str) {
        let mut visited = HashMap::new();
        let mut queue = VecDeque::new();

        visited.insert(start.to_string(), true);
        queue.push_back(start.to_string());

        while let Some(vertex) = queue.pop_front() {
            println!("{}", vertex);
            if let Some(neighbors) = self.edges.get(&vertex) {
                for neighbor in neighbors {
                    if !visited.get(neighbor).unwrap_or(&false) {
                        visited.insert(neighbor.clone(), true);
                        queue.push_back(neighbor.clone());
                    }
                }
            }
        }
    }
}

Displaying the Graph

It’s often useful to have a method to display the graph. Here’s a simple implementation:

impl Graph {
    fn display(&self) {
        for (vertex, neighbors) in &self.edges {
            println!("{} -> {:?}", vertex, neighbors);
        }
    }
}

Complete Example

Putting everything together, here’s the complete program:

use std::collections::{HashMap, VecDeque};

#[derive(Debug)]
struct Graph {
    edges: HashMap<String, Vec<String>>,
}

impl Graph {
    fn new() -> Self {
        Graph {
            edges: HashMap::new(),
        }
    }

    fn add_vertex(&mut self, vertex: String) {
        self.edges.entry(vertex).or_insert(Vec::new());
    }

    fn add_edge(&mut self, from: String, to: String) {
        self.edges.entry(from.clone()).or_insert(Vec::new()).push(to);
        self.edges.entry(to).or_insert(Vec::new());
    }

    fn dfs(&self, start: &str, visited: &mut HashMap<String, bool>) {
        visited.insert(start.to_string(), true);
        println!("{}", start);

        if let Some(neighbors) = self.edges.get(start) {
            for neighbor in neighbors {
                if !visited.get(neighbor).unwrap_or(&false) {
                    self.dfs(neighbor, visited);
                }
            }
        }
    }

    fn depth_first_search(&self, start: &str) {
        let mut visited = HashMap::new();
        self.dfs(start, &mut visited);
    }

    fn breadth_first_search(&self, start: &str) {
        let mut visited = HashMap::new();
        let mut queue = VecDeque::new();

        visited.insert(start.to_string(), true);
        queue.push_back(start.to_string());

        while let Some(vertex) = queue.pop_front() {
            println!("{}", vertex);
            if let Some(neighbors) = self.edges.get(&vertex) {
                for neighbor in neighbors {
                    if !visited.get(neighbor).unwrap_or(&false) {
                        visited.insert(neighbor.clone(), true);
                        queue.push_back(neighbor.clone());
                    }
                }
            }
        }
    }

    fn display(&self) {
        for (vertex, neighbors) in &self.edges {
            println!("{} -> {:?}", vertex, neighbors);
        }
    }
}

fn main() {
    let mut graph = Graph::new();
    graph.add_vertex("A".to_string());
    graph.add_vertex("B".to_string());
    graph.add_vertex("C".to_string());
    graph.add_edge("A".to_string(), "B".to_string());
    graph.add_edge("A".to_string(), "C".to_string());
    graph.add_edge("B".to_string(), "C".to_string());

    println!("Graph:");
    graph.display();

    println!("\nDepth First Search starting from A:");
    graph.depth_first_search("A");

    println!("\nBreadth First Search starting from A:");
    graph.breadth_first_search("A");
}

Conclusion

In this tutorial, we successfully implemented a simple graph data structure in Rust using an adjacency list. We created methods to add vertices and edges, traverse the graph using DFS and BFS, and display the graph. This foundational knowledge can be extended to more complex graph algorithms and applications.

Learn more with useful resources: