Algorithms Overview

Nine graph algorithms are fully implemented in src/graph.rs. All run distributed across the MPI cluster and animate step-by-step in the browser.

Algorithm Matrix

Algorithm	Category	Time Complexity	Output
BFS	Traversal	O(V + E)	Visit order
DFS	Traversal	O(V + E)	Visit order
Dijkstra	Shortest Path	O((V + E) log V)	Path + distances
A*	Shortest Path	O(E log V)	Path
Bellman-Ford	Shortest Path	O(V × E)	Path + distances + cycle detection
Kruskal MST	Graph	O(E log E)	MST edges
PageRank	Graph	O(V + E) per iter × 30	Rank scores
SCC (Kosaraju)	Graph	O(V + E)	Component assignments
Topological Sort	Graph	O(V + E)	Ordered nodes

MPI Execution Model

All algorithms use the replicated computation model:

1. The master serializes the full graph + task as a GraphTask struct (bincode)
2. Each worker receives the full graph and executes the algorithm independently
3. The master collects results and merges them — preferring the worker result to demonstrate remote execution
4. Results are returned as JSON with mpi_processes and mpi_mode fields

This works correctly because the algorithms require the full graph structure. For billion-edge graphs, proper partitioning (METIS-style) would be needed.

Result Types

Traversal Results (BFS, DFS)

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

Path is the visit order. Animation reveals nodes one-by-one.

Shortest Path Results (Dijkstra, A*, Bellman-Ford)

{
  "path": [0, 2, 3, 4],
  "distances": { "0": 0.0, "1": 2.5, "2": 1.0, "3": 1.5, "4": 3.5 },
  "has_negative_cycle": false,
  "mpi_processes": 2,
  "mpi_mode": "distributed"
}

Path is the actual shortest route. The distance table shows all reachable nodes.

MST Result (Kruskal)

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

Path is interleaved [u0, v0, u1, v1, ...] edge pairs. Animation reveals one edge per step.

PageRank Result

{
  "pagerank": { "0": 0.15, "1": 0.38, "2": 0.21, ... },
  "mpi_processes": 2
}

Scores are used by compute_node_styles to color nodes on a cyan→violet gradient.

SCC Result

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

Each inner array is one strongly connected component. Components are color-coded with a 7-color palette.

Topological Sort Result

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

Returns null if a cycle is detected (i.e., the graph is not a DAG).

Explore the Algorithms

• Traversal Algorithms → — BFS and DFS implementation details
• Shortest Path Algorithms → — Dijkstra, A*, and Bellman-Ford
• Graph Algorithms → — Kruskal, PageRank, SCC, and Topological Sort