tpl_matgraph.H

/*
  This file is part of Aleph system

  Copyright (c) 2002, 2003, 2004, 2005, 2006
  UNIVERSITY LOS ANDES (ULA) Merida - REPÚBLICA BOLIVARIANA DE VENEZUELA  

  - Center of Studies in Microelectronics & Distributed Systems (CEMISID) 
  - ULA Computer Science Department
  - FUNDACITE Mérida - Ministerio de Ciencia y Tecnología

  PERMISSION TO USE, COPY, MODIFY AND DISTRIBUTE THIS SOFTWARE AND ITS
  DOCUMENTATION IS HEREBY GRANTED, PROVIDED THAT BOTH THE COPYRIGHT
  NOTICE AND THIS PERMISSION NOTICE APPEAR IN ALL COPIES OF THE
  SOFTWARE, DERIVATIVE WORKS OR MODIFIED VERSIONS, AND ANY PORTIONS
  THEREOF, AND THAT BOTH NOTICES APPEAR IN SUPPORTING DOCUMENTATION.

  Aleph 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.

  UNIVERSIDAD DE LOS ANDES requests users of this software to return to 

  Leandro Leon
  CEMISID 
  Ed La Hechicera 
  3er piso, ala sur
  Facultad de Ingenieria 
  Universidad de Los Andes 
  Merida - REPÚBLICA BOLIVARIANA DE VENEZUELA    or

  lrleon@ula.ve

  any improvements or extensions that they make and grant Universidad 
  de Los Andes (ULA) the rights to redistribute these changes. 

  Aleph is (or was) granted by: 
  - Consejo de Desarrollo Cientifico, Humanistico, Tecnico de la ULA 
    (CDCHT)
  - Fundacite Mérida
*/


# ifndef TPL_MAT_GRAPH_H
# define TPL_MAT_GRAPH_H

# include <tpl_graph.H>
# include <dyn_sort_utils.H>

using namespace Aleph;

namespace Aleph 
{

      template <typename GT> inline static 
  typename GT::Node * get_node(DynArray<typename GT::Node *> nodes, 
                               const long &                  i)
  {

    if (i >= nodes.size())
      throw std::out_of_range("Index of node out of range");

    return nodes.access(i);
  }
      template <typename GT>
  inline static long index_of_node(DynArray<typename GT::Node *> nodes,
                                   const long &                  n,
                                   typename GT::Node *           p) 
  {
    return Aleph::binary_search<typename GT::Node*>(nodes, p, 0, n - 1);
  }
  inline static long index_array(const long & i, const long & j, const long & n) 

  {
    if (i >= n or j >= n)
      throw std::out_of_range("Matrix index out of range");

    return i + j*n;
  }

      template <typename Entry>
  inline static Entry * read_matrix(const DynArray<Entry> & mat,
                                    const long &            i, 
                                    const long &            j, 
                                    const long &            n)
  {
    const long index = index_array(i, j, n);

    if (not mat.exist(index))
      return NULL;

    return &const_cast<Entry&>(mat.access(index));
  }
      template <typename Entry>
  inline static void write_matrix(DynArray<Entry> & mat,
                                  const long &      i, 
                                  const long &      j, 
                                  const long &      n, 
                                  const Entry &     entry)
  {
    mat[index_array(i, j, n)] = entry;
  }

      template <typename GT>
  class Map_Matrix_Graph
  {
    public:
    typedef GT List_Graph_Type;

    typedef typename GT::Node_Type Node_Type;

    typedef typename GT::Arc_Type Arc_Type;

    typedef typename GT::Node Node;

    typedef typename GT::Arc Arc;

  private:

    DynArray<Node*> nodes;
    GT * lgraph;
    mutable size_t num_nodes;
    struct Mat_Entry
    {
      Arc * arc;

      Mat_Entry(Arc * __arc = NULL) : arc(__arc) { /* empty */ }
    };
    DynArray<Mat_Entry> mat;

  public:

    Map_Matrix_Graph(GT & g);

    Map_Matrix_Graph(Map_Matrix_Graph & mat);
    inline Map_Matrix_Graph & operator = (Map_Matrix_Graph & mat);

    inline Map_Matrix_Graph & operator = (GT & g);
    inline Node * operator () (const long & i) const;
    inline long operator () (Node * node) const;
    inline Arc * operator () (Node * src_node, Node * tgt_node) const;
    inline Arc * operator () (const long & i, const long & j) const;  
    GT & get_list_graph() { return *lgraph; }
    const size_t & get_num_nodes() const { return num_nodes; }
    void copy_list_graph(GT & g);
  };

      template <class GT>
  typename GT::Node * Map_Matrix_Graph<GT>::operator () (const long & i) const
  {
    return get_node <GT> (nodes, i);
  }
      template <class GT>
  long Map_Matrix_Graph<GT>::operator () (typename GT::Node * node) const
  {
    return index_of_node <GT> (nodes, num_nodes, node);
  }
      template <class GT>
  typename GT::Arc * Map_Matrix_Graph<GT>::operator () (const long & i, 
                                                        const long & j) const
  { 
    Mat_Entry * mat_entry = read_matrix<Mat_Entry>(mat, i, j, num_nodes); 

    if (mat_entry == NULL)
      return NULL;

    return mat_entry->arc;
  } 

      template <class GT>
  typename GT::Arc * Map_Matrix_Graph<GT>::operator () (Node * src_node, 
                                                        Node * tgt_node) const
  { 
    Mat_Entry * mat_entry = 
      read_matrix<Mat_Entry>(mat, 
                             index_of_node<GT>(nodes, num_nodes, src_node), 
                             index_of_node<GT>(nodes, num_nodes, tgt_node), 
                             num_nodes); 

    if (mat_entry == NULL)
      return NULL;

    return mat_entry->arc;
  } 
      template <class GT>
  Map_Matrix_Graph<GT>::Map_Matrix_Graph(GT & g) 
    : lgraph(&g), num_nodes(g.get_num_nodes())
  {
    copy_list_graph(g);
  }
      template <class GT>
  Map_Matrix_Graph<GT>::Map_Matrix_Graph
      (Map_Matrix_Graph<GT>::Map_Matrix_Graph & mat) 
  {
    copy_list_graph(*(mat.lgraph));
  }

      template <class GT>
  Map_Matrix_Graph<GT>& Map_Matrix_Graph<GT>::operator = (Map_Matrix_Graph & mat)
  {
    if (this == &mat)
      return *this;

    copy_list_graph(*(mat.lgraph));

    return *this;
  }

      template <class GT>
  Map_Matrix_Graph<GT> & Map_Matrix_Graph<GT>::operator = (GT & g)
  {
    copy_list_graph(g);
  }
      template <class GT>
  void Map_Matrix_Graph<GT>::copy_list_graph(GT & g)
  {
        // copiar atributos
    lgraph    = &g;
    num_nodes = g.get_num_nodes();

    nodes.cut(); // limpiar arreglos dinámicos de contenidos anteriores
    mat.cut();

         // copiar los nodos de g hacia el arreglo nodes[]
    int i = 0;
    for (typename GT::Node_Iterator it(g); it.has_current(); it.next(), ++i)
      nodes[i] = it.get_current_node();

    quicksort(nodes); // ordenar nodes de modo que se soporte la búsqueda binaria

        // Para todos los arcos de g
    for (typename GT::Node_Iterator nit(g); nit.has_current(); nit.next())
    {
      Node * src = nit.get_current_node();

      const long src_idx = index_of_node<GT>(nodes, num_nodes, src);

          // para cada arco de src escribirlo en la matriz mat
      for (typename GT::Node_Arc_Iterator ait(src); ait.has_current(); ait.next())
        {
          Arc * arc = ait.get_current_arc();

          Node * tgt = g.get_connected_node(arc, src);
            
          const long tgt_idx = index_of_node<GT>(nodes, num_nodes, tgt);

          write_matrix<Mat_Entry>(mat, src_idx, tgt_idx, num_nodes, arc);
        }
    }
  }

      template <typename GT>
  class Matrix_Graph
  {

    public:

    typedef GT List_Graph_Type;

    typedef typename GT::Node_Type Node_Type;

    typedef typename GT::Arc_Type Arc_Type;

    typedef typename GT::Node Node;

    typedef typename GT::Arc Arc;

  private:

    DynArray<Node_Type> nodes;
    DynArray<Arc_Type>  arcs;
    mutable size_t      n;
    mutable Arc_Type Null_Value;
    void copy(Matrix_Graph & mat)
    {

      if (this == &mat)
        return;

      n          = mat.n;           // copiar atributos
      Null_Value = mat.Null_value;

      nodes.cut();                  // limpiar memoria de arreglos dinámicos
      arcs.cut();

      arcs.set_default_initial_value(Null_Value);
      
      for (int i = 0; i < n; ++i) // recorrer mat[i,j] y copiarla a nodes[], arcs[] 
        {
          nodes[i] = mat.nodes[i];

          for (int j = 0; j < n; ++j)
            {
              const long mat_index = index_array(i, j, n);

              if (not arcs.exist(mat_index))
                continue;

              arcs.touch(mat_index) = mat.arcs.access(mat_index);
            }
        }
    }

    void copy(GT & g)
    {
      n = g.get_num_nodes();

      DynArray<typename GT::Node *> ptr; // arreglo temporal 
      
      int i = 0;
      for (typename GT::Node_Iterator it(g); it.has_current(); it.next(), ++i)
        ptr[i] = it.get_current_node();

      quicksort(ptr); // ordenar por si se requiere relación con Map_Matrix_Graph

      arcs.set_default_initial_value(Null_Value); 

      for (i = 0; i < n; ++i) // coloca contenidos de ptr[] en nodes[]
        {
          typename GT::Node * src = ptr[i];

          nodes[i] = src->get_info();

          for (typename GT::Node_Arc_Iterator it(src); 
               it.has_current(); it.next())
            {
              typename GT::Arc * arc = it.get_current_arc();

              typename GT::Node * tgt = it.get_tgt_node();

              const long j = index_of_node<GT>(ptr, n, tgt);

              const long mat_index = index_array(i, j, n);

              arcs[mat_index] = arc->get_info();
            }
        }
    }

  public:

    const size_t & get_num_nodes() const { return n; }
    const Arc_Type & null_value() const { return Null_Value; }
    Matrix_Graph(GT & g, const Arc_Type & null) : Null_Value(null)
    {
      copy(g);
    }
    Matrix_Graph(Matrix_Graph & mat) 
    {
      copy(mat);
    }
    Matrix_Graph & operator = (Matrix_Graph & mat) 
    {
      copy(mat);

      return *this;
    }

    Matrix_Graph & operator = (GT & g) 
    {
      copy(g);

      return *this;
    }
    const Arc_Type & operator () (const long & i, const long & j) const
    {
      const long mat_index = index_array(i, j, n);

      if (not arcs.exist(mat_index)) // ¿Existe entrada?
        return Null_Value; // No ==> no hay arco

      return arcs.access(mat_index);      
    }
    Node_Type & operator () (const long & i) const
    {
      if (i >= n)
        throw std::out_of_range("node index out of range");

      return const_cast<Node_Type &>(nodes.access(i));
    }

    Arc_Type & operator () (const long & i, const long & j) 
    {
      const long mat_index = index_array(i, j, n);

      return arcs.touch(mat_index);
    }
  };

      template <typename GT, typename __Entry_Type>
  class Ady_Mat
  {

  public:

    typedef GT List_Graph_Type;

    typedef __Entry_Type Entry_Type;

    typedef typename GT::Node_Type Node_Type;

    typedef typename GT::Arc_Type Arc_Type;

    typedef typename GT::Node Node;

    typedef typename GT::Arc Arc;

  private:

    GT *                 lgraph;
    DynArray<Node*>      nodes;
    DynArray<Entry_Type> mat;
    mutable size_t       num_nodes;
    mutable Entry_Type   Null_Value;
    void test_same_graph(Ady_Mat & mat)
    {
      if (lgraph == mat.lgraph)
        return;

      throw std::domain_error("mat does not refers the same List_Graph than this");
    }

    void copy_nodes(GT & g)
    {
      lgraph     = &g;
      num_nodes  = g.get_num_nodes();

      nodes.cut(); // limpiar memoria por los nodos

          // coloca punteros a nodos en el arreglo nodes[]
      int i = 0;
      for (typename GT::Node_Iterator it(g); it.has_current(); it.next(), ++i)
        nodes[i] = it.get_current_node();

      quicksort(nodes); // ordena para luego hacer búsqueda binaria
    }

    Ady_Mat & copy(Ady_Mat & mat)
    {
      if (this == &mat)
        return *this;

      test_same_graph(mat);

      Null_Value = mat.Null_Value;

      copy(mat.lgraph);

      return *this;
    }

  public:

    Node * operator () (const long & i) const
    {
      return Aleph::get_node<GT>(nodes, i);
    }

    long operator () (Node * node) const
    {
      return index_of_node<GT>(nodes, num_nodes, node);
    }

    Entry_Type & operator () (const long & i, const long & j)
    {
      return mat.touch(index_array(i, j, num_nodes));
    }

    const Entry_Type & operator () (const long & i, const long & j) const
    {
      const long index = index_array(i, j, num_nodes);

      if (mat.exist(index))
        return mat.access(index);
        
      return Null_Value;
    }

    Entry_Type & operator () (Node * src, Node * tgt) 
    {
      return (*this)(index_of_node <GT> (nodes, num_nodes, src),
                     index_of_node <GT> (nodes, num_nodes, tgt));
    }

    const Entry_Type & operator () (Node * src, Node * tgt) const
    {
      return (*this)(index_of_node <GT> (nodes, num_nodes, src),
                     index_of_node <GT> (nodes, num_nodes, tgt));
    }
    GT & get_list_graph() { return *lgraph; }

    const Entry_Type & null_value() const { return Null_Value; }

    const size_t & get_num_nodes() const { return num_nodes; }
    Ady_Mat(GT & g) : lgraph(&g), num_nodes(lgraph->get_num_nodes())
    {
      copy_nodes(g);
    }
    Ady_Mat(GT & g, const Entry_Type & null) 
      : lgraph(&g), num_nodes(lgraph->get_num_nodes()), Null_Value(null)
    {
      copy_nodes(*lgraph);
    }
    void set_null_value(const Entry_Type & null)
    {
      Null_Value = null;
    }
    Ady_Mat(Ady_Mat & mat) 
    {
      copy(mat);
    }
    template <class Operation> void operate_all_arcs_list_graph();
    template <class Operation> void operate_all_arcs_list_graph(void * ptr);
    template <class Operation> void operate_all_arcs_matrix();

    template <class Operation> void operate_all_arcs_matrix(void * ptr); 
  }; 

      template <class GT, typename __Entry_Type>
      template <class Operation>
  void Ady_Mat<GT, __Entry_Type>::operate_all_arcs_list_graph()
  {
        // recorrer todos los nodos del grafo
    for (typename GT::Node_Iterator nit(*lgraph); nit.has_current(); nit.next())
      {
        Node * src = nit.get_current_node();

        const long src_idx = // obtener índice del nodo origen
          index_of_node<List_Graph_Type>(nodes, num_nodes, src);

            // recorrer todos los arcos del nodo origen
        for (typename GT::Node_Arc_Iterator at(src); at.has_current(); at.next())
          {
            Arc * arc = at.get_current_arc();
          
            const long tgt_idx = // obtener índice del nodo destino
              index_of_node<List_Graph_Type>(nodes, num_nodes, 
                                             arc->get_tgt_node());

            Entry_Type & entry = // asegurar acceso a mat(src_idx, tgt_idx)
              mat.touch(index_array(src_idx, tgt_idx, num_nodes));

            Operation () (*this, arc, src_idx, tgt_idx, entry);
          }
      }
  }

      template <class GT, typename __Entry_Type>
      template <class Operation>
  void Ady_Mat<GT, __Entry_Type>::operate_all_arcs_matrix()
  {
    const long & n = num_nodes;

    for (int s = 0; s < n; ++s)
      {
        Node * src_node = get_node<GT>(nodes, s);

        for (int t = 0; t < n; ++t)
          {
            Node * tgt_node = get_node<GT>(nodes, t);

            Entry_Type & entry = mat.touch(index_array(s, t, num_nodes));

            Operation () (*this, src_node, tgt_node, s, t, entry);
          }
      }
  }
      template <class GT, typename __Entry_Type>
      template <class Operation>
  void Ady_Mat<GT, __Entry_Type>::operate_all_arcs_list_graph(void * ptr)
  {
        // recorrer todos los nodos del grafo
    for (typename GT::Node_Iterator nit(*lgraph); nit.has_current(); nit.next())
      {
        Node * src = nit.get_current_node();

        const long src_idx = // obtener índice del nodo origen
          index_of_node<List_Graph_Type>(nodes, num_nodes, src);

            // recorrer todos los arcos del nodo origen
        for (typename GT::Node_Arc_Iterator at(src); at.has_current(); at.next())
          {
            Arc * arc = at.get_current_arc();

            Node * tgt = lgraph->get_tgt_node(arc);
          
            const long tgt_idx = // obtener índice del nodo destino
              index_of_node<List_Graph_Type>(nodes, num_nodes, tgt);

            Entry_Type & entry = // asegurar acceso a mat(src_idx, tgt_idx)
              mat.touch(index_array(src_idx, tgt_idx, num_nodes));

            Operation () (*this, arc, src_idx, tgt_idx, entry, ptr);
          }
      }
  }

      template <class GT, typename __Entry_Type>
      template <class Operation>
  void Ady_Mat<GT, __Entry_Type>::operate_all_arcs_matrix(void * ptr)
  {
    const long & n = num_nodes;

    for (int s = 0; s < n; ++s)
      {
        Node * src_node = get_node<GT>(nodes, s);

        for (int t = 0; t < n; ++t)
          {
            Node * tgt_node = get_node<GT>(nodes, t);

            Entry_Type & entry = mat.touch(index_array(s, t, num_nodes));

            Operation () (*this, src_node, tgt_node, s, t, entry, ptr);
          }
      }
  }

      template <class GT>
  class Bit_Mat_Graph
  {

  public:

    typedef GT List_Graph_Type;

    typedef typename GT::Node Node;

    typedef typename GT::Arc Arc;

  private:

    BitArray bit_array;
    GT *                         lgraph;
    DynArray<typename GT::Node*> nodes;
    mutable size_t               n;
    void copy_list_graph(GT & g)
    {
      n = g.get_num_nodes();

      nodes.cut(); // liberar memoria 

          // copiar todos los nodos de g al arreglo nodes[]
      int i = 0;
      for (typename GT::Node_Iterator it(g); it.has_current(); it.next())
        nodes[i++] = static_cast<typename GT::Node*>(it.get_current_node());

      quicksort(nodes); // ordenar para luego hacer búsqueda binaria

      bit_array.resize(n*n); // reajustar dimensión al grafo que se asigna

          // recorrer todos los nodos de g para asignar los arcos en bit_array
      for (typename GT::Node_Iterator it(g); it.has_current(); it.next())
        {
          typename GT::Node * src = it.get_current_node();

          const size_t src_idx = // obtener índice de nodo origen
            index_of_node<List_Graph_Type>(nodes, n, src);

          for (typename GT::Node_Arc_Iterator jt(src); jt.has_current(); jt.next())
            {
              typename GT::Node * tgt = jt.get_tgt_node();

              const size_t tgt_idx = // obtener índice de nodo destino
                index_of_node<List_Graph_Type>(nodes, n, tgt);

              bit_array[index_array(src_idx, tgt_idx,n)] = 1;
            }
        }
    }
    struct Proxy
    {
      BitArray & bit_array;

      const size_t bit_index;

      Proxy(Bit_Mat_Graph & __bitmat, const long & i, const long & j)
        : bit_array(__bitmat.bit_array), bit_index(index_array(i, j, __bitmat.n))
      {
        // empty
      }

      Proxy& operator = (const Proxy & proxy)
      {
        bit_array[bit_index] = proxy.bit_array[proxy.bit_index];
      }
      
      Proxy& operator = (const int & i)
      {
        bit_array[bit_index] = i;

        return *this;
      }

      operator int () const
      {
        return bit_array[bit_index];
      }
    };

  public: 

    const size_t & get_num_nodes() const { return n; }
    Bit_Mat_Graph() : lgraph(NULL) { /* empty */ }

    Bit_Mat_Graph(GT & g) : lgraph(&g) 
    {
      copy_list_graph(g);
    }

    Bit_Mat_Graph(const Bit_Mat_Graph & bitmat)
      : bit_array(bitmat.bit_array), lgraph(bitmat.lgraph), 
        nodes(bitmat.nodes), n(bitmat.n)
    {
      // empty
    }

    Bit_Mat_Graph(const size_t & dim) 
      : bit_array(dim*dim), lgraph(NULL),
        nodes(dim), n(dim)
    {
     /* empty */ 
    }
    void set_list_graph(GT & g)
    {
      lgraph = &g;

      copy_list_graph(g);
    }

    GT * get_list_graph() { return lgraph; }
    Bit_Mat_Graph & operator = (const Bit_Mat_Graph & bitmat)
    {
      if (this == &bitmat)
        return *this;

      lgraph    = bitmat.lgraph;
      bit_array = bitmat.bit_array;

      return *this;
    }

    Bit_Mat_Graph & operator = (GT & g)
    {
      if (&g == lgraph)
        return *this;

      copy_list_graph(g);

      return *this;
    }
    Node * operator () (const long & i) const
    {

      if (lgraph == NULL)
        throw std::domain_error("There is no a List_Graph object");

      return Aleph::get_node<GT>(nodes, i);
    }

    long operator () (Node * node) const
    {

      if (lgraph == NULL)
        throw std::domain_error("There is no a List_Graph object");

      return index_of_node<GT>(nodes, n, node);
    }
    Proxy operator () (const long & i, const long & j)
    {
      return Proxy(*this, i, j);
    }

    Proxy operator () (const long & i, const long & j) const
    {
      return Proxy(const_cast<Bit_Mat_Graph&>(*this), i, j);
    }

    Proxy operator () (Node * src_node, Node * tgt_node) 
    {
      if (lgraph == NULL)
        throw std::domain_error("There is no a List_Graph object");

      return Proxy(*this, index_of_node<GT>(nodes, n, src_node), 
                   index_of_node<GT>(nodes, n, tgt_node)); 
    }

    Proxy operator () (Node * src_node, Node * tgt_node) const
    {
      if (lgraph == NULL)
        throw std::domain_error("There is no a List_Graph object");

      return Proxy(*this, index_of_node<GT>(nodes, n, src_node), 
                   index_of_node<GT>(nodes, n, tgt_node)); 
    }
  };

} // end namespace Aleph

# endif // TPL_MAT_GRAPH_H

---