Graph Algorithms

Kruskal's Minimum Spanning Tree

Category: Graph Time: O(E log E) Output: Minimum spanning tree edges

Kruskal's algorithm builds the minimum spanning tree by greedily adding the lowest-weight edge that doesn't form a cycle.

Union-Find with Compact Indices

Union-Find uses compact indices (0..n) rather than original node IDs — sparse IDs can be large integers that would make Union-Find arrays enormous:

fn kruskal_mst(&self) -> Vec<usize> {
    let n = self.compact_to_id.len();
    let mut parent: Vec<usize> = (0..n).collect();
    let mut rank = vec![0usize; n];

    // Collect and sort all edges by weight
    let mut edges: Vec<(f64, usize, usize)> = ...;
    edges.sort_by(|a, b| a.0.partial_cmp(&b.0).unwrap());

    let mut mst_edges = Vec::new();
    for (_, u_id, v_id) in edges {
        let u = id_to_compact[&u_id];
        let v = id_to_compact[&v_id];
        if find(&mut parent, u) != find(&mut parent, v) {
            union(&mut parent, &mut rank, u, v);
            mst_edges.extend([u_id, v_id]); // interleaved pairs
        }
    }
    mst_edges
}

Path compression and union by rank ensure near-O(1) amortized Find/Union operations.

Output Format

MST is returned as interleaved [u0, v0, u1, v1, ...] edge pairs. WASM's build_path_sets handles this special format, producing mst_edge_set for edge highlighting.

API Request

curl -X POST http://localhost:8000/process_file \
  -F "file=@graph.txt" \
  -F 'request={"algorithm":"kruskal","file_format":"edge_list"}'

Visualization

MST edges are highlighted in green. Animation reveals one MST edge per step.

---

PageRank

Category: Graph Time: O(V + E) per iteration × 30 iterations Output: Rank scores for all nodes

PageRank models the probability that a random surfer visits each node. Nodes with many high-ranked incoming links receive high scores.

Implementation Details

• Damping factor: d = 0.85 (industry standard)
• Iterations: 30 (sufficient for convergence on most graphs)
• Dangling node redistribution — nodes with no outgoing edges accumulate rank but never distribute it, causing rank to "leak". The implementation corrects this:

let dangling_sum: f64 = dangling_nodes.iter()
    .map(|&id| rank[&id])
    .sum::<f64>() * damping / n as f64;

for r in new_rank.values_mut() {
    *r += dangling_sum;
}

This preserves the stochastic property of the PageRank matrix and produces correct results on graphs with sink nodes.

API Request

curl -X POST http://localhost:8000/process_file \
  -F "file=@graph.txt" \
  -F 'request={"algorithm":"pagerank","file_format":"edge_list"}'

API Response

{
  "pagerank": {
    "0": 0.152,
    "1": 0.387,
    "2": 0.203,
    "3": 0.258
  },
  "mpi_processes": 2
}

Visualization

Nodes are colored on a cyan → violet gradient based on normalized rank score:

• Low rank → #22d3ee (cyan)
• High rank → #7c3aed (violet)

The results panel shows a horizontal bar chart of the top 15 nodes by rank.

---

Strongly Connected Components (Kosaraju's)

Category: Graph Time: O(V + E) Output: Component assignment for all nodes

Kosaraju's algorithm finds all strongly connected components (SCCs) — maximal sets of nodes where every node is reachable from every other.

Iterative Two-Pass DFS

Recursive DFS causes stack overflows for graphs with paths longer than ~8,000 nodes (default Rust stack: ~8MB). The implementation uses an explicit stack with (node, post: bool) tuples to simulate the two DFS phases iteratively:

// First pass: build finish order on forward graph
let mut stack = vec![(start, false)];
while let Some((node, post)) = stack.pop() {
    if post {
        finish_order.push(node);
        continue;
    }
    if visited.insert(node) {
        stack.push((node, true)); // re-push for post-order
        for &(neighbor, _) in &self.adjacency[&node] {
            if !visited.contains(&neighbor) {
                stack.push((neighbor, false));
            }
        }
    }
}

// Second pass: DFS on reversed graph in reverse finish order
// Each DFS tree is one SCC

This exactly mimics recursive DFS post-order without risking stack overflow, making it safe for graphs of any size.

API Request

curl -X POST http://localhost:8000/process_file \
  -F "file=@graph.txt" \
  -F 'request={"algorithm":"scc","file_format":"edge_list"}'

API Response

{
  "scc": [[0, 1, 2], [3, 4], [5]],
  "mpi_processes": 2
}

Visualization

Each SCC gets a distinct color from a 7-color palette. The results panel lists components sorted by size (largest first).

---

Topological Sort

Category: Graph Time: O(V + E) Constraint: Graph must be a DAG (Directed Acyclic Graph) Output: Nodes in topological order, or null if a cycle exists

Kahn's Algorithm

Uses BFS-based approach (Kahn's algorithm) rather than DFS-based topological sort:

fn topological_sort(&self) -> Option<Vec<usize>> {
    // Compute in-degree for all nodes
    let mut in_degree: HashMap<usize, usize> = ...;

    // Start with all nodes of in-degree 0
    let mut queue: VecDeque<usize> = in_degree.iter()
        .filter(|(_, &d)| d == 0)
        .map(|(&id, _)| id)
        .collect();

    let mut order = Vec::new();
    while let Some(node) = queue.pop_front() {
        order.push(node);
        for &(neighbor, _) in &self.adjacency[&node] {
            let d = in_degree.get_mut(&neighbor).unwrap();
            *d -= 1;
            if *d == 0 { queue.push_back(neighbor); }
        }
    }

    // If not all nodes processed, graph has a cycle
    if order.len() == self.adjacency.len() {
        Some(order)
    } else {
        None
    }
}

If None is returned, the graph contains a cycle and topological ordering is impossible.

API Request

curl -X POST http://localhost:8000/process_file \
  -F "file=@graph.txt" \
  -F 'request={"algorithm":"topological_sort","file_format":"edge_list"}'

API Response

{
  "path": [0, 2, 1, 4, 3],
  "mpi_processes": 2
}

Returns null for path if a cycle is detected.

Visualization

Nodes are highlighted in topological order — the animation shows nodes becoming "available" (in-degree drops to 0) in sequence. The results panel shows the first 50 nodes in order.