tpl_netcapgraph.H

/* Aleph-w

     / \  | | ___ _ __ | |__      __      __
    / _ \ | |/ _ \ '_ \| '_ \ ____\ \ /\ / / Data structures & Algorithms
   / ___ \| |  __/ |_) | | | |_____\ V  V /  version 1.9b
  /_/   \_\_|\___| .__/|_| |_|      \_/\_/   https://github.com/lrleon/Aleph-w
                 |_|         

  This file is part of Aleph-w library

  Copyright (c) 2002-2018 Leandro Rabindranath Leon & Alejandro Mujica

  This program is free software: you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation, either version 3 of the License, or
  (at your option) any later version.

  This program is distributed in the hope that it will be useful, but
  WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with this program. If not, see <https://www.gnu.org/licenses/>.
*/
# ifndef TPL_NETCAPGRAPH_H
# define TPL_NETCAPGRAPH_H
# include <tpl_netgraph.H>

namespace Aleph {

    template <typename Node_Info, typename F_Type = double>
class Net_Cap_Node : public Net_Node<Node_Info, F_Type>
{
public:
  typedef F_Type Flow_Type;

  Flow_Type max_cap; 

  Net_Cap_Node() : max_cap(numeric_limits<Flow_Type>::max()) {}

  Net_Cap_Node(const Node_Info & node_info) 
    : Net_Node<Node_Info, F_Type>(node_info), 
      max_cap(numeric_limits<Flow_Type>::max())
  { /* empty */ }

  Net_Cap_Node(Net_Cap_Node * node) 
    : Net_Node<Node_Info, F_Type>(*node), max_cap(node->max_cap) { /* empty */ }
}; 

    template <class NodeT, class ArcT>
class Net_Cap_Graph : public Net_Graph<NodeT, ArcT>
{
public:
  typedef Net_Graph<NodeT, ArcT> Net_Class;
  typedef ArcT Arc;
  typedef NodeT Node;
  typedef typename Arc::Flow_Type Flow_Type;
  typedef typename Node::Node_Type Node_Type;
  typedef typename Arc::Arc_Type Arc_Type;

  Node * insert_node(const Node_Type & node_info, 
                     const Flow_Type & cap = numeric_limits<Flow_Type>::max())
  {
    Node * p = Net_Class::insert_node(node_info);
    p->max_cap = cap;
    return p;
  }
    typedef Net_Graph<Net_Node<Empty_Class, Flow_Type>, 
                      Net_Arc<bool, Flow_Type> > Aux_Net;
  private:
    Aux_Net * aux_net;
  public:
    Net_Cap_Graph() : aux_net(nullptr) { /* empty */ }
  Aux_Net * get_aux_net() { return aux_net; }
  Aux_Net * compute_aux_net()
  {
    if (aux_net != nullptr)
      throw std::domain_error("aux_net has already computed");
    aux_net = new Aux_Net;
    try
      {
        for (Node_Iterator<Net_Cap_Graph> it(*this); it.has_curr();
             it.next_ne())
          {
            Node * p = it.get_curr_ne();
            typename Aux_Net::Node * src = aux_net->insert_node();
            typename Aux_Net::Node * tgt = aux_net->insert_node();
            typename Aux_Net::Arc  * arc = 
              aux_net->insert_arc(src, tgt, true, p->max_cap, 0);
            NODE_COOKIE(p)  = arc;
            ARC_COOKIE(arc) = p;
          }
        for (Arc_Iterator<Net_Cap_Graph> it(*this); it.has_curr();
             it.next_ne())
          {
            Arc * arc = it.get_curr_ne();
            typename Aux_Net::Arc * src_arc = 
              (typename Aux_Net::Arc *) NODE_COOKIE(get_src_node(arc));
            typename Aux_Net::Arc * tgt_arc = 
              (typename Aux_Net::Arc *) NODE_COOKIE(get_tgt_node(arc));
            typename Aux_Net::Arc * a = 
              aux_net->insert_arc(aux_net->get_tgt_node(src_arc), 
                                  aux_net->get_src_node(tgt_arc), false, 
                                  arc->cap, arc->flow);
            ARC_COOKIE(arc) = a;
            ARC_COOKIE(a)   = arc;
          }
        return aux_net;
      }
    catch (...)
      {
        free_aux_net();
      }
  }
  void update()
  {
    if (aux_net == nullptr)
      throw std::domain_error("Auxiliar net has not been generated");

    for (Arc_Iterator<Aux_Net, No_Res_Arc<Aux_Net> > it(*aux_net); 
         it.has_curr(); it.next_ne())
      {
        typename Aux_Net::Arc * arc = it.get_curr_ne();
        if (arc->get_info())
          {
            Node * p = (Node*) ARC_COOKIE(arc);
            p->in_flow = p->out_flow = arc->flow;
          }
        else
          {
            Arc * a = (Arc*) ARC_COOKIE(arc);
            a->flow = arc->flow;
          }
      }
  }
  void free_aux_net()
  {
    if (aux_net == nullptr)
      throw std::domain_error("Auxiliar net has not been generated");

    clear_graph(*aux_net);
    delete aux_net;
    aux_net = nullptr;
  }

  ~Net_Cap_Graph()
  {
    if (aux_net != nullptr)
      free_aux_net();
  }
};

} // end namespace Aleph

# endif // endif