Página principal | Lista de namespace | Jerarquía de la clase | Lista de componentes | Directories | Lista de archivos | Miembros del Namespace  | Miembros de las clases | Archivos de los miembros | Páginas relacionadas
ADH::Graph

Referencia de la Clase ADH::Graph

Contenedor grapo dirigido en que los vértices son hileras y los valores de los arcos son enteros. Más...

#include <ADH_Graph.h>

Lista de todos los miembros.

Tipos públicos

typedef std::string key_type
 Tipo de los vértices.
typedef std::map< std::string,
int > 		mapped_type
 Lista de aristas para un vértice.
typedef Rep::value_type value_type
 Nombre estándar del objeto contenido.
typedef value_type & reference
 Referencia al objeto contenido.
typedef const value_type & const_reference
 Referencia constante al objeto contenido.

Métodos públicos

 Graph ()
 Constructor de vector.
 Graph (const Graph &G)
 Constructor de copia.
 ~Graph ()
 Destructor.
bool empty () const
 Retorna "true" si el contenedor está vacío.
Graph & operator= (const Graph &G)
 Copia *this = G.
void swap (Graph &M)
 Intercambia los valores de "M" <==> "*this".
const_iterator begin () const
 Denota al primer valor del contenedor.
const_iterator end () const
 Denota el valor que ya está fuera del contenedor.
bool isVertex (const std::string &vtx) const
 Retorna "true" si existe el vértice vtx.
bool isArc (const std::string &src, const std::string &dst, int &val) const
 Retorna "true" si existe el arco src->dst.
void set (const std::string &vtx)
 Establece que el grafo tiene el vértice vtx.
void set (const std::string &src, const std::string &dst, int val)
 Establece que el grafo tiene la arista src->dst con valor "val".
bool connected (const std::string &src, const std::string &dst, std::list< std::string > &C)
 Determina si existe un camino en el grafo comenzando en "src" y terminando en "dst".

Tipos privados

typedef std::map< key_type,
mapped_type > 		Rep
 Abreviatura para el Rep, implementado con un diccionario.

Atributos privados

Rep m_DICC
 Diccionario que contiene los valores del grafo.

Amigas

class test_Graph
 Datos de prueba de la clase.
std::ostream & operator<< (std::ostream &COUT, const Graph &G)
 Graba el valor de "G" en el flujo "COUT".
void dump (std::ostream &COUT, const Graph &G)
 Graba el valor de "G" en el flujo "COUT".
bool check_ok (const Graph &DDD)
 Verifica la invariante del grafo.

Clases

class  const_iterator
 Iteradores [CONST] simples para la clase "Graph". Más...

Descripción detallada

Contenedor grapo dirigido en que los vértices son hileras y los valores de los arcos son enteros.

Definición en la línea 26 del archivo ADH_Graph.h.

Documentación de los 'Tipos Definidos' miembros de la clase

typedef std::string ADH::Graph::key_type
 

Tipo de los vértices.

Definición en la línea 28 del archivo ADH_Graph.h.

typedef std::map< std::string, int > ADH::Graph::mapped_type
 

Lista de aristas para un vértice.

Definición en la línea 29 del archivo ADH_Graph.h.

typedef std::map< key_type, mapped_type > ADH::Graph::Rep [private]
 

Abreviatura para el Rep, implementado con un diccionario.

Definición en la línea 32 del archivo ADH_Graph.h.

typedef Rep::value_type ADH::Graph::value_type
 

Nombre estándar del objeto contenido.

Definición en la línea 34 del archivo ADH_Graph.h.

typedef value_type& ADH::Graph::reference
 

Referencia al objeto contenido.

Definición en la línea 35 del archivo ADH_Graph.h.

typedef const value_type& ADH::Graph::const_reference
 

Referencia constante al objeto contenido.

Definición en la línea 36 del archivo ADH_Graph.h.

Documentación del constructor y destructor

ADH::Graph::Graph (   )  [inline]
 

Constructor de vector.

Definición en la línea 77 del archivo ADH_Graph.h.

ADH::Graph::Graph (  const Graph &  G  )  [inline]
 

Constructor de copia.

Definición en la línea 78 del archivo ADH_Graph.h.

ADH::Graph::~Graph (   )  [inline]
 

Destructor.

Definición en la línea 79 del archivo ADH_Graph.h.

Documentación de las funciones miembro

bool ADH::Graph::empty (   )  const [inline]
 

Retorna "true" si el contenedor está vacío.

Definición en la línea 81 del archivo ADH_Graph.h.

Graph& ADH::Graph::operator= (  const Graph &  G  )  [inline]
 

Copia *this = G.

Definición en la línea 83 del archivo ADH_Graph.h.

void ADH::Graph::swap (  Graph &  M  )  [inline]
 

Intercambia los valores de "M" <==> "*this".

Definición en la línea 85 del archivo ADH_Graph.h.

const_iterator ADH::Graph::begin (   )  const [inline]
 

Denota al primer valor del contenedor.

Definición en la línea 88 del archivo ADH_Graph.h.

const_iterator ADH::Graph::end (   )  const [inline]
 

Denota el valor que ya está fuera del contenedor.

Definición en la línea 90 del archivo ADH_Graph.h.

bool ADH::Graph::isVertex (  const std::string &  vtx  )  const
 

Retorna "true" si existe el vértice vtx. 

 
Ver también:
test_Graph::test_isVertex() 




Definición en la línea 130 del archivo ADH_Graph.cpp.    

  







  

    
      

        

          bool ADH::Graph::isArc           
          ( 
          const std::string & 
           src, 
        

        

          
          
          const std::string & 
           dst, 
        

        

          
          
          int & 
           val
        

        

          
          ) 
           const
        

      

    		
  





  

    
       
    
    



Retorna "true" si existe el arco src->dst. 



    

  • Si el arco existe, en val se copia el valor asociado al arco.
  • Si el arco no existe, retorna "false" y no cambia el valor de val.



 
 
Ver también:
test_Graph::test_isVertex() 




Definición en la línea 144 del archivo ADH_Graph.cpp.    

  







  

    
      

        

          void ADH::Graph::set           
          ( 
          const std::string & 
           vtx          
           ) 
          
        

      

    		
  





  

    
       
    
    



Establece que el grafo tiene el vértice vtx. 





Definición en la línea 108 del archivo ADH_Graph.cpp.    

  







  

    
      

        

          void ADH::Graph::set           
          ( 
          const std::string & 
           src, 
        

        

          
          
          const std::string & 
           dst, 
        

        

          
          
          int 
           val
        

        

          
          ) 
          
        

      

    		
  





  

    
       
    
    



Establece que el grafo tiene la arista src->dst con valor "val". 



    

  • Si ya la arista estaba en el grafo, no la agrega ni le cambia el valor asociado. 




Definición en la línea 79 del archivo ADH_Graph.cpp.    

  







  

    
      

        

          bool ADH::Graph::connected           
          ( 
          const std::string & 
           src, 
        

        

          
          
          const std::string & 
           dst, 
        

        

          
          
          std::list< std::string > & 
           C
        

        

          
          ) 
          
        

      

    		
  





  

    
       
    
    



Determina si existe un camino en el grafo comenzando en "src" y terminando en "dst". 



    

  • Retorna "true" cuando el camino existe, y "false" en caso contrario.
  • La lista "C" contiene la secuencia de nodos del camino.
  • Si no hay camino, la lista "C" queda vacía.



 
 
Ver también:
test_Graph::test_connected() 




Definición en la línea 206 del archivo ADH_Graph.cpp.    

  




Documentación de las funciones relacionadas y clases amigas





  

    
      

        

          friend class test_Graph [friend]          
        

      

    		
  





  

    
       
    
    



Datos de prueba de la clase. 





Definición en la línea 96 del archivo ADH_Graph.h.    

  







  

    
      

        

          std::ostream& operator<<           
          ( 
          std::ostream & 
           COUT, 
        

        

          
          
          const Graph & 
           G
        

        

          
          ) 
           [friend]
        

      

    		
  





  

    
       
    
    



Graba el valor de "G" en el flujo "COUT". 





Definición en la línea 163 del archivo ADH_Graph.cpp.    

  







  

    
      

        

          void dump           
          ( 
          std::ostream & 
           COUT, 
        

        

          
          
          const Graph & 
           G
        

        

          
          ) 
           [friend]
        

      

    		
  





  

    
       
    
    



Graba el valor de "G" en el flujo "COUT". 





Definición en la línea 181 del archivo ADH_Graph.cpp.    

  







  

    
      

        

          bool check_ok           
          ( 
          const Graph & 
           DDD          
           ) 
           [friend]
        

      

    		
  





  

    
       
    
    



Verifica la invariante del grafo. 



    

  • Regresa "true" si el grafo "DDD" contiene un valor correcto
  • Podría retornar "true" para un grafo lista cuyo valor está corrupto
  • Podría no retornar si el grafo tiene su valor corrupto




    

  • Como los valores del grafo están ordenados, verifica que la lista que DDD contiene esté ordenada




Rep Diagrama de la clase
        m_DICC[]
    +------+-----------------------------------+
    |      | +---------+---------+-----------+ |
    |  F   | | A(1)=>2 | A(2)=>8 | A(3)==>64 | |
    |      | +---------+---------+-----------+ |
    +------+-----------------------------------+
    |      | +------+                          |         A(1)         C(1)
    | A(1) | | B=>2 |                          |        /    \       /    \
    |      | +------+                          |       /      \     /      \
    +------+-----------------------------------+    F----A(2)----B--        --D
    |      | +------+                          |       \      /     \      /
    | A(2) | | B=>8 |                          |        \    /       \    /
    |      | +------+                          |         A(3)         C(2)
    +------+-----------------------------------+
    |      | +-------+                         |
    | A(3) | | B=>64 |                         |    G.set("F", "A(1)",  2 ); G.set( "A(1)", "B",  2 );
    |      | +-------+                         |    G.set("F", "A(2)",  8 ); G.set( "A(2)", "B",  8 );
    +------+-----------------------------------+    G.set("F", "A(3)", 64 ); G.set( "A(3)", "B", 64 );
    |      | +---------+----------+            |
    |  B   | | C(1)=>3 | C(2)=>27 |            |    G.set("B", "C(1)",  3 ); G.set( "C(1)", "D",  3 );
    |      | +---------+----------+            |    G.set("B", "C(2)", 27 ); G.set( "C(2)", "D", 27 );
    +------+-----------------------------------+
    |      | +------+                          |
    | C(1) | | D=>2 |                          |
    |      | +------+                          |
    +------+-----------------------------------+
    |      | +------+                          |
    | C(2) | | D=>8 |                          |
    |      | +------+                          |
    +------+-----------------------------------+
    |      | +-+                               |
    |  D   | | |                               |     D no es salida de ninguna arista
    |      | +-+                               |     - Su diccionario está vacío
    +------+-----------------------------------+



    

  • El grafo está implementado como un diccionario que contiene otro diccionario.
  • La llave del diccionario principal es el vértice que comienza un arco.
  • Cada vértice tiene asociado un diccionario cuya llave es el vértice de destino. Este es el diccionario que representa cada arista.
  • El valor numérico asociado en el diccionario de cada arista es el valor de la arista.
  • Si un vértice no participa en ninguna arista, tampoco aparece en el grafo. / - En el grado sólo están almacenados los vértices que participan en alguna arista.



- Invariante: ningún objeto puede estar almacenado en la posición nula. 


Definición en la línea 69 del archivo ADH_Graph.cpp.    

  




Documentación de los datos miembro





  

    
      

        

          Rep ADH::Graph::m_DICC [private]          
        

      

    		
  





  

    
       
    
    



Diccionario que contiene los valores del grafo. 





Definición en la línea 105 del archivo ADH_Graph.h.    

  




La documentación para esta clase fué generada a partir de los siguientes archivos:

Generado el Thu Nov 15 15:47:46 2007 para Clase ADH_Graph: por 

doxygen 1.4.1 





Hosted by www.Geocities.ws





        






1