petgraph/algo/maximum_flow/
ford_fulkerson.rs

1use alloc::{collections::VecDeque, vec, vec::Vec};
2use core::ops::Sub;
3
4use crate::{
5    algo::PositiveMeasure,
6    data::DataMap,
7    prelude::Direction,
8    visit::{
9        EdgeCount, EdgeIndexable, EdgeRef, IntoEdges, IntoEdgesDirected, NodeCount, NodeIndexable,
10        VisitMap, Visitable,
11    },
12};
13
14fn residual_capacity<G>(
15    network: G,
16    edge: G::EdgeRef,
17    vertex: G::NodeId,
18    flow: G::EdgeWeight,
19) -> G::EdgeWeight
20where
21    G: NodeIndexable + IntoEdges,
22    G::EdgeWeight: Sub<Output = G::EdgeWeight> + PositiveMeasure,
23{
24    if vertex == edge.source() {
25        // backward edge
26        flow
27    } else if vertex == edge.target() {
28        // forward edge
29        *edge.weight() - flow
30    } else {
31        let end_point = NodeIndexable::to_index(&network, vertex);
32        panic!("Illegal endpoint {}", end_point);
33    }
34}
35
36/// Gets the other endpoint of graph edge, if any, otherwise panics.
37fn other_endpoint<G>(network: G, edge: G::EdgeRef, vertex: G::NodeId) -> G::NodeId
38where
39    G: NodeIndexable + IntoEdges,
40{
41    if vertex == edge.source() {
42        edge.target()
43    } else if vertex == edge.target() {
44        edge.source()
45    } else {
46        let end_point = NodeIndexable::to_index(&network, vertex);
47        panic!("Illegal endpoint {}", end_point);
48    }
49}
50
51/// Tells whether there is an augmented path in the graph
52fn has_augmented_path<G>(
53    network: G,
54    source: G::NodeId,
55    destination: G::NodeId,
56    edge_to: &mut [Option<G::EdgeRef>],
57    flows: &[G::EdgeWeight],
58) -> bool
59where
60    G: NodeCount + IntoEdgesDirected + NodeIndexable + EdgeIndexable + Visitable,
61    G::EdgeWeight: Sub<Output = G::EdgeWeight> + PositiveMeasure,
62{
63    let mut visited = network.visit_map();
64    let mut queue = VecDeque::new();
65    visited.visit(source);
66    queue.push_back(source);
67
68    while let Some(vertex) = queue.pop_front() {
69        let out_edges = network.edges_directed(vertex, Direction::Outgoing);
70        let in_edges = network.edges_directed(vertex, Direction::Incoming);
71        for edge in out_edges.chain(in_edges) {
72            let next = other_endpoint(&network, edge, vertex);
73            let edge_index: usize = EdgeIndexable::to_index(&network, edge.id());
74            let residual_cap = residual_capacity(&network, edge, next, flows[edge_index]);
75            if !visited.is_visited(&next) && (residual_cap > G::EdgeWeight::zero()) {
76                visited.visit(next);
77                edge_to[NodeIndexable::to_index(&network, next)] = Some(edge);
78                if destination == next {
79                    return true;
80                }
81                queue.push_back(next);
82            }
83        }
84    }
85    false
86}
87
88fn adjust_residual_flow<G>(
89    network: G,
90    edge: G::EdgeRef,
91    vertex: G::NodeId,
92    flow: G::EdgeWeight,
93    delta: G::EdgeWeight,
94) -> G::EdgeWeight
95where
96    G: NodeIndexable + IntoEdges,
97    G::EdgeWeight: Sub<Output = G::EdgeWeight> + PositiveMeasure,
98{
99    if vertex == edge.source() {
100        // backward edge
101        flow - delta
102    } else if vertex == edge.target() {
103        // forward edge
104        flow + delta
105    } else {
106        let end_point = NodeIndexable::to_index(&network, vertex);
107        panic!("Illegal endpoint {}", end_point);
108    }
109}
110
111/// [Ford-Fulkerson][ff] algorithm in the [Edmonds-Karp][ek] variation.
112/// Computes the [maximum flow] from `source` to `destination` in a weighted directed graph.
113///
114/// See also [`maximum_flow`][max flow mod] module for other maximum flow algorithms.
115///
116/// # Arguments
117/// * `network`: a wieghted directed graph.
118/// * `source`: a stream *source* node.
119/// * `destination`: a stream *sink* node.
120///
121/// # Returns
122/// Returns a tuple of two values:
123/// * `N::EdgeWeight`: computed maximum flow;
124/// * `Vec<N::EdgeWeight>`: the flow of each edge. The vector is indexed by the graph's edge indices.
125///
126/// # Complexity
127/// * Time complexity: **O(|V||E|²)**.
128/// * Auxiliary space: **O(|V| + |E|)**.
129///
130/// where **|V|** is the number of nodes and **|E|** is the number of edges.
131///
132/// [maximum flow]: https://en.wikipedia.org/wiki/Maximum_flow_problem
133/// [ff]: https://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm
134/// [ek]: https://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm
135/// [max flow mod]: index.html
136///
137/// # Example
138/// ```rust
139/// use petgraph::Graph;
140/// use petgraph::algo::ford_fulkerson;
141/// // Example from CLRS book
142/// let mut graph = Graph::<u8, u8>::new();
143/// let source = graph.add_node(0);
144/// let _ = graph.add_node(1);
145/// let _ = graph.add_node(2);
146/// let _ = graph.add_node(3);
147/// let _ = graph.add_node(4);
148/// let destination = graph.add_node(5);
149/// graph.extend_with_edges(&[
150///    (0, 1, 16),
151///    (0, 2, 13),
152///    (1, 2, 10),
153///    (1, 3, 12),
154///    (2, 1, 4),
155///    (2, 4, 14),
156///    (3, 2, 9),
157///    (3, 5, 20),
158///    (4, 3, 7),
159///    (4, 5, 4),
160/// ]);
161/// let (max_flow, _) = ford_fulkerson(&graph, source, destination);
162/// assert_eq!(23, max_flow);
163/// ```
164pub fn ford_fulkerson<G>(
165    network: G,
166    source: G::NodeId,
167    destination: G::NodeId,
168) -> (G::EdgeWeight, Vec<G::EdgeWeight>)
169where
170    G: NodeCount
171        + EdgeCount
172        + IntoEdgesDirected
173        + EdgeIndexable
174        + NodeIndexable
175        + DataMap
176        + Visitable,
177    G::EdgeWeight: Sub<Output = G::EdgeWeight> + PositiveMeasure,
178{
179    let mut edge_to = vec![None; network.node_count()];
180    let mut flows = vec![G::EdgeWeight::zero(); network.edge_bound()];
181    let mut max_flow = G::EdgeWeight::zero();
182    while has_augmented_path(&network, source, destination, &mut edge_to, &flows) {
183        let mut path_flow = G::EdgeWeight::max();
184
185        // Find the bottleneck capacity of the path
186        let mut vertex = destination;
187        let mut vertex_index = NodeIndexable::to_index(&network, vertex);
188        while let Some(edge) = edge_to[vertex_index] {
189            let edge_index = EdgeIndexable::to_index(&network, edge.id());
190            let residual_capacity = residual_capacity(&network, edge, vertex, flows[edge_index]);
191            // Minimum between the current path flow and the residual capacity.
192            path_flow = if path_flow > residual_capacity {
193                residual_capacity
194            } else {
195                path_flow
196            };
197            vertex = other_endpoint(&network, edge, vertex);
198            vertex_index = NodeIndexable::to_index(&network, vertex);
199        }
200
201        // Update the flow of each edge along the path
202        let mut vertex = destination;
203        let mut vertex_index = NodeIndexable::to_index(&network, vertex);
204        while let Some(edge) = edge_to[vertex_index] {
205            let edge_index = EdgeIndexable::to_index(&network, edge.id());
206            flows[edge_index] =
207                adjust_residual_flow(&network, edge, vertex, flows[edge_index], path_flow);
208            vertex = other_endpoint(&network, edge, vertex);
209            vertex_index = NodeIndexable::to_index(&network, vertex);
210        }
211        max_flow = max_flow + path_flow;
212    }
213    (max_flow, flows)
214}
petgraph/algo/maximum_flow/ford_fulkerson.rs

petgraph/algo/maximum_flow/
ford_fulkerson.rs
