Line data    Source code

       1             : #include "Static/Solution.hpp"
       2             : 
       3             : #include <algorithm>
       4             : #include <set>
       5             : #include <unordered_map>
       6             : 
       7             : using namespace std;
       8             : using namespace Static;
       9             : 
      10             : typedef Network::Edge    Edge;
      11             : typedef Network::Path    Path;
      12             : typedef Solution::Routes Routes;
      13             : 
      14         189 : Solution::Solution() {}
      15             : 
      16         170 : Solution::Solution(const Solution &sol):
      17          13 :     s(sol.s) {}
      18             : 
      19           3 : void Solution::Internals::addToRoutes(
      20             :     Routes &routes
      21             : ) const {
      22           3 :     if(s1 == nullptr && s2 == nullptr) {
      23           0 :         routes = paths;
      24           0 :         return;
      25             :     }
      26             : 
      27           3 :     addToRoutes(routes, 1.0);
      28             : }
      29             : 
      30           7 : void Solution::Internals::addToRoutes(
      31             :     Routes &routes,
      32             :     double  a
      33             : ) const {
      34          18 :     for(const auto &[path, flow]: paths) {
      35           7 :         routes[path] += a * flow;
      36             :     }
      37          11 :     if(s1 != nullptr) s1->addToRoutes(routes, a * (1.0 - alpha));
      38          11 :     if(s2 != nullptr) s2->addToRoutes(routes, a * alpha);
      39           7 : }
      40             : 
      41         482 : unordered_set<Edge::ID> Solution::getEdges() const {
      42         482 :     const auto &edges = s.get()->edges;
      43         482 :     return edges;
      44             : }
      45             : 
      46       29239 : Flow Solution::getFlowInEdge(Edge::ID id) const {
      47       29239 :     const auto &flows = s.get()->flows;
      48       29239 :     if((Edge::ID)flows.size() <= id)
      49             :         return 0.0;
      50             :     else
      51        1461 :         return flows[(size_t)id];
      52             : }
      53             : 
      54           3 : Routes Solution::getRoutes() const {
      55           3 :     Routes ret;
      56           3 :     s->addToRoutes(ret);
      57           3 :     return ret;
      58             : }
      59             : 
      60          21 : Solution &Solution::operator=(const Solution &sol) {
      61          21 :     s = sol.s;
      62             : 
      63          21 :     return *this;
      64             : }
      65             : 
      66         159 : Solution Solution::interpolate(
      67             :     const Solution &s1,
      68             :     const Solution &s2,
      69             :     Flow            alpha
      70             : ) {
      71         159 : #pragma GCC diagnostic push
      72         159 : #pragma GCC diagnostic ignored "-Wfloat-equal"
      73         159 :     if(alpha == 0.0)
      74           1 :         return s1;
      75         158 :     if(alpha == 1.0)
      76           1 :         return s2;
      77         157 : #pragma GCC diagnostic pop
      78             : 
      79         316 :     Solution ret;
      80             : 
      81         157 :     ret.s->alpha = alpha;
      82         157 :     ret.s->s1    = s1.s;
      83         157 :     ret.s->s2    = s2.s;
      84             : 
      85         314 :     const unordered_set<Edge::ID> &edges1 = s1.getEdges();
      86         314 :     const unordered_set<Edge::ID> &edges2 = s2.getEdges();
      87             : 
      88         157 :     auto &edges = ret.s->edges;
      89         157 :     auto &flows = ret.s->flows;
      90             : 
      91         157 :     edges.insert(edges1.begin(), edges1.end());
      92         157 :     edges.insert(edges2.begin(), edges2.end());
      93             : 
      94         157 :     if(edges.empty())
      95           0 :         flows.resize(0);
      96             :     else
      97         314 :         flows.resize(*max_element(edges.begin(), edges.end()) + 1, 0.0);
      98             : 
      99         700 :     for(size_t id = 0; id < flows.size(); ++id) {
     100         543 :         Edge::ID edgeID = (Edge::ID)id;
     101        1086 :         flows[id] =
     102         543 :             (1.0 - alpha) * s1.getFlowInEdge(edgeID) + (alpha)*s2.getFlowInEdge(edgeID);
     103             :     }
     104             : 
     105         157 :     return ret;
     106             : }
     107             : 
     108           0 : void Solution::materialize() {
     109           0 :     s->materialize();
     110           0 : }
     111             : 
     112           0 : void Solution::Internals::materialize() {
     113           0 :     if(s1) {
     114           0 :         s1->addToRoutes(paths, 1.0 - alpha);
     115           0 :         s1.reset();
     116             :     }
     117           0 :     if(s2) {
     118           0 :         s2->addToRoutes(paths, alpha);
     119           0 :         s2.reset();
     120             :     }
     121           0 : }
     122             : 
     123           3 : double Solution::getTotalFlow() const {
     124           3 :     double ret    = 0.0;
     125           3 :     Routes routes = getRoutes();
     126           9 :     for(const auto &[path, flow]: routes) {
     127           6 :         ret += flow;
     128             :     }
     129           3 :     return ret;
     130             : }
     131             : 
     132          18 : void SolutionBase::addPath(const Path &path, Flow newFlow) {
     133          18 :     auto &paths = s.get()->paths;
     134          18 :     auto &flows = s.get()->flows;
     135          18 :     auto &edges = s.get()->edges;
     136             : 
     137          18 :     Flow &f     = paths[path];
     138          18 :     Flow  delta = newFlow - f;
     139             : 
     140             :     /*
     141             :      * TODO: check if this is correct. Because it would make more sense to have
     142             :      * f += delta instead of f = newFlow; in which case it should be discussed
     143             :      * what the definition of newFlow is. Because we are not actually adding a
     144             :      * flow, we are modifying the flow of a path.
     145             :      */
     146          18 :     f = newFlow;
     147             : 
     148          18 :     if(!path.empty()) {
     149          18 :         Edge::ID maxId = *max_element(path.begin(), path.end());
     150          18 :         if(maxId >= (Edge::ID)flows.size()) flows.resize(maxId + 1, 0.0);
     151             :     }
     152             : 
     153          65 :     for(const Edge::ID &id: path) {
     154          47 :         edges.insert(id);
     155          47 :         flows[id] += delta;
     156             :     }
     157          18 : }