tpl_kgraph.H

# ifndef TPL_KGRAPH_H
# define TPL_KGRAPH_H

# include <tpl_netgraph.H>

namespace Aleph {

template <class GT, 
          template <class> class Max_Flow = Random_Preflow_Maximum_Flow,
          class SA = Dft_Show_Arc<GT> > 
long edge_connectivity(GT & g)
{
  typedef Net_Graph<Net_Node<Empty_Class>, Net_Arc<Empty_Class> > Net;
  Net net;
  typename Net::Node * source = NULL; 
  long min_degree = numeric_limits<long>::max(); 
  for (Node_Iterator<GT> it(g); it.has_current(); it.next())
    {
      typename GT::Node * p = it.get_current();
      NODE_COOKIE(p) = net.insert_node();
      if (g.get_num_arcs(p) < min_degree)
        {
          source = mapped_node<GT, Net> (p);
          min_degree = g.get_num_arcs(p);
        }
    }

  if (min_degree <= 1)
    return min_degree; 

  for (Arc_Iterator<GT, SA> it(g); it.has_current(); it.next()) 
    {
      typename GT::Arc * a     = it.get_current();
      typename Net::Node * src = mapped_node<GT, Net> (g.get_src_node(a));
      typename Net::Node * tgt = mapped_node<GT, Net> (g.get_tgt_node(a));
      if (src != source)
        net.insert_arc(tgt, src, 1);

      if (tgt != source)
        net.insert_arc(src, tgt, 1);
    }

  I(source->in_degree == 0);

  long min_k = min_degree;
  for (Node_Iterator<Net> it(net); it.has_current(); it.next())
    {
      typename Net::Node * sink = it.get_current();
      if (sink == source) 
        continue;

      DynDlist<typename Net::Arc*> from_sink_arcs;

      for (Node_Arc_Iterator<Net> it(sink); it.has_current(); it.next())
        from_sink_arcs.append(it.get_current());

      for (typename DynDlist<typename Net::Arc*>::Iterator 
             it(from_sink_arcs); it.has_current(); it.next())
        net.disconnect_arc(it.get_current());

      const typename Net::Flow_Type flow = Max_Flow <Net> () (net); 
      if (flow < min_k)
        min_k = flow;

      while (not from_sink_arcs.is_empty())
        net.connect_arc(from_sink_arcs.get());

      net.reset(); // colocar flujo en cero
    }

  return min_k;
}

    template <class GT, 
              template <class> class Max_Flow = Heap_Preflow_Maximum_Flow> 
class Edge_Connectivity
{
public:

  long operator () (GT & g) { return edge_connectivity <GT, Max_Flow> (g); }
};


  template <class GT, 
            template <class> class Max_Flow = Heap_Preflow_Maximum_Flow,
            class SA = Dft_Show_Arc<GT> > 
long compute_min_cut(GT &                             g,
                     Aleph::set<typename GT::Node*> & l, 
                     Aleph::set<typename GT::Node*> & r,
                     DynDlist<typename GT::Arc *> &   cut)
{
  typedef Net_Graph<Net_Node<Empty_Class>, Net_Arc<Empty_Class> > Net;
  Net net;
  typename Net::Node * source = NULL; 
  long min_degree = numeric_limits<long>::max(); 
  for (Node_Iterator<GT> it(g); it.has_current(); it.next())
    {
      typename GT::Node * p  = it.get_current();
      typename Net::Node * q = net.insert_node();
      GT::map_nodes (p, q);

      if (g.get_num_arcs(p) < min_degree)
        {
          source = mapped_node<GT, Net> (p);
          min_degree = g.get_num_arcs(p);
        }
    }

  if (min_degree <= 1)
    return min_degree; 

  for (Arc_Iterator<GT, SA> it(g); it.has_current(); it.next()) 
    {
      typename GT::Arc * a     = it.get_current();
      typename Net::Node * src = mapped_node<GT, Net>(g.get_src_node(a));
      typename Net::Node * tgt = mapped_node<GT, Net>(g.get_tgt_node(a));
      if (src != source)
        {
          typename Net::Arc * arc = net.insert_arc(tgt, src, 1);
          ARC_COOKIE(arc) = a;
        }

      if (tgt != source)
        {
          typename Net::Arc * arc = net.insert_arc(src, tgt, 1);
          ARC_COOKIE(arc) = a;
        }
    }

  Aleph::set<typename Net::Node*> tmp_vs, tmp_vt;
  DynDlist<typename Net::Arc*>    tmp_cuts, tmp_cutt;
  long min_k = numeric_limits<long>::max();  
  for (Node_Iterator<Net> it(net); it.has_current(); it.next())
    {
      typename Net::Node * sink = it.get_current();
      if (sink == source) 
        continue;

      DynDlist<typename Net::Arc*> from_sink_arcs;

      for (Node_Arc_Iterator<Net> it(sink); it.has_current(); it.next())
        from_sink_arcs.append(it.get_current());

      for (typename DynDlist<typename Net::Arc*>::Iterator 
             it(from_sink_arcs); it.has_current(); it.next())
        net.disconnect_arc(it.get_current());

      Aleph::set<typename Net::Node*> vs, vt;
      DynDlist<typename Net::Arc *> cuts, cutt;
      const typename Net::Flow_Type flow = 
        Min_Cut <Net, Max_Flow> () (net, vs, vt, cuts, cutt); 

      if (flow < min_k)
        {
          min_k = flow;
          tmp_vs.swap(vs);
          tmp_vt.swap(vt);
          tmp_cuts.swap(cuts);
          tmp_cutt.swap(cutt);
        }

      net.reset(); // colocar flujo en cero

      while (not from_sink_arcs.is_empty())
        net.connect_arc(from_sink_arcs.get());
    }
  
  for (typename Aleph::set<typename Net::Node*>::iterator
         it = tmp_vs.begin(); it != tmp_vs.end(); it++)
    l.insert(mapped_node <Net, GT> (*it));

  for (typename Aleph::set<typename Net::Node*>::iterator 
         it = tmp_vt.begin(); it != tmp_vt.end(); it++)
    r.insert(mapped_node <Net, GT> (*it));

  for (typename DynDlist<typename Net::Arc*>::Iterator it(tmp_cuts); 
       it.has_current(); it.next())
    {
      typename Net::Arc* arc = it.get_current();
      cut.append(mapped_arc<Net, GT> (arc));
    }

  return min_k;
}

    template <class GT, 
              template <class> class Max_Flow = Heap_Preflow_Maximum_Flow,
              class SA = Dft_Show_Arc<GT> > 
class Compute_Min_Cut
{
public:
  long operator () (GT &                             g,
                    Aleph::set<typename GT::Node*> & l, 
                    Aleph::set<typename GT::Node*> & r,
                    DynDlist<typename GT::Arc *> &   cut) 
  { 
    return compute_min_cut <GT, Max_Flow, SA> (g, l, r, cut); 
  }
};


  template <class GT, 
            template <class> class Max_Flow = Random_Preflow_Maximum_Flow,
            class SA                        = Dft_Show_Arc<GT> > 
long vertex_connectivity(GT & g)
{
  typedef Net_Graph<Net_Node<Empty_Class>, Net_Arc<Empty_Class> > Net;
  Net net;
  for (Node_Iterator<GT> it(g); it.has_current(); it.next())
    {
      typename GT::Node * p = it.get_current();
      NODE_COOKIE(p) = net.insert_node();
    }

  for (Arc_Iterator<GT, SA> it(g); it.has_current(); it.next()) 
    {
      typename GT::Arc * a     = it.get_current();
      typename Net::Node * src = mapped_node<GT,Net>(g.get_src_node(a));
      typename Net::Node * tgt = mapped_node<GT,Net>(g.get_tgt_node(a));
      net.insert_arc(tgt, src, 1);
      net.insert_arc(src, tgt, 1);
    }

  long min_k = g.get_num_nodes();
  int i = 1;

  for (Node_Iterator<Net> k(net); k.has_current() and i < min_k; k.next(), i++)
    {
      typename Net::Node * source = k.get_current();
      
      DynDlist<typename Net::Arc*> to_source_list;
      for (Node_Arc_Iterator<Net> it(source); it.has_current(); it.next())
        {
          typename Net::Arc * from_arc = it.get_current();
          typename Net::Arc * to_arc   = 
            search_arc <Net> (net, net.get_tgt_node(from_arc), source);
          I(to_arc != NULL);
          I(net.get_tgt_node(to_arc) == source);
          to_source_list.append(to_arc);
        }

      for (typename DynDlist<typename Net::Arc *>::Iterator it(to_source_list); 
           it.has_current(); it.next())
        net.disconnect_arc(it.get_current());

      {
        Node_Iterator<Net> j(k);
        for (j.next(); j.has_current(); j.next())
          {
            typename Net::Node * sink = j.get_current();
            if (search_arc <Net> (net, source, sink) != NULL)
              continue; // existe arco ==> ignórelo y avance a siguiente

            DynDlist<typename Net::Arc*> from_sink_arcs;

            for (Node_Arc_Iterator<Net> it(sink); it.has_current(); it.next())
              from_sink_arcs.append(it.get_current());

            for (typename DynDlist<typename Net::Arc*>::Iterator 
                   it(from_sink_arcs); it.has_current(); it.next())
              net.disconnect_arc(it.get_current());
            {
              Net aux_net;
              {
                DynMapTreap<typename Net::Node*,typename Net::Arc*> map;
                for (Node_Iterator<Net> it(net); it.has_current(); it.next())
                  {
                    typename Net::Node * p = it.get_current();
                    if (p == source or p == sink)
                      {
                        NODE_COOKIE(p) = aux_net.insert_node();
                        continue;
                      }

                    typename Net::Node * ps = 
                      aux_net.insert_node(p->get_info());
                    typename Net::Node * pt = 
                      aux_net.insert_node(p->get_info());
                    map.insert(p, aux_net.insert_arc(ps, pt, 1));
                  }

                for (Arc_Iterator<Net> it(net); it.has_current(); it.next())
                  {
                    typename Net::Arc * a = it.get_current();

                    typename Net::Node * nsrc = net.get_src_node(a);
                    typename Net::Node * ntgt = net.get_tgt_node(a);
                    typename Net::Node * asrc = NULL;
                    typename Net::Node * atgt = NULL;

                    if (nsrc == source)
                      asrc = (typename Net::Node *) NODE_COOKIE(nsrc);
                    else
                      {
                        typename Net::Arc * arc = map.find(nsrc);
                        asrc = aux_net.get_tgt_node(arc);
                      }

                    if (ntgt == sink)
                      atgt = (typename Net::Node *) NODE_COOKIE(ntgt);
                    else
                      {
                        typename Net::Arc * arc = map.find(ntgt);
                        atgt = aux_net.get_src_node(arc);
                      }
                    aux_net.insert_arc(asrc, atgt, 1);
                  }
              } // fin de bloque que crea el mapeo

              const typename Net::Flow_Type flow = Max_Flow <Net> () (aux_net); 
              if (flow < min_k)
                min_k = flow;
            }

            while (not from_sink_arcs.is_empty())
              net.connect_arc(from_sink_arcs.get());

            net.reset(); // colocar flujo en cero
          }

        while (not to_source_list.is_empty())
          net.connect_arc(to_source_list.get());
      }
    }

  return min_k;
}


} // end namespace Aleph

# endif // TPL_KGRAPH_H