tpl_indexGraph.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_INDEXGRAPH
# define TPL_INDEXGRAPH

# include <tpl_indexNode.H>
# include <tpl_indexArc.H>

namespace Aleph
{

template <class GT, class Compare = Dft_Node_Cmp<GT>,
          template <class /* Key */, class /* Compare */> class Tree = Treap>
class Index_Graph
{
private:

  typedef typename GT::Arc GT_Arc;
  typedef typename GT::Node GT_Node;
  typedef typename GT::Arc_Type GT_Arc_Type;
  typedef typename GT::Node_Type GT_Node_Type;

  IndexNode<GT, Compare, Tree> idx_node;
  IndexArc<GT, Tree>           idx_arc;

public:

  Index_Graph(GT & g) : idx_node(g), idx_arc(g)
  {
    // empty
  }

  GT_Node * insert_node(const GT_Node_Type & info)
  {
    return idx_node.insert_in_graph(info);
  }

  GT_Arc * insert_arc(GT_Node * src, GT_Node * tgt,
                      const GT_Arc_Type & info = GT_Arc_Type())
  {
    if (idx_node.search(src) == nullptr)
      throw std::domain_error("src node not in index");

    if (idx_node.search(tgt) == nullptr)
      throw std::domain_error("tgt node not in index");

    return idx_arc.insert_in_graph(src, tgt, info);
  }

  GT_Node * search_node(GT_Node * p)
  {
    return idx_node.search(p);
  }

  GT_Node * search_node(const GT_Node_Type & info)
  {
    return idx_node.search(info);
  }

  GT_Arc * search_arc(GT_Node * src, GT_Node * tgt)
  {
    return idx_arc.search(src, tgt);
  }

  void remove_node(GT_Node * p)
  {
    // eliminar del índice los arcos emanantes del nodo (ellos serán
    // eliminados por la eliminación de nodo del grafo)
    for (typename GT::Node_Arc_Iterator it(p); it.has_curr(); it.next_ne())
      idx_arc.remove(it.get_curr_ne());

    return idx_node.remove_from_graph(p);
  }

  void remove_arc(GT_Arc * a)
  {
    return idx_arc.remove_from_graph(a);
  }

  size_t get_num_arcs() const { return idx_arc.size(); }

  size_t get_num_nodes() const { return idx_node.size(); }
};

  template <class GT> inline
  bool are_equal(const GT & g1, const GT & g2)
  {
    if (g1.vsize() != g2.vsize() or g1.esize() != g2.esize())
      return false;

    {
      IndexNode<GT> t2(const_cast<GT&>(g2));
      if (not g1.all_nodes([&t2] (auto p)
                           {
                             auto q = t2.search(p);
                             if (q == nullptr)
                               return false;
                             GT::map_nodes(p, q);
                             return true;
                           }))
        return false;
    }

    IndexArc<GT> t2(const_cast<GT&>(g2));
    return g1.all_arcs([idx = &t2, &g1] (auto a)
                       {
                         auto s1 = g1.get_src_node(a);
                         auto t1 = g1.get_tgt_node(a);
                         auto s2 = mapped_node<GT>(s1);
                         auto t2 = mapped_node<GT>(t1);
                         auto a2 = idx->search(s2, t2);
                         if (a2 == nullptr)
                           return false;
                         return a2->get_info() == a->get_info();
                       });
  }

}

# endif // TPL_INDEXGRAPH