tpl_net_sup_dem.H

Go to the documentation of this file.

 
/*
                          Aleph_w
 
  Data structures & Algorithms
  version 2.0.0b
  https://github.com/lrleon/Aleph-w
 
  This file is part of Aleph-w library
 
  Copyright (c) 2002-2026 Leandro Rabindranath Leon
 
  Permission is hereby granted, free of charge, to any person obtaining a copy
  of this software and associated documentation files (the "Software"), to deal
  in the Software without restriction, including without limitation the rights
  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  copies of the Software, and to permit persons to whom the Software is
  furnished to do so, subject to the following conditions:
 
  The above copyright notice and this permission notice shall be included in all
  copies or substantial portions of the Software.
 
  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  SOFTWARE.
*/
 
 
#ifndef TPL_NET_SUP_DEM_H
#define TPL_NET_SUP_DEM_H
 
#include <tpl_net.H>
#include <ah-errors.H>
 
namespace Aleph
{
 
template <typename Node_Info, typename F_Type = long>
class Net_Sup_Dem_Node : public Graph_Anode<Node_Info>
{
public:
  using Flow_Type = F_Type;
  
  using Base = Graph_Anode<Node_Info>;
 
  Flow_Type supply_flow = Flow_Type{0};
 
  Flow_Type out_cap = Flow_Type{0};
 
  Flow_Type in_cap = Flow_Type{0};
 
  Flow_Type out_flow = Flow_Type{0};
 
  Flow_Type in_flow = Flow_Type{0};
 
  [[nodiscard]] Flow_Type& get_supply_flow() noexcept { return supply_flow; }
 
  [[nodiscard]] const Flow_Type& get_supply_flow() const noexcept 
  { 
    return supply_flow; 
  }
 
  Net_Sup_Dem_Node() : Base() {}
 
  explicit Net_Sup_Dem_Node(const Node_Info& node_info)
    : Base(node_info)
  {}
 
  Net_Sup_Dem_Node(Net_Sup_Dem_Node* node)
    : Base(*node), 
      supply_flow(node->supply_flow),
      out_cap(node->out_cap),
      in_cap(node->in_cap),
      out_flow(node->out_flow),
      in_flow(node->in_flow)
  {}
};
 
 
template <class NodeT = Net_Sup_Dem_Node<Empty_Class, double>,
          class ArcT = Net_Arc<Empty_Class, double>>
class Net_Sup_Dem_Graph : public Net_Graph<NodeT, ArcT>
{
public:
  using Net_Class = Net_Graph<NodeT, ArcT>;
  using Arc = ArcT;
  using Node = NodeT;
  using Flow_Type = typename Arc::Flow_Type;
  using Node_Type = typename Node::Node_Type;
  using Arc_Type = typename Arc::Arc_Type;
  using Aux_Net = Net_Sup_Dem_Graph;
 
private:
  Node* super_source = nullptr;  
  Node* super_sink = nullptr;    
 
public:
 
  Net_Sup_Dem_Graph() = default;
 
  ~Net_Sup_Dem_Graph()
  {
    if (exist_aux_net())
      free_aux_net();
  }
 
 
  // Bring base class insert_node overloads into scope
  using Net_Class::insert_node;
 
 
  Node* insert_node(const Node_Type& node_info, const Flow_Type& supply = 0)
  {
    Node* p = Net_Class::insert_node(node_info);
    p->supply_flow = supply;
    return p;
  }
 
  Node* insert_node(const Flow_Type& supply)
  {
    return insert_node(Node_Type(), supply);
  }
 
 
 
  [[nodiscard]] bool exist_aux_net() const noexcept
  {
    return super_source != nullptr or super_sink != nullptr;
  }
 
  Net_Sup_Dem_Graph* compute_aux_net()
  {
    ah_domain_error_if(exist_aux_net())
      << "Auxiliary net is already computed";
 
    super_source = insert_node(0);  // auxiliary source
    super_sink = insert_node(0);    // auxiliary sink
 
    // Connect super-source/sink based on supply/demand values
    for (Node_Iterator<Net_Sup_Dem_Graph> it(*this); it.has_curr(); it.next_ne())
      {
        Node* p = it.get_curr();
        if (p->supply_flow > 0)  // supply node?
          {
            ah_range_error_if(p->out_cap < p->supply_flow)
              << "Supply flow in node at " << static_cast<void*>(p)
              << " is greater than out capacity";
            this->insert_arc(super_source, p, p->supply_flow);
          }
        else if (p->supply_flow < 0)  // demand node?
          {
            ah_range_error_if(p->in_cap < -p->supply_flow)
              << "Supply flow in node at " << static_cast<void*>(p)
              << " is smaller than in capacity";
            this->insert_arc(p, super_sink, -p->supply_flow);
          }
      }
 
    // Remove super-source if no supply nodes
    if (this->get_out_degree(super_source) == 0)
      {
        this->remove_node(super_source);
        super_source = nullptr;
      }
 
    // Remove super-sink if no demand nodes
    if (this->get_in_degree(super_sink) == 0)
      {
        this->remove_node(super_sink);
        super_sink = nullptr;
      }
 
    return this;
  }
 
  [[nodiscard]] Net_Sup_Dem_Graph* get_aux_net() noexcept
  {
    return exist_aux_net() ? this : nullptr;
  }
 
  [[nodiscard]] Node* get_super_source() const noexcept { return super_source; }
 
  [[nodiscard]] Node* get_super_sink() const noexcept { return super_sink; }
 
  void free_aux_net()
  {
    ah_domain_error_if(not exist_aux_net())
      << "Auxiliary net has not been computed";
 
    if (super_source != nullptr)
      {
        this->remove_node(super_source);
        super_source = nullptr;
      }
 
    if (super_sink != nullptr)
      {
        this->remove_node(super_sink);
        super_sink = nullptr;
      }
  }
 
 
 
  [[nodiscard]] bool is_feasible() const
  {
    ah_domain_error_if(not exist_aux_net())
      << "Auxiliary net has not been computed";
 
    for (Node_Iterator<Net_Sup_Dem_Graph> it(*this); it.has_curr(); it.next_ne())
      {
        Node* p = it.get_curr();
        const Flow_Type& supply_flow = p->supply_flow;
 
        if (supply_flow == 0)
          continue;
 
        if (supply_flow > 0 and p->out_flow < supply_flow)
          return false;  // Supply node not providing enough flow
 
        if (supply_flow < 0 and p->in_flow < -supply_flow)
          return false;  // Demand node not receiving enough flow
      }
 
    return true;
  }
 
  void non_feasible_nodes(DynDlist<Node*>& supply_list,
                          DynDlist<Node*>& demand_list)
  {
    for (Node_Iterator<Net_Sup_Dem_Graph> it(*this); it.has_curr(); it.next_ne())
      {
        Node* p = it.get_curr();
        const Flow_Type& supply_flow = p->supply_flow;
 
        if (supply_flow == 0)
          continue;
 
        if (supply_flow > 0 and p->out_flow < supply_flow)
          supply_list.append(p);
        else if (supply_flow < 0 and p->in_flow < -supply_flow)
          demand_list.append(p);
      }
  }
 
 
 
  void set_supply_flow(Node* p, const Flow_Type& supply)
  {
    ah_range_error_if(supply > 0 and p->out_cap < supply)
      << "Supply flow in node at " << static_cast<void*>(p)
      << " is greater than out capacity";
    ah_range_error_if(supply < 0 and p->in_cap < -supply)
      << "Supply flow in node at " << static_cast<void*>(p)
      << " is smaller than in capacity";
 
    p->supply_flow = supply;
  }
 
  [[nodiscard]] Flow_Type get_supply_flow(Node* p) const noexcept
  {
    return p->supply_flow;
  }
 
 
 
  [[nodiscard]] size_t count_supply_nodes() const noexcept
  {
    size_t count = 0;
    for (Node_Iterator<Net_Sup_Dem_Graph> it(*this); it.has_curr(); it.next_ne())
      if (it.get_curr()->supply_flow > 0)
        ++count;
    return count;
  }
 
  [[nodiscard]] size_t count_demand_nodes() const noexcept
  {
    size_t count = 0;
    for (Node_Iterator<Net_Sup_Dem_Graph> it(*this); it.has_curr(); it.next_ne())
      if (it.get_curr()->supply_flow < 0)
        ++count;
    return count;
  }
 
  [[nodiscard]] Flow_Type total_supply() const noexcept
  {
    Flow_Type total = 0;
    for (Node_Iterator<Net_Sup_Dem_Graph> it(*this); it.has_curr(); it.next_ne())
      {
        const Flow_Type& sf = it.get_curr()->supply_flow;
        if (sf > 0)
          total += sf;
      }
    return total;
  }
 
  [[nodiscard]] Flow_Type total_demand() const noexcept
  {
    Flow_Type total = 0;
    for (Node_Iterator<Net_Sup_Dem_Graph> it(*this); it.has_curr(); it.next_ne())
      {
        const Flow_Type& sf = it.get_curr()->supply_flow;
        if (sf < 0)
          total -= sf;  // Add absolute value
      }
    return total;
  }
 
  [[nodiscard]] bool is_balanced() const noexcept
  {
    return total_supply() == total_demand();
  }
 
};
 
} // end namespace Aleph
 
#endif // TPL_NET_SUP_DEM_H