graph_flow/
ford_fulkerson.rs

1//! Ford-Fulkerson maximum flow via DFS augmenting paths.
2
3use crate::FlowGraph;
4
5/// Computes the **maximum flow** from `source` to `sink` using the
6/// Ford-Fulkerson algorithm with DFS augmenting paths.
7///
8/// Repeatedly finds an augmenting path from `source` to `sink` in the
9/// residual graph using DFS, then pushes the bottleneck capacity along that
10/// path. Terminates when no augmenting path exists.
11///
12/// # When to use this vs [`edmonds_karp`]
13///
14/// Ford-Fulkerson with DFS is simple but has a worst-case complexity of
15/// O(E · max_flow) — it can be very slow if max_flow is large and augmenting
16/// paths carry only 1 unit of flow each. Prefer [`edmonds_karp`] for general
17/// use since BFS augmentation guarantees polynomial time regardless of
18/// capacity values.
19///
20/// Ford-Fulkerson is primarily useful as an educational reference and for
21/// small graphs or integer capacities where max_flow is bounded.
22///
23/// # Arguments
24///
25/// - `graph` — a mutable [`FlowGraph`]; flow values are updated in place.
26/// - `source` — index of the source node.
27/// - `sink` — index of the sink node.
28///
29/// # Returns
30///
31/// The total maximum flow value sent from `source` to `sink`.
32///
33/// # Complexity
34///
35/// O(E · max_flow). Not guaranteed to terminate with irrational capacities
36/// (use integer or rational capacities).
37///
38/// # Examples
39///
40/// ```
41/// use graph_flow::{FlowGraph, ford_fulkerson};
42///
43/// // Simple two-path network:
44/// //   0 --10-- 1 --10-- 3
45/// //   |                 |
46/// //   +---5--- 2 --5----+
47/// let mut g = FlowGraph::new(4);
48/// g.add_edge(0, 1, 10.0);
49/// g.add_edge(0, 2, 5.0);
50/// g.add_edge(1, 3, 10.0);
51/// g.add_edge(2, 3, 5.0);
52///
53/// let flow = ford_fulkerson(&mut g, 0, 3);
54/// assert_eq!(flow, 15.0);
55/// ```
56///
57/// [`edmonds_karp`]: crate::edmonds_karp::edmonds_karp
58pub fn ford_fulkerson(graph: &mut FlowGraph, source: usize, sink: usize) -> f64 {
59    // Trivial case: no flow is possible when source and sink are the same node.
60    if source == sink {
61        return 0.0;
62    }
63
64    let mut total_flow = 0.0;
65
66    loop {
67        // Find an augmenting path via DFS and push flow along it.
68        let mut visited = vec![false; graph.node_count()];
69        let pushed = dfs_augment(graph, source, sink, f64::INFINITY, &mut visited);
70
71        if pushed == 0.0 {
72            break; // No augmenting path found — done.
73        }
74        total_flow += pushed;
75    }
76
77    total_flow
78}
79
80/// DFS that finds one augmenting path and returns the bottleneck flow pushed.
81///
82/// Returns `0.0` if no path from `node` to `sink` exists in the residual
83/// graph.
84fn dfs_augment(
85    graph: &mut FlowGraph,
86    node: usize,
87    sink: usize,
88    pushed: f64,
89    visited: &mut Vec<bool>,
90) -> f64 {
91    if node == sink {
92        return pushed;
93    }
94
95    visited[node] = true;
96
97    // Iterate by index so we can call push_flow after the recursive call
98    // without holding a borrow on graph.adjacency.
99    for edge_idx in 0..graph.adjacency[node].len() {
100        let neighbour = graph.adjacency[node][edge_idx].to;
101        let residual = graph.adjacency[node][edge_idx].residual();
102
103        if visited[neighbour] || residual <= 0.0 {
104            continue;
105        }
106
107        let bottleneck = dfs_augment(graph, neighbour, sink, pushed.min(residual), visited);
108
109        if bottleneck > 0.0 {
110            graph.push_flow(node, edge_idx, bottleneck);
111            return bottleneck;
112        }
113    }
114
115    0.0
116}
graph_flow/ford_fulkerson.rs

graph_flow/
ford_fulkerson.rs
