tpl_netcapgraph.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_NETCAPGRAPH_H
#define TPL_NETCAPGRAPH_H
 
#include <tpl_net.H>
#include <ah-errors.H>
 
namespace Aleph {
 
template <typename Node_Info = Empty_Class, typename F_Type = double>
class Net_Cap_Node : public Graph_Anode<Node_Info>
{
  using Base = Graph_Anode<Node_Info>;
 
public:
  using Flow_Type = F_Type;
  
  using Node_Type = Node_Info;
 
  Flow_Type max_cap;
 
  Flow_Type in_flow = Flow_Type{0};
 
  Flow_Type out_flow = Flow_Type{0};
 
  Net_Cap_Node() noexcept
    : Base(), max_cap(std::numeric_limits<Flow_Type>::max())
  {
    // empty
  }
 
  explicit Net_Cap_Node(const Node_Info& node_info) 
    : Base(node_info), 
      max_cap(std::numeric_limits<Flow_Type>::max())
  {
    // empty
  }
 
  explicit Net_Cap_Node(Node_Info&& node_info) noexcept
    : Base(std::move(node_info)),
      max_cap(std::numeric_limits<Flow_Type>::max())
  {
    // empty
  }
 
  Net_Cap_Node(const Net_Cap_Node* node) 
    : Base(node->get_info()),
      max_cap(node->max_cap),
      in_flow(node->in_flow),
      out_flow(node->out_flow)
  {
    // empty
  }
 
  Net_Cap_Node(const Net_Cap_Node& other)
    : Base(other),
      max_cap(other.max_cap),
      in_flow(other.in_flow),
      out_flow(other.out_flow)
  {
    // empty
  }
 
  Net_Cap_Node& operator=(const Net_Cap_Node& other)
  {
    if (this != &other)
    {
      Base::operator=(other);
      max_cap = other.max_cap;
      in_flow = other.in_flow;
      out_flow = other.out_flow;
    }
    return *this;
  }
 
  [[nodiscard]] const Flow_Type& get_max_cap() const noexcept
  {
    return max_cap;
  }
 
  void set_max_cap(const Flow_Type& cap)
  {
    ah_domain_error_if(cap < Flow_Type{0})
      << "Node capacity cannot be negative";
    max_cap = cap;
  }
};
 
 
template <class NodeT = Net_Cap_Node<Empty_Class, double>,
          class ArcT = Net_Arc<Empty_Class, double>>
class Net_Cap_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;
 
  Node * insert_node(Node *p) override
  {
    return Net_Class::insert_node(p);
  }
 
  Node* insert_node(const Node_Type& node_info, 
                    const Flow_Type& cap = std::numeric_limits<Flow_Type>::max())
  {
    ah_domain_error_if(cap < Flow_Type{0})
      << "Node capacity cannot be negative";
    
    Node* p = Net_Class::insert_node(node_info);
    p->max_cap = cap;
    return p;
  }
 
  Node* insert_node(const Flow_Type& cap)
  {
    return insert_node(Node_Type{}, cap);
  }
 
  Node* insert_node()
  {
    return insert_node(Node_Type{}, std::numeric_limits<Flow_Type>::max());
  }
 
  using Aux_Net = Net_Graph<Net_Node<Empty_Class>, 
                            Net_Arc<bool, Flow_Type>>;
 
private:
  Aux_Net* aux_net = nullptr;
 
public:
  Net_Cap_Graph() noexcept
    : Net_Class(), aux_net(nullptr)
  {
    // empty
  }
 
  Net_Cap_Graph(const Net_Cap_Graph& other)
    : Net_Class(other), aux_net(nullptr)
  {
    // aux_net is not copied; must be recomputed if needed
  }
 
  Net_Cap_Graph(Net_Cap_Graph&& other) noexcept
    : Net_Class(std::move(other)), aux_net(other.aux_net)
  {
    other.aux_net = nullptr;
  }
 
  Net_Cap_Graph& operator=(const Net_Cap_Graph& other)
  {
    if (this != &other)
    {
      if (aux_net != nullptr)
        free_aux_net();
      Net_Class::operator=(other);
    }
    return *this;
  }
 
  Net_Cap_Graph& operator=(Net_Cap_Graph&& other) noexcept
  {
    if (this != &other)
    {
      if (aux_net != nullptr)
        free_aux_net();
      Net_Class::operator=(std::move(other));
      aux_net = other.aux_net;
      other.aux_net = nullptr;
    }
    return *this;
  }
 
  ~Net_Cap_Graph()
  {
    if (aux_net != nullptr)
    {
      clear_graph(*aux_net);
      delete aux_net;
      aux_net = nullptr;
    }
  }
 
  [[nodiscard]] Aux_Net* get_aux_net() noexcept
  {
    return aux_net;
  }
 
  [[nodiscard]] const Aux_Net* get_aux_net() const noexcept
  {
    return aux_net;
  }
 
  [[nodiscard]] bool has_aux_net() const noexcept
  {
    return aux_net != nullptr;
  }
 
  Aux_Net* compute_aux_net()
  {
    ah_domain_error_if(aux_net != nullptr)
      << "Auxiliary network has already been computed";
    
    aux_net = new Aux_Net;
    
    try
    {
      // Phase 1: Create node pairs and capacity arcs
      for (Node_Iterator<Net_Cap_Graph> it(*this); it.has_curr(); it.next_ne())
      {
        Node* p = it.get_curr();
        
        // Create source and target nodes for this node
        typename Aux_Net::Node* src = aux_net->insert_node();
        typename Aux_Net::Node* tgt = aux_net->insert_node();
        
        // Create arc representing node capacity
        // info = true means this arc represents a node
        typename Aux_Net::Arc* arc = 
          aux_net->insert_arc(src, tgt, p->max_cap, Flow_Type{0}, true);
        
        // Establish bidirectional mapping
        NODE_COOKIE(p) = arc;
        ARC_COOKIE(arc) = p;
      }
      
      // Phase 2: Create arcs corresponding to original edges
      for (Arc_Iterator<Net_Cap_Graph> it(*this); it.has_curr(); it.next_ne())
      {
        Arc* arc = it.get_curr();
        
        // Get the auxiliary arcs for source and target nodes
        typename Aux_Net::Arc* src_arc = 
          static_cast<typename Aux_Net::Arc*>(NODE_COOKIE(this->get_src_node(arc)));
        typename Aux_Net::Arc* tgt_arc = 
          static_cast<typename Aux_Net::Arc*>(NODE_COOKIE(this->get_tgt_node(arc)));
        
        // Connect tgt of src_arc to src of tgt_arc
        // info = false means this arc represents an original edge
        typename Aux_Net::Arc* a = 
          aux_net->insert_arc(aux_net->get_tgt_node(src_arc), 
                              aux_net->get_src_node(tgt_arc),
                              arc->cap, arc->flow, false);
        
        // Establish bidirectional mapping
        ARC_COOKIE(arc) = a;
        ARC_COOKIE(a) = arc;
      }
      
      return aux_net;
    }
    catch (...)
    {
      // Clean up on failure
      if (aux_net != nullptr)
      {
        clear_graph(*aux_net);
        delete aux_net;
        aux_net = nullptr;
      }
      throw;
    }
  }
 
  void update()
  {
    ah_domain_error_if(aux_net == nullptr)
      << "Auxiliary network has not been computed";
 
    for (typename Aux_Net::Arc_Iterator it(*aux_net); it.has_curr(); it.next_ne())
    {
      typename Aux_Net::Arc* arc = it.get_curr();
      
      if (arc->get_info())  // This arc represents a node
      {
        Node* p = static_cast<Node*>(ARC_COOKIE(arc));
        p->in_flow = arc->flow;
        p->out_flow = arc->flow;
      }
      else  // This arc represents an original edge
      {
        Arc* a = static_cast<Arc*>(ARC_COOKIE(arc));
        a->flow = arc->flow;
      }
    }
  }
 
  void free_aux_net()
  {
    ah_domain_error_if(aux_net == nullptr)
      << "Auxiliary network has not been computed";
 
    clear_graph(*aux_net);
    delete aux_net;
    aux_net = nullptr;
  }
 
  [[nodiscard]] Flow_Type get_total_flow() const
  {
    ah_domain_error_if(aux_net == nullptr)
      << "Auxiliary network has not been computed";
 
    Flow_Type total = Flow_Type{0};
    for (Node_Iterator<Net_Cap_Graph> it(*this); it.has_curr(); it.next_ne())
    {
      Node* p = it.get_curr();
      total += p->in_flow;
    }
    return total;
  }
 
  [[nodiscard]] bool check_node_capacities() const noexcept
  {
    for (Node_Iterator<Net_Cap_Graph> it(*this); it.has_curr(); it.next_ne())
    {
      Node* p = it.get_curr();
      if (p->in_flow > p->max_cap || p->out_flow > p->max_cap)
        return false;
    }
    return true;
  }
 
  void reset_flows() noexcept
  {
    // Reset arc flows
    for (Arc_Iterator<Net_Cap_Graph> it(*this); it.has_curr(); it.next_ne())
      it.get_curr()->flow = Flow_Type{0};
    
    // Reset node flows  
    for (Node_Iterator<Net_Cap_Graph> it(*this); it.has_curr(); it.next_ne())
    {
      Node* p = it.get_curr();
      p->in_flow = Flow_Type{0};
      p->out_flow = Flow_Type{0};
    }
  }
 
  [[nodiscard]] static Flow_Type get_node_cap(const Node* node) noexcept
  {
    return node->max_cap;
  }
 
  static void set_node_cap(Node* node, const Flow_Type& cap)
  {
    ah_domain_error_if(cap < Flow_Type{0})
      << "Node capacity cannot be negative";
    ah_overflow_error_if(node->in_flow > cap || node->out_flow > cap)
      << "Current flow exceeds new capacity";
    node->max_cap = cap;
  }
};
 
} // end namespace Aleph
 
#endif // TPL_NETCAPGRAPH_H