Graph Algorithms

Graphs are data structures consisting of vertices (nodes) connected by edges. They model relationships: social networks, road maps, dependencies. In Rust, graphs challenge us with shared ownership since vertices can have multiple incoming edges.

Graphs in Rust must handle:

• Multiple references: A vertex can be pointed to by many edges
• Cycles: Unlike trees, graphs often have cycles
• Mutability: Adding edges while iterating requires care
• Performance: Graph algorithms need efficient adjacency lookups

use std::collections::{HashMap, HashSet, VecDeque, BinaryHeap};
use std::cmp::Ordering;

/// Adjacency list graph using indices
#[derive(Debug)]
pub struct Graph<T> {
    vertices: Vec<T>,
    /// adjacency[i] contains indices of vertices connected to vertex i
    adjacency: Vec<Vec<usize>>,
}

impl<T> Graph<T> {
    pub fn new() -> Self {
        Graph {
            vertices: Vec::new(),
            adjacency: Vec::new(),
        }
    }

    pub fn add_vertex(&mut self, value: T) -> usize {
        let index = self.vertices.len();
        self.vertices.push(value);
        self.adjacency.push(Vec::new());
        index
    }

    pub fn add_edge(&mut self, from: usize, to: usize) {
        if from < self.adjacency.len() && to < self.vertices.len() {
            self.adjacency[from].push(to);
        }
    }

    pub fn add_undirected_edge(&mut self, a: usize, b: usize) {
        self.add_edge(a, b);
        self.add_edge(b, a);
    }

    pub fn neighbors(&self, vertex: usize) -> &[usize] {
        &self.adjacency[vertex]
    }

    pub fn vertex(&self, index: usize) -> Option<&T> {
        self.vertices.get(index)
    }

    /// Breadth-First Search - finds shortest path in unweighted graph
    pub fn bfs(&self, start: usize, target: usize) -> Option<Vec<usize>> {
        if start >= self.vertices.len() || target >= self.vertices.len() {
            return None;
        }

        let mut visited = vec![false; self.vertices.len()];
        let mut parent = vec![None; self.vertices.len()];
        let mut queue = VecDeque::new();

        visited[start] = true;
        queue.push_back(start);

        while let Some(current) = queue.pop_front() {
            if current == target {
                // Reconstruct path
                return Some(self.reconstruct_path(&parent, start, target));
            }

            for &neighbor in &self.adjacency[current] {
                if !visited[neighbor] {
                    visited[neighbor] = true;
                    parent[neighbor] = Some(current);
                    queue.push_back(neighbor);
                }
            }
        }

        None // No path found
    }

    /// Depth-First Search - explores as deep as possible first
    pub fn dfs(&self, start: usize) -> Vec<usize> {
        let mut visited = vec![false; self.vertices.len()];
        let mut result = Vec::new();
        self.dfs_recursive(start, &mut visited, &mut result);
        result
    }

    fn dfs_recursive(&self, vertex: usize, visited: &mut [bool], result: &mut Vec<usize>) {
        if visited[vertex] {
            return;
        }

        visited[vertex] = true;
        result.push(vertex);

        for &neighbor in &self.adjacency[vertex] {
            self.dfs_recursive(neighbor, visited, result);
        }
    }

    fn reconstruct_path(&self, parent: &[Option<usize>], start: usize, target: usize) -> Vec<usize> {
        let mut path = Vec::new();
        let mut current = target;

        while current != start {
            path.push(current);
            current = parent[current].unwrap();
        }
        path.push(start);
        path.reverse();
        path
    }

    /// Topological sort using Kahn's algorithm
    pub fn topological_sort(&self) -> Option<Vec<usize>> {
        let n = self.vertices.len();
        let mut in_degree = vec![0usize; n];

        // Calculate in-degrees
        for neighbors in &self.adjacency {
            for &neighbor in neighbors {
                in_degree[neighbor] += 1;
            }
        }

        // Start with vertices that have no incoming edges
        let mut queue: VecDeque<usize> = in_degree
            .iter()
            .enumerate()
            .filter(|(_, &deg)| deg == 0)
            .map(|(i, _)| i)
            .collect();

        let mut result = Vec::with_capacity(n);

        while let Some(vertex) = queue.pop_front() {
            result.push(vertex);

            for &neighbor in &self.adjacency[vertex] {
                in_degree[neighbor] -= 1;
                if in_degree[neighbor] == 0 {
                    queue.push_back(neighbor);
                }
            }
        }

        // If we didn't visit all vertices, there's a cycle
        if result.len() == n {
            Some(result)
        } else {
            None
        }
    }
}

impl<T> Default for Graph<T> {
    fn default() -> Self {
        Self::new()
    }
}

/// Weighted graph for Dijkstra's algorithm
pub struct WeightedGraph {
    adjacency: Vec<Vec<(usize, u64)>>, // (neighbor, weight)
}

#[derive(Eq, PartialEq)]
struct State {
    cost: u64,
    vertex: usize,
}

impl Ord for State {
    fn cmp(&self, other: &Self) -> Ordering {
        // Reverse ordering for min-heap
        other.cost.cmp(&self.cost)
    }
}

impl PartialOrd for State {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl WeightedGraph {
    pub fn new(num_vertices: usize) -> Self {
        WeightedGraph {
            adjacency: vec![Vec::new(); num_vertices],
        }
    }

    pub fn add_edge(&mut self, from: usize, to: usize, weight: u64) {
        self.adjacency[from].push((to, weight));
    }

    /// Dijkstra's shortest path algorithm
    pub fn dijkstra(&self, start: usize, target: usize) -> Option<(u64, Vec<usize>)> {
        let n = self.adjacency.len();
        let mut dist = vec![u64::MAX; n];
        let mut parent = vec![None; n];
        let mut heap = BinaryHeap::new();

        dist[start] = 0;
        heap.push(State { cost: 0, vertex: start });

        while let Some(State { cost, vertex }) = heap.pop() {
            if vertex == target {
                // Reconstruct path
                let mut path = Vec::new();
                let mut current = target;
                while let Some(p) = parent[current] {
                    path.push(current);
                    current = p;
                }
                path.push(start);
                path.reverse();
                return Some((cost, path));
            }

            if cost > dist[vertex] {
                continue; // Already found a better path
            }

            for &(neighbor, weight) in &self.adjacency[vertex] {
                let next_cost = cost + weight;
                if next_cost < dist[neighbor] {
                    dist[neighbor] = next_cost;
                    parent[neighbor] = Some(vertex);
                    heap.push(State { cost: next_cost, vertex: neighbor });
                }
            }
        }

        None
    }
}

fn main() {
    // Unweighted graph example
    let mut graph = Graph::new();
    let a = graph.add_vertex("A");
    let b = graph.add_vertex("B");
    let c = graph.add_vertex("C");
    let d = graph.add_vertex("D");
    let e = graph.add_vertex("E");

    graph.add_edge(a, b);
    graph.add_edge(a, c);
    graph.add_edge(b, d);
    graph.add_edge(c, d);
    graph.add_edge(d, e);

    println!("DFS from A: {:?}", graph.dfs(a)); // [0, 1, 3, 4, 2]
    println!("BFS path A->E: {:?}", graph.bfs(a, e)); // Some([0, 1, 3, 4])
    println!("Topological sort: {:?}", graph.topological_sort());

    // Weighted graph example
    let mut weighted = WeightedGraph::new(5);
    weighted.add_edge(0, 1, 4);
    weighted.add_edge(0, 2, 1);
    weighted.add_edge(2, 1, 2);
    weighted.add_edge(1, 3, 1);
    weighted.add_edge(2, 3, 5);
    weighted.add_edge(3, 4, 3);

    if let Some((cost, path)) = weighted.dijkstra(0, 4) {
        println!("Shortest path 0->4: {:?} (cost: {})", path, cost);
    }
}

1. Index-based adjacency list: Avoids ownership issues by using usize indices
2. Vec>: Efficient adjacency representation
3. BinaryHeap for Dijkstra: Rust's standard library provides a max-heap; we reverse ordering for min-heap
4. No Rc/RefCell needed: Index approach is simpler and faster

| Algorithm | Use When |

|-----------|----------|

| BFS | Finding shortest path in unweighted graphs |

| DFS | Detecting cycles, topological sort, connected components |

| Dijkstra | Shortest path with non-negative weights |

| Bellman-Ford | Shortest path with negative weights (not shown) |

| A* | Shortest path with heuristic (pathfinding) |

• Route planning: Google Maps, navigation systems
• Social networks: Friend recommendations, influence propagation
• Package managers: Dependency resolution (Cargo!)
• Compilers: Control flow graphs, data flow analysis

1. Implement cycle detection for directed graphs
2. Add Bellman-Ford algorithm for negative weights
3. Implement A* pathfinding with a heuristic function
4. Create a function to find strongly connected components