Struct DiGraph 

pub struct DiGraph {
    pub n: usize,
    pub adj: Vec<Vec<(usize, i64)>>,
}

A simple directed graph with Rust-level algorithms.

Fields

n: usize

Number of vertices (0..n).

adj: Vec<Vec<(usize, i64)>>

Adjacency list: adj[u] = list of (v, weight) neighbors.

Implementations

impl DiGraph

pub fn new(n: usize) -> Self

Create a new directed graph with n vertices.

pub fn add_edge(&mut self, u: usize, v: usize, w: i64)

Add a directed edge u → v with weight w.

pub fn bfs(&self, s: usize) -> Vec<usize>

BFS from source s; returns distances (usize::MAX if unreachable).

pub fn dfs(&self, s: usize) -> Vec<usize>

DFS from source s; returns DFS finish order.

pub fn topo_sort(&self) -> Option<Vec<usize>>

Topological sort (Kahn’s algorithm). Returns None if cycle exists.

pub fn scc(&self) -> Vec<Vec<usize>>

Strongly connected components (Kosaraju’s algorithm).

pub fn dijkstra(&self, s: usize) -> (Vec<i64>, Vec<Option<usize>>)

Dijkstra’s shortest paths from source s (non-negative weights only). Returns (dist, parent) where dist[v] = shortest distance, parent[v] = predecessor.

pub fn bellman_ford(&self, s: usize) -> Option<Vec<i64>>

Bellman-Ford shortest paths from source s (allows negative weights). Returns None if negative cycle is reachable.

pub fn floyd_warshall(&self) -> Vec<Vec<i64>>

Floyd-Warshall all-pairs shortest paths. Returns distance matrix (i64::MAX/2 = unreachable).

pub fn is_dag(&self) -> bool

Is this graph a DAG?

pub fn reachable_count(&self, s: usize) -> usize

Count vertices reachable from s.

Trait Implementations

impl Clone for DiGraph

fn clone(&self) -> DiGraph

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for DiGraph

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.