CXXGraph/include/CXXGraph/Graph/Algorithm/FordFulkerson_impl.hpp at 58a20a416a80714681856e2fd5863a2dd3b1d035 · toge/CXXGraph · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
/***********************************************************/
/***      ______  ____  ______                 _         ***/
/***     / ___\ \/ /\ \/ / ___|_ __ __ _ _ __ | |__	     ***/
/***    | |    \  /  \  / |  _| '__/ _` | '_ \| '_ \	 ***/
/***    | |___ /  \  /  \ |_| | | | (_| | |_) | | | |    ***/
/***     \____/_/\_\/_/\_\____|_|  \__,_| .__/|_| |_|    ***/
/***                                    |_|			     ***/
/***********************************************************/
/***     Header-Only C++ Library for Graph			     ***/
/***	 Representation and Algorithms				     ***/
/***********************************************************/
/***     Author: ZigRazor ***/
/***	 E-Mail: zigrazor@gmail.com 				     ***/
/***********************************************************/
/***	 Collaboration: ----------- 				     ***/
/***********************************************************/
/***	 License: AGPL v3.0 ***/
/***********************************************************/

#ifndef __CXXGRAPH_FORDFULKERSON_IMPL_H__
#define __CXXGRAPH_FORDFULKERSON_IMPL_H__

#pragma once

#include <algorithm>

#include "CXXGraph/Graph/Graph_decl.h"

namespace CXXGraph {

template <typename T>
double Graph<T>::fordFulkersonMaxFlow(const Node<T> &source,
                                      const Node<T> &target) const {
  if (!isDirectedGraph()) {
    return -1;
  }
  double maxFlow = 0;
  std::unordered_map<shared<const Node<T>>, shared<const Node<T>>, nodeHash<T>>
      parent;
  std::unordered_map<
      shared<const Node<T>>,
      std::unordered_map<shared<const Node<T>>, double, nodeHash<T>>,
      nodeHash<T>>
      weightMap;
  // build weight map
  auto edgeSet = this->getEdgeSet();
  for (const auto &edge : edgeSet) {
    // The Edge are all Directed at this point because is checked at the
    // start
    if (edge->isWeighted().value_or(false)) {
      shared<const DirectedWeightedEdge<T>> dw_edge =
          std::static_pointer_cast<const DirectedWeightedEdge<T>>(edge);
      weightMap[edge->getNodePair().first][edge->getNodePair().second] =
          dw_edge->getWeight();
    } else {
      weightMap[edge->getNodePair().first][edge->getNodePair().second] =
          0;  // No Weighted Edge are assumed to be 0 weigthed
    }
  }

  // Constuct iterators for source and target nodes in nodeSet
  auto nodeSet = getNodeSet();
  auto source_node_ptr = *std::find_if(
      nodeSet.begin(), nodeSet.end(),
      [&source](auto node) { return node->getUserId() == source.getUserId(); });
  auto target_node_ptr = *std::find_if(
      nodeSet.begin(), nodeSet.end(),
      [&target](auto node) { return node->getUserId() == target.getUserId(); });

  auto bfs_helper = [this, &source_node_ptr, &target_node_ptr, &parent,
                     &weightMap]() -> bool {
    std::unordered_map<shared<const Node<T>>, bool, nodeHash<T>> visited;
    std::queue<shared<const Node<T>>> queue;
    queue.push(source_node_ptr);
    visited[source_node_ptr] = true;
    parent[source_node_ptr] = nullptr;
    while (!queue.empty()) {
      auto u = queue.front();
      queue.pop();
      for (auto &v : weightMap[u]) {
        if (!visited[v.first] && v.second > 0) {
          queue.push(v.first);
          visited[v.first] = true;
          parent[v.first] = u;
        }
      }
    }

    return (visited[target_node_ptr]);
  };
  // Updating the residual values of edges
  while (bfs_helper()) {
    double pathFlow = std::numeric_limits<double>::max();
    for (auto v = target_node_ptr; v != source_node_ptr; v = parent[v]) {
      auto u = parent[v];
      pathFlow = std::min(pathFlow, weightMap[u][v]);
    }
    for (auto v = target_node_ptr; v != source_node_ptr; v = parent[v]) {
      auto u = parent[v];
      weightMap[u][v] -= pathFlow;
      weightMap[v][u] += pathFlow;
    }
    // Adding the path flows
    maxFlow += pathFlow;
  }

  return maxFlow;
}
}  // namespace CXXGraph
#endif  // __CXXGRAPH_FORDFULKERSON_IMPL_H__