[B]asic module for [unit] program testing:
 All Classes Namespaces Files Functions Variables Typedefs Enumerator Friends Defines
Classes | Public Types | Public Member Functions | Private Types | Private Member Functions | Private Attributes | Friends
ADH::Graph Class Reference

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

#include <ADH_Graph.h>

List of all members.

Classes

class  const_iterator
 Iteradores [CONST] para obtener todos los vértices de un grafo. More...
class  Rep_const_iterator
 Iteradores [CONST] simples para la clase "Graph". More...

Public Types

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.

Public Member Functions

 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".
void clear ()
 Deja al grafo vacío.
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".
void vertexList (std::list< std::string > &L) const
 Retorna la lista de todos los vértices del grafo.
void vertexList (std::string vtx, std::list< std::string > &L) const
 Retorna la lista de todos los vértices a los que se llega con un arco desde "vtx".

Private Types

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

Private Member Functions

Rep_const_iterator begin_Rep () const
 Denota al primer valor del contenedor.
Rep_const_iterator end_Rep () const
 Denota el valor que ya está fuera del contenedor.

Private Attributes

Rep m_DICC
 Diccionario que contiene los valores del grafo.

Friends

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.

Detailed Description

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

Definition at line 26 of file ADH_Graph.h.

Member Typedef Documentation

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

Tipo de los vértices.

Definition at line 28 of file ADH_Graph.h.

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

Lista de aristas para un vértice.

Definition at line 29 of file ADH_Graph.h.

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

Abreviatura para el Rep, implementado con un diccionario.

Definition at line 32 of file ADH_Graph.h.

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

Nombre estándar del objeto contenido.

Definition at line 34 of file ADH_Graph.h.

typedef value_type& ADH::Graph::reference

Referencia al objeto contenido.

Definition at line 35 of file ADH_Graph.h.

typedef const value_type& ADH::Graph::const_reference

Referencia constante al objeto contenido.

Definition at line 36 of file ADH_Graph.h.

Constructor & Destructor Documentation

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

Constructor de vector.

Definition at line 116 of file ADH_Graph.h.

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

Constructor de copia.

Definition at line 117 of file ADH_Graph.h.

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

Destructor.

Definition at line 118 of file ADH_Graph.h.

Member Function Documentation

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

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

Definition at line 120 of file ADH_Graph.h.

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

Copia *this = G

Definition at line 122 of file ADH_Graph.h.

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

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

Definition at line 124 of file ADH_Graph.h.

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

Deja al grafo vacío.

Definition at line 125 of file ADH_Graph.h.

Rep_const_iterator ADH::Graph::begin_Rep ( ) const [inline, private]

Denota al primer valor del contenedor.

Definition at line 128 of file ADH_Graph.h.

Rep_const_iterator ADH::Graph::end_Rep ( ) const [inline, private]

Denota el valor que ya está fuera del contenedor.

Definition at line 130 of file ADH_Graph.h.

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

Denota al primer valor del contenedor.

Definition at line 133 of file ADH_Graph.h.

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

Denota el valor que ya está fuera del contenedor.

Definition at line 135 of file ADH_Graph.h.

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

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

    {{ // test::isVertex()
        Graph G; int val = 666;
        G.set( "F", "D", 2*2*2 );
        assertTrue( G.isVertex( "F" ) ) ;
        assertTrue( G.isVertex( "D" ) ) ;
        assertTrue( val == 666 && "initial val" );
        assertTrue( G.isArc( "F" , "D", val ) );
        assertTrue( val == 2*2*2 && "returned val" );
        val = 666;
        assertTrue( ! G.isArc( "D" , "F", val ) );
        assertTrue( val == 666 && "unchanged val" );
    }}

See also:
test_Graph::test_isVertex()

Definition at line 130 of file 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.
    {{ // test::isVertex()
        Graph G; int val = 666;
        G.set( "F", "D", 2*2*2 );
        assertTrue( G.isVertex( "F" ) ) ;
        assertTrue( G.isVertex( "D" ) ) ;
        assertTrue( val == 666 && "initial val" );
        assertTrue( G.isArc( "F" , "D", val ) );
        assertTrue( val == 2*2*2 && "returned val" );
        val = 666;
        assertTrue( ! G.isArc( "D" , "F", val ) );
        assertTrue( val == 666 && "unchanged val" );
    }}

See also:
test_Graph::test_isVertex()

Definition at line 144 of file ADH_Graph.cpp.

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

Establece que el grafo tiene el vértice vtx.

Definition at line 108 of file 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.

Definition at line 79 of file ADH_Graph.cpp.

void ADH::Graph::vertexList ( std::list< std::string > &  L) const

Retorna la lista de todos los vértices del grafo.

  • Deja la lista "L" vacía si no existe ningún vértice en el grafo.

Definition at line 165 of file ADH_Graph.cpp.

void ADH::Graph::vertexList ( std::string  vtx,
std::list< std::string > &  L 
) const

Retorna la lista de todos los vértices a los que se llega con un arco desde "vtx".

  • Deja la lista "L" vacía si no existe el vértice "vtx".
  • Deja la lista "L" vacía si no existe ningún arco que comience con el vértice "vtx".
    {{ // test::diagram()
         A(1)         C(1)        O(1)---->O(2)
        /    \       /    \       /|\       |
       /      \     /      \       |        |
    F->--A(2)-->-B->        ->D    |        |
       \      /     \      /       |        |
        \    /       \    /        |       \|/
         A(3)         C(2)        O(4)<----O(3)
    }}
    {{ // test::vertexList()
        std::list< std::string > L;
        G.vertexList( L );
        assertTrue( L.size() == 12 );

        G.vertexList( "F", L );
        assertTrue( L.size() == 3 );
        assertTrue( find(L.begin(), L.end() ,"A(1)") != L.end() );
        assertTrue( find(L.begin(), L.end() ,"A(2)") != L.end() );
        assertTrue( find(L.begin(), L.end() ,"A(3)") != L.end() );

        G.vertexList( "D", L );
        assertTrue( L.empty() );

        G.vertexList( "A(2)", L );
        assertTrue( L.size() == 1 );
        assertTrue( L.front() == "B" );
    }}

See also:
test_Graph::test_vertexList()

Definition at line 184 of file ADH_Graph.cpp.

Friends And Related Function Documentation

friend class test_Graph [friend]

Datos de prueba de la clase.

Definition at line 141 of file ADH_Graph.h.

std::ostream& operator<< ( std::ostream &  COUT,
const Graph &  G 
) [friend]

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

void dump ( std::ostream &  COUT,
const Graph &  G 
) [friend]

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

bool check_ok ( const Graph &  DDD) [friend]

Verifica la invariante del grafo. 

- Regresa \c "true" si el grafo \c "DDD" contiene un valor correcto
- Podría retornar \c "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

\par 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.

Definition at line 69 of file ADH_Graph.cpp.

Member Data Documentation

Rep ADH::Graph::m_DICC [private]

Diccionario que contiene los valores del grafo.

Definition at line 151 of file ADH_Graph.h.

The documentation for this class was generated from the following files:
Generated on Fri May 25 2012 08:28:13 for [B]asic module for [unit] program testing: by   doxygen 1.8.0