Modulo [B]asico para prueba [unit]aria de programas:
Clases | Funciones
Referencia del Namespace ADH

ADH: Adolfo Di Mare H. Más...

Clases

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

Funciones

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

Descripción detallada

ADH: Adolfo Di Mare H.

Documentación de las funciones

bool ADH::check_ok ( const Graph &  DDD)

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.

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

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

Definición en la línea 18 del archivo ADH_Graph_Lib.cpp.

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

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

Definición en la línea 36 del archivo 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
    }}

Ver también:
test_Graph::test_connected()

Definición en la línea 105 del archivo 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
    }}

Ver también:
test_Graph::isConnected()
Autor:
Joseiby Hernadez Cedeño <joherce@yahoo.com>

Definición en la línea 133 del archivo 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()
    }}

Ver también:
test_Graph::isCircuit()
Autor:
Joseiby Hernadez Cedeño <joherce@yahoo.com>

Definición en la línea 161 del archivo 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

 


Ver también:
test_Graph::isTree() 


Autor:
Joseiby Hernadez Cedeño <joherce@yahoo.com> 



Definición en la línea 203 del archivo 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 "T".
    • 

  • Si se pudo construir el árbol correctamente devuelve "true" 
    • 

  • Si no lo pudo construir retorna "false" y no cambia el valor de "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.

 
    {{ // test::spanningTree()
        Graph G;                                          //      B----->D
        G.set( "A", "B",  10 );   G.set( "A", "C",  12 ); //     /|    / |
        G.set( "C", "B",  14 );   G.set( "C", "D",  21 ); //    / |   /  |
        G.set( "C", "E",  16 );   G.set( "D", "B",  20 ); // A-> /|\ /   |
        G.set( "D", "E",  18 );                           //    \ | /    |
                                                          //     \|/    \|/
        // Tiene un arbol de expansión (spanning tree)    //      C----->E
        Graph T;
        assertTrue( spanningTree(G,T));
        assertTrue( isTree(T));
        std::list<std::string> T_Vertices;
        T.vertexList(T_Vertices);
        std::list<std::string> N_Nodos;
        int cant = 0;
        for( std::list<std::string>::iterator iT = T_Vertices.begin(); iT != T_Vertices.end(); ++iT ) {
            T.vertexList(*iT, N_Nodos);
            cant += N_Nodos.size();
        }
        assertTrue(  cant +1 == T_Vertices.size()); // Mido cantidad de aristas con cantidad de Nodos

        // El árbol de expansión no es un conexo
        assertTrue( !isConnected(T) );

        // En este caso es un árbol
        assertTrue( isTree(T) );
    }}

 


Ver también:
test_Graph::spanningTree() 


Autor:
Joseiby Hernadez Cedeño <joherce@yahoo.com> 



Definición en la línea 289 del archivo 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. 
    • 




Definición en la línea 60 del archivo ADH_Graph_Lib.cpp.











 Todo Clases Namespaces Archivos Funciones Variables 'typedefs' Valores de enumeraciones Amigas 'defines'













Generado el Viernes, 21 de Octubre de 2011 10:28:59 para Modulo [B]asico para prueba [unit]aria de programas: por  
doxygen
 1.7.5.1