petgraph/algo/
ford_fulkerson.rs

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

petgraph/algo/
ford_fulkerson.rs
