1 #ifndef OSRM_PARTITIONER_DINIC_MAX_FLOW_HPP_
2 #define OSRM_PARTITIONER_DINIC_MAX_FLOW_HPP_
3 
4 #include "partitioner/bisection_graph_view.hpp"
5 
6 #include <cstdint>
7 #include <functional>
8 #include <set>
9 #include <unordered_set>
10 #include <utility>
11 #include <vector>
12 
13 namespace osrm
14 {
15 namespace partitioner
16 {
17 
18 class DinicMaxFlow
19 {
20   public:
21     // maximal number of hops in the graph from source to sink
22     using Level = std::uint32_t;
23 
24     using MinCut = struct
25     {
26         std::size_t num_nodes_source;
27         std::size_t num_edges;
28         std::vector<bool> flags;
29     };
30 
31     // input parameter storing the set o
32     using SourceSinkNodes = std::unordered_set<NodeID>;
33 
34     MinCut operator()(const BisectionGraphView &view,
35                       const SourceSinkNodes &source_nodes,
36                       const SourceSinkNodes &sink_nodes) const;
37 
38     // validates the inpiut parameters to the flow algorithm (e.g. not intersecting)
39     bool Validate(const BisectionGraphView &view,
40                   const SourceSinkNodes &source_nodes,
41                   const SourceSinkNodes &sink_nodes) const;
42 
43   private:
44     // the level of each node in the graph (==hops in BFS from source)
45     using LevelGraph = std::vector<Level>;
46 
47     // this is actually faster than using an unordered_set<Edge>, stores all edges that have
48     // capacity grouped by node
49     using FlowEdges = std::vector<std::set<NodeID>>;
50 
51     // The level graph (see [1]) is based on a BFS computation. We assign a level to all nodes
52     // (starting with 0 for all source nodes) and assign the hop distance in the residual graph as
53     // the level of the node.
54     //    a
55     //  /   \ 
56     // s     t
57     //  \   /
58     //    b
59     // would assign s = 0, a,b = 1, t=2
60     LevelGraph ComputeLevelGraph(const BisectionGraphView &view,
61                                  const std::vector<NodeID> &border_source_nodes,
62                                  const SourceSinkNodes &source_nodes,
63                                  const SourceSinkNodes &sink_nodes,
64                                  const FlowEdges &flow) const;
65 
66     // Using the above levels (see ComputeLevelGraph), we can use multiple DFS (that can now be
67     // directed at the sink) to find a flow that completely blocks the level graph (i.e. no path
68     // with increasing level exists from `s` to `t`).
69     std::size_t BlockingFlow(FlowEdges &flow,
70                              LevelGraph &levels,
71                              const BisectionGraphView &view,
72                              const SourceSinkNodes &source_nodes,
73                              const std::vector<NodeID> &border_sink_nodes) const;
74 
75     // Finds a single augmenting path from a node to the sink side following levels in the level
76     // graph. We don't actually remove the edges, so we have to check for increasing level values.
77     // Since we know which sinks have been reached, we actually search for these paths starting at
78     // sink nodes, instead of the source, so we can save a few dfs runs
79     std::vector<NodeID> GetAugmentingPath(LevelGraph &levels,
80                                           const NodeID from,
81                                           const BisectionGraphView &view,
82                                           const FlowEdges &flow,
83                                           const SourceSinkNodes &source_nodes) const;
84 
85     // Builds an actual cut result from a level graph
86     MinCut MakeCut(const BisectionGraphView &view,
87                    const LevelGraph &levels,
88                    const std::size_t flow_value) const;
89 };
90 
91 } // namespace partitioner
92 } // namespace osrm
93 
94 // Implementation of Dinics [1] algorithm for max-flow/min-cut.
95 // [1] https://www.cs.bgu.ac.il/~dinitz/D70.pdf
96 
97 #endif // OSRM_PARTITIONER_DINIC_MAX_FLOW_HPP_
98