Rust Tutorials: Cycle Detection (Weak) 🚀

Welcome back to CodeYourCraft! Today, we're going to dive into an exciting topic: Cycle Detection in Graphs using Rust. This tutorial is designed for both beginners and intermediates, so let's get started!

What is a Cycle in a Graph? 🎯

A cycle in a graph is a path that starts and ends on the same vertex. In other words, if you can follow a series of edges and end up back where you started, you've found a cycle.

Why is Cycle Detection Important? 📝

Cycle detection is crucial in many real-world applications, such as network analysis, database design, and compiler implementation. It helps ensure the efficiency and reliability of these systems.

Understanding Rust for Graphs 💡

Rust is a modern, safe, and concurrent systems programming language. For graphs, we'll be using the adjacency_list data structure, which is a collection of nodes and their adjacent nodes.

Creating an Adjacency List in Rust ✅

Here's a simple example of an adjacency list in Rust:

rust

use std::collections::HashMap;

type Node = i32;
type AdjacencyList = HashMap<Node, Vec<Node>>;

let mut graph: AdjacencyList = HashMap::new();

// Adding nodes and edges
graph.insert(1, vec![2, 3]);
graph.insert(2, vec![1, 4]);
graph.insert(3, vec![1, 5]);
graph.insert(4, vec![2]);
graph.insert(5, vec![3]);

In this example, we have a simple graph with 5 nodes (1, 2, 3, 4, 5) and their connections.

Detecting Cycles in a Graph 🎯

To detect cycles in a graph, we'll use Depth-First Search (DFS). During DFS, we mark each node we visit to prevent revisiting the same node again. If we encounter a node that is already marked, we've found a cycle.

rust

use std::fmt::Debug;

fn dfs<T: Copy + Debug>(
    node: &T,
    graph: &AdjacencyList,
    visited: &mut HashMap<T, bool>,
    recursion_stack: &mut Vec<T>,
) -> bool {
    // Mark the current node as visited
    visited.insert(*node, true);
    recursion_stack.push(*node);

    // If the node has edges, iterate through them
    if let Some(neighbors) = graph.get(node) {
        for neighbor in neighbors {
            // If the neighbor is not visited and we find a cycle, return true
            if !visited.get(neighbor).unwrap_or(&false) && dfs(neighbor, graph, visited, recursion_stack) {
                return true;
            }
            // If the neighbor is already on the recursion stack, we have a cycle
            if recursion_stack.contains(neighbor) {
                return true;
            }
        }
    }

    // If we've reached here, it means we've explored the current node and its neighbors without finding a cycle
    false
}

fn has_cycle<T: Copy + Debug>(graph: &AdjacencyList) -> bool {
    let mut visited = HashMap::new();
    let mut recursion_stack = Vec::new();

    // Iterate through all nodes in the graph
    for (node, neighbors) in graph {
        // If the node is not visited, start DFS
        if !visited.get(node).unwrap_or(&false) {
            if dfs(node, graph, &mut visited, &mut recursion_stack) {
                return true;
            }
        }
    }

    false
}

In the above code, the dfs function performs a depth-first search on the graph, and the has_cycle function checks if there's a cycle in the graph by calling dfs on each node.

Testing Our Cycle Detection Function ✅

Let's create a graph with a cycle and test our function:

rust

let mut graph: AdjacencyList = HashMap::new();

// Adding nodes and edges
graph.insert(1, vec![2, 3]);
graph.insert(2, vec![1, 4]);
graph.insert(3, vec![1, 5]);
graph.insert(4, vec![2, 5]); // This creates a cycle
graph.insert(5, vec![3, 4]);

assert!(has_cycle(&graph)); // This should return true

Quiz Time! 🎯

That's it for today's lesson on Cycle Detection in Graphs using Rust. Stay tuned for more exciting tutorials at CodeYourCraft! 🚀