petgraph/algo/
ford_fulkerson.rs

1use std::{collections::VecDeque, ops::Sub};
2
3use crate::{
4    data::DataMap,
5    visit::{
6        EdgeCount, EdgeIndexable, IntoEdges, IntoEdgesDirected, NodeCount, NodeIndexable, VisitMap,
7        Visitable,
8    },
9};
10
11use super::{EdgeRef, PositiveMeasure};
12use crate::prelude::Direction;
13
14fn residual_capacity<N>(
15    network: N,
16    edge: N::EdgeRef,
17    vertex: N::NodeId,
18    flow: N::EdgeWeight,
19) -> N::EdgeWeight
20where
21    N: NodeIndexable + IntoEdges,
22    N::EdgeWeight: Sub<Output = N::EdgeWeight> + PositiveMeasure,
23{
24    if vertex == edge.source() {
25        // backward edge
26        flow
27    } else if vertex == edge.target() {
28        // forward edge
29        return *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<N>(network: N, edge: N::EdgeRef, vertex: N::NodeId) -> N::NodeId
38where
39    N: 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<N>(
53    network: N,
54    source: N::NodeId,
55    destination: N::NodeId,
56    edge_to: &mut [Option<N::EdgeRef>],
57    flows: &[N::EdgeWeight],
58) -> bool
59where
60    N: NodeCount + IntoEdgesDirected + NodeIndexable + EdgeIndexable + Visitable,
61    N::EdgeWeight: Sub<Output = N::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 > N::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<N>(
89    network: N,
90    edge: N::EdgeRef,
91    vertex: N::NodeId,
92    flow: N::EdgeWeight,
93    delta: N::EdgeWeight,
94) -> N::EdgeWeight
95where
96    N: NodeIndexable + IntoEdges,
97    N::EdgeWeight: Sub<Output = N::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/// \[Generic\] Ford-Fulkerson algorithm.
112///
113/// Computes the [maximum flow][ff] of a weighted directed graph.
114///
115/// If it terminates, it returns the maximum flow and also the computed edge flows.
116///
117/// [ff]: https://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm
118///
119/// # Example
120/// ```rust
121/// use petgraph::Graph;
122/// use petgraph::algo::ford_fulkerson;
123/// // Example from CLRS book
124/// let mut graph = Graph::<u8, u8>::new();
125/// let source = graph.add_node(0);
126/// let _ = graph.add_node(1);
127/// let _ = graph.add_node(2);
128/// let _ = graph.add_node(3);
129/// let _ = graph.add_node(4);
130/// let destination = graph.add_node(5);
131/// graph.extend_with_edges(&[
132///    (0, 1, 16),
133///    (0, 2, 13),
134///    (1, 2, 10),
135///    (1, 3, 12),
136///    (2, 1, 4),
137///    (2, 4, 14),
138///    (3, 2, 9),
139///    (3, 5, 20),
140///    (4, 3, 7),
141///    (4, 5, 4),
142/// ]);
143/// let (max_flow, _) = ford_fulkerson(&graph, source, destination);
144/// assert_eq!(23, max_flow);
145/// ```
146pub fn ford_fulkerson<N>(
147    network: N,
148    source: N::NodeId,
149    destination: N::NodeId,
150) -> (N::EdgeWeight, Vec<N::EdgeWeight>)
151where
152    N: NodeCount
153        + EdgeCount
154        + IntoEdgesDirected
155        + EdgeIndexable
156        + NodeIndexable
157        + DataMap
158        + Visitable,
159    N::EdgeWeight: Sub<Output = N::EdgeWeight> + PositiveMeasure,
160{
161    let mut edge_to = vec![None; network.node_count()];
162    let mut flows = vec![N::EdgeWeight::zero(); network.edge_count()];
163    let mut max_flow = N::EdgeWeight::zero();
164    while has_augmented_path(&network, source, destination, &mut edge_to, &flows) {
165        let mut path_flow = N::EdgeWeight::max();
166
167        // Find the bottleneck capacity of the path
168        let mut vertex = destination;
169        let mut vertex_index = NodeIndexable::to_index(&network, vertex);
170        while let Some(edge) = edge_to[vertex_index] {
171            let edge_index = EdgeIndexable::to_index(&network, edge.id());
172            let residual_capacity = residual_capacity(&network, edge, vertex, flows[edge_index]);
173            // Minimum between the current path flow and the residual capacity.
174            path_flow = if path_flow > residual_capacity {
175                residual_capacity
176            } else {
177                path_flow
178            };
179            vertex = other_endpoint(&network, edge, vertex);
180            vertex_index = NodeIndexable::to_index(&network, vertex);
181        }
182
183        // Update the flow of each edge along the path
184        let mut vertex = destination;
185        let mut vertex_index = NodeIndexable::to_index(&network, vertex);
186        while let Some(edge) = edge_to[vertex_index] {
187            let edge_index = EdgeIndexable::to_index(&network, edge.id());
188            flows[edge_index] =
189                adjust_residual_flow(&network, edge, vertex, flows[edge_index], path_flow);
190            vertex = other_endpoint(&network, edge, vertex);
191            vertex_index = NodeIndexable::to_index(&network, vertex);
192        }
193        max_flow = max_flow + path_flow;
194    }
195    (max_flow, flows)
196}
petgraph/algo/ford_fulkerson.rs

petgraph/algo/
ford_fulkerson.rs
