[B]asic module for [unit] program testing:
 All Classes Namespaces Files Functions Variables Typedefs Enumerator Friends Defines
Classes | Functions
ADH Namespace Reference

ADH: Adolfo Di Mare H. More...

Classes

class  Graph
 Contenedor grapo dirigido en que los vértices son hileras y los valores de los arcos son enteros. More...
class  test_Graph
 Clase simple para probar la clase ADH_Graph. More...

Functions

bool check_ok (const Graph &DDD)
 Verifica la invariante del grafo.
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 connected (const Graph &G,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".
bool isConnected (const Graph &G)
 Determina si el grafo "G" está conectado.
bool isCircuit (const Graph &G, std::list< std::string > &C)
 Determina si el camino "C" es un circuito.
bool isTree (const Graph &G)
 Determina si el grafo "G" es o no un árbol.
bool spanningTree (const Graph &G, Graph &T)
 Construye un árbol de expansión (spanning tree) "T" para el grafo "G".
bool connected_set (const Graph &G, std::set< std::string > &S, const std::string &src, const std::string &dst, std::list< std::string > &C)
 Determina si existe un camino desde "src" hasta "dst" sin pasar por los nodos de "S".

Detailed Description

ADH: Adolfo Di Mare H.

Function Documentation

bool ADH::check_ok ( const Graph &  DDD)

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.

std::ostream & ADH::operator<< ( std::ostream &  COUT,
const Graph &  G 
)

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

Definition at line 18 of file ADH_Graph_Lib.cpp.

void ADH::dump ( std::ostream &  COUT,
const Graph &  G 
)

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

Definition at line 36 of file ADH_Graph_Lib.cpp.

bool ADH::connected ( const Graph &  G,
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".

  • Si src == dst retorna "true" (un vértice siempre está conectado consigo mismo).
  • 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.
    {{ // test::diagram()
         A(1)         C(1)        O(1)---->O(2)
        /    \       /    \       /|\       |
       /      \     /      \       |        |
    F->--A(2)-->-B->        ->D    |        |
       \      /     \      /       |        |
        \    /       \    /        |       \|/
         A(3)         C(2)        O(4)<----O(3)
    }}
    {{ // test::connected()
        std::list< std::string > C; // camino en el grafo
        std::list< std::string >::iterator it;

        assertTrue( ! connected( G , "???" , "???",  C ) ); // no existe el vértice
        assertTrue( ! connected( G ,  "F" ,  "O(4)", C ) ); // grafo no conexo
        assertTrue( C.size() == 0 );
        assertTrue( ! connected( G , "D" , "F"   , C ) ); // el grafo es dirigido
        assertTrue( C.size() == 0 );

        assertTrue( connected( G , "F" , "F", C ) );       // si está conectado
        assertTrue( C.size() == 1 && C.front() == "F" ); // porque ya está ahí

        assertTrue( ! connected( G , "D", "A(2)" , C ) ); assertTrue( C.size() == 0 );
        assertTrue( connected( G , "A(2)" , "D", C ) );   assertTrue( C.size() == 4 );
        assertTrue( C.front() == "A(2)" && C.back() == "D" );
        it = C.begin(); it++;
        assertTrue( *it == "B" ); // 2do nodo en el camino
        it++;
        assertTrue( *it == "C(1)" || *it == "C(2)" ); // 3er nodo en el camino
    }}

See also:
test_Graph::test_connected()

Definition at line 105 of file ADH_Graph_Lib.cpp.

bool ADH::isConnected ( const Graph &  G)

Determina si el grafo "G" está conectado.

  • Determnina si siempre existe un camino entre cualesquiera 2 nodos.
    {{ // test::isConnected()
        Graph G;
        std::list<std::string> C;
        std::list<std::string> tmp;
        G.set("M(1)", "M(2)", 13 );  //  M(1)<------->M(2)<--
        G.set("M(2)", "M(3)", 15 );  //   /\           |    |
        G.set("M(3)", "M(4)", 17 );  //   |            |    |
        G.set("M(4)", "M(2)", 19 );  //   |            \/   |
        G.set("M(2)", "M(1)", 23 );  //  M(4)<------- M(3)  |
        G.set("M(4)", "M(1)", 29 );  //   |                 |
                                     //   +------->---------+
        assertTrue( isConnected(G) );
        G.vertexList( C );

        // Con este doble ciclo se prueba que "isConnected()"  funciona ya que dan los mismos resultados
        for ( std::list< std::string >::iterator it = C.begin(); it != C.end(); ++it ) {
            for ( std::list< std::string >::iterator jt = C.begin(); jt != C.end(); ++jt ) {
                assertTrue ( connected( G , *it , *jt , tmp ) );
            }
        }
        assertTrue( !isTree( G ) ); // No cuenta con las características de un árbol
    }}

See also:
test_Graph::isConnected()
Author:
Joseiby Hernadez Cedeño joher.nosp@m.ce@y.nosp@m.ahoo..nosp@m.com

Definition at line 133 of file ADH_Graph_Lib.cpp.

bool ADH::isCircuit ( const Graph &  G,
std::list< std::string > &  C 
)

Determina si el camino "C" es un circuito.

Para que sea un circuito debe:

  • Realmente ser un camino
  • Que el primer y ultimo nodo sean el mismo
    {{ // test::isCircuit()
    }}

See also:
test_Graph::isCircuit()
Author:
Joseiby Hernadez Cedeño joher.nosp@m.ce@y.nosp@m.ahoo..nosp@m.com

Definition at line 161 of file ADH_Graph_Lib.cpp.

bool ADH::isTree ( const Graph &  G)

Determina si el grafo "G" es o no un árbol. 

Para que sea un árbol debe:
- Haber una sola raiz (nodo del cual se llegué a todos).
- Poder alcanzar cada uno de los nodos DIRECTAMENTE desde un solo nodo,
  excepto la raiz, la cual no tiene ningun "padre". Por ejemplo:

 _________1_______     <---- Raiz
|         |       |
\/       \/       \/
A      __2__     __3__       A cada nodo solo lo "toca" un unico nodo:
      |     |   |     |      1 --> A     1 --> 2     1 --> 3
      \/   \/   \/    \/     2 --> 4     2 --> 5     3 --> 6
      4     5   6      7     3 --> 7     4 --> 8     6 --> 9
      |         |
      \/        \/           Lo cual no equivale a que solo ese este conectado con el nodo
      8         9

\dontinclude test_Graph.cpp
\skipline    test::isTree()
\until       }}
\see         test_Graph::isTree()
\author Joseiby Hernadez Cedeño <joherce@yahoo.com>

Definition at line 203 of file ADH_Graph_Lib.cpp.

bool ADH::spanningTree ( const Graph &  G,
Graph &  T 
)

Construye un árbol de expansión (spanning tree) "T" para el grafo "G". 

- Lo retorna en \c "T".
- Si se pudo construir el árbol correctamente devuelve \c "true"
- Si no lo pudo construir retorna \c "false" y no cambia el valor de \c "T".
- Si el arbol de expansión se logra, este tendrá conexión con todos los nodos.

          ---<----                   Arbol de expansión
         /        \
     A(1)         C(1)                 A(1)         C(1)
    /    \       /    \               /            /    \
   /      \     /      \             /            /      \
F->--A(2)-->-B->        ->D->-+   F->--A(2)-->-B->        ->D
   \      /     \      /      |      \            \
    \    /       \    /       |       \            \
     A(3)<--------C(2)<-------+        A(3)         C(2)

Nota: Generalmente el árbol de expansión de un grafo se puede sacar por medio de
ciertos algoritmos ya inventados como el algoritmo de Kruskal y el de Prim. Pero como
se está trabajando con grafos dirigidos el algoritmo se vuelve complejo.

En este caso lo que se hace es "imaginar" que el árbol no es dirigido y sacar un árbol
de expansión a partir de los nodos y conexiones que se tienen. El arbol de expansión
en este caso sería un arbol que contiene TODOS los nodos del grafo.

\dontinclude test_Graph.cpp
\skipline    test::spanningTree()
\until       }}
\see         test_Graph::spanningTree()
\author Joseiby Hernadez Cedeño <joherce@yahoo.com>

Definition at line 289 of file ADH_Graph_Lib.cpp.

bool ADH::connected_set ( const Graph &  G,
std::set< std::string > &  S,
const std::string &  src,
const std::string &  dst,
std::list< std::string > &  C 
)

Determina si existe un camino desde "src" hasta "dst" sin pasar por los nodos de "S".

  • Este es el paso recursivo desde el método públic connected().
  • Le agrega valores a la lista "C", pero no la borra si no encuentra el camino.
  • No agrega "src" al principio de "C" (tampoco lo agrega en otro lado).
  • El conjunto "S" contiene vértices que ya fueron visitados.
  • Se usa "S" para evitar que el programa se encicle cuando el grafo tiene ciclos.

Definition at line 60 of file ADH_Graph_Lib.cpp.

Generated on Fri May 25 2012 08:28:13 for [B]asic module for [unit] program testing: by   doxygen 1.8.0