Line data    Source code

       1             : #include "Alg/Flow/EdmondsKarp.hpp"
       2             : 
       3             : #include <unordered_set>
       4             : 
       5             : #include "Alg/Graph.hpp"
       6             : 
       7             : using namespace std;
       8             : using namespace Alg;
       9             : using namespace Alg::Flow;
      10             : 
      11             : typedef Graph::Node  Node;
      12             : typedef Graph::Edge  Edge;
      13             : typedef Edge::Weight Weight;
      14             : typedef Graph::Path  Path;
      15             : 
      16     1087340 : void EdmondsKarp::EGraph::addEdge(Edge::ID id, Node u, Node v, Edge::Weight c) {
      17     1087340 :     Graph::addEdge(id, u, v, c);
      18     1087340 :     if(edges.size() <= size_t(id))
      19      375112 :         edges.resize(id + 1);
      20     1087340 :     edges.at(id) = {u, getAdj(u).size() - 1};
      21     1087340 : }
      22             : 
      23     1014760 : Edge &EdmondsKarp::EGraph::getEdge(Edge::ID id) {
      24     1014760 :     const auto &[u, i] = edges.at(id);
      25     1014760 :     return getAdj(u).at(i);
      26             : }
      27             : 
      28       93778 : EdmondsKarp::EdmondsKarp(ShortestPath::ShortestPathOneOne &sp_):
      29       93778 :     sp(sp_) {}
      30             : 
      31       93778 : void EdmondsKarp::buildResidualGraph(const Graph &G) {
      32       93778 :     Gf = EGraph();
      33             : 
      34      686793 :     for(const Node &u: G.getNodes()) {
      35      593015 :         Gf.addNode(u);
      36     1136680 :         for(const Edge &e: G.getAdj(u)) {
      37      543669 :             size_t eid1 = (size_t(e.id) << 1);
      38      543669 :             size_t eid2 = (size_t(e.id) << 1) | 1;
      39             :             // clang-format off
      40      543669 :             Gf.addEdge((Edge::ID)eid1, e.u, e.v, e.w);
      41      543669 :             Gf.addEdge((Edge::ID)eid2, e.v, e.u, 0.0);
      42             :             // clang-format on
      43             :         }
      44             :     }
      45       93778 : }
      46             : 
      47      114545 : Weight getBottleneck(const Path &path) {
      48      114545 :     Weight bottleneck = Edge::WEIGHT_INF;
      49      621926 :     for(const Edge &e: path) {
      50      644407 :         bottleneck = min(bottleneck, e.w);
      51             :     }
      52      114545 :     return bottleneck;
      53             : }
      54             : 
      55       93778 : Weight EdmondsKarp::solve(
      56             :     const Graph &G,
      57             :     Node         source,
      58             :     Node         sink
      59             : ) {
      60       93778 :     originalGraph = &G;
      61             : 
      62       93778 :     buildResidualGraph(G);
      63             : 
      64       93778 :     Weight totalFlow = 0.0;
      65             : 
      66      208323 :     while(true) {
      67      208323 :         sp.solveStartFinish(Gf, source, sink);
      68      208323 :         if(!sp.hasVisited(sink))
      69             :             break;
      70             : 
      71      229090 :         Path   path = sp.getPath(sink);
      72      114545 :         Weight f    = getBottleneck(path);
      73      114545 :         if(f <= 0.0)
      74             :             break;
      75             : 
      76      114545 :         totalFlow += f;
      77             : 
      78      621926 :         for(const Edge &e: path) {
      79      507381 :             Edge::ID oppositeID = e.id ^ 1;
      80             : 
      81      507381 :             Gf.getEdge(e.id).w -= f;
      82      507381 :             Gf.getEdge(oppositeID).w += f;
      83             :         }
      84             :     }
      85             : 
      86       93778 :     return totalFlow;
      87             : }
      88             : 
      89           0 : Graph EdmondsKarp::getFlowsGraph() const {
      90           0 :     unordered_set<Edge::ID> edgeIDs;
      91           0 :     for(const Node &u: originalGraph->getNodes()) {
      92           0 :         for(const Edge &e: originalGraph->getAdj(u)) {
      93           0 :             edgeIDs.insert(e.id);
      94             :         }
      95             :     }
      96             : 
      97           0 :     unordered_map<Edge::ID, Weight> flows;
      98           0 :     for(const Node &u: Gf.getNodes()) {
      99           0 :         for(const Edge &e: Gf.getAdj(u)) {
     100           0 :             Edge::ID eid      = e.id >> 1;
     101           0 :             bool     backward = (e.id & 1);
     102           0 :             if(backward && edgeIDs.count(eid)) {
     103           0 :                 flows[e.id] = e.w;
     104             :             }
     105             :         }
     106             :     }
     107             : 
     108           0 :     Graph G;
     109           0 :     for(const Node &u: originalGraph->getNodes()) {
     110           0 :         G.addNode(u);
     111           0 :         for(const Edge &e: originalGraph->getAdj(u)) {
     112           0 :             G.addEdge(e.id, e.u, e.v, flows.at(e.id));
     113             :         }
     114             :     }
     115             : 
     116           0 :     return G;
     117             : }