test_Graph.cpp

Go to the documentation of this file.

// test_Graph.cpp (c) adolfo@di-mare.com

/** \file  test_Graph.cpp
    \brief Datos de prueba para la clase \c ADH_Graph.

    \author Adolfo Di Mare <adolfo@di-mare.com>
    \date   2007
*/

#include "BUnit.h"
#include "ADH_Graph.h"
#include "ADH_Graph_Lib.h"
#include <algorithm>

namespace ADH {

/// Clase simple para probar la clase \c ADH_Graph.
class test_Graph : public TestCase {
    bool m_cycle; ///< Indica si \c run() invoca \c test_connected_cycle();.
    Graph G;  ///< Valor usado en las pruebas.
public:
    test_Graph() : G(), m_cycle(false) {} ///< Constructor por defecto.
    void test_connected();
    void test_connected_cycle();
    void test_isVertex();
    void test_vertexList();
    void setUp();
    void do_cout( std::ostream & COUT );
    void do_dump( std::ostream & COUT );
    void test_Rep_const_iterator();
    void test_isConnected();
    void test_isCircuit();
    void test_spanningTree();
    bool run();
    void set_cycles( bool v ) {
        m_cycle = v;
    } ///< Define si \c run() invoca \c test_connected_cycle();.
}; // test_Graph

/// Ejecuta las pruebas para \c test_Graph.
bool test_Graph::run() {
    test_connected();
    if ( m_cycle ) { test_connected_cycle(); }
    test_isVertex();
    test_vertexList();
    test_Rep_const_iterator();
    test_isConnected();
    test_isCircuit();
    test_spanningTree();
    return wasSuccessful();
}

/*
    {{ // test::diagram()
         A(1)         C(1)        O(1)---->O(2)
        /    \       /    \       /|\       |
       /      \     /      \       |        |
    F->--A(2)-->-B->        ->D    |        |
       \      /     \      /       |        |
        \    /       \    /        |       \|/
         A(3)         C(2)        O(4)<----O(3)
    }}
*/
void test_Graph::setUp() {
    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 );

    G.set("B", "C(1)",  3 ); G.set( "C(1)", "D",  3 );
    G.set("B", "C(2)", 27 ); G.set( "C(2)", "D", 27 );

    G.set("O(1)", "O(2)", 2*2*2 );
    G.set("O(2)", "O(3)", 3*3*3 );
    G.set("O(3)", "O(4)", 5*5*5 );
    G.set("O(4)", "O(1)", 7*7*7 );
}

/// Graba en \c COUT el valor de \c G (Fixture).
void test_Graph::do_cout( std::ostream & COUT ) {
    COUT << G;
}

/// Graba en \c COUT el valor de \c G (Fixture).
void test_Graph::do_dump( std::ostream & COUT ) {
    Graph G;
    G.set("O(1)", "O(2)", 2*2*2 );
    G.set("O(2)", "O(3)", 3*3*3 );
    G.set("O(3)", "O(4)", 5*5*5 );
    G.set("O(4)", "O(1)", 7*7*7 );
    ADH::dump( COUT , G );
}

/// Prueba \c Graph::Rep_const_iterator().
void test_Graph::test_Rep_const_iterator() {
    {{ // test::Rep_const_iterator()
        Graph Tree;
        Tree.set("root", "child(1)", 1 );
        Tree.set("root", "child(2)", 2*2 );
        Tree.set("root", "child(3)", 3*3*3);
        Graph::Rep_const_iterator it, jt; int val = int();
        for ( it = Tree.begin_Rep() ; it != Tree.end_Rep() ; ++it ) {
            for ( jt = Tree.begin_Rep() ; jt != Tree.end_Rep() ; ++jt ) {
                if ( Tree.isArc( it->first , jt->first , val ) ) {
                    assertTrue( it->first == "root" );
                    assertTrue( jt->first.substr(0,5) == "child" );
                }
            }
        }
    }}
}

/// Prueba \c Graph::connected().
void test_Graph::test_connected() {
    {{ // 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
    }}
    {  // resto de las pruebas
        std::list< std::string > C;
        std::list< std::string >::iterator it;
        assertTrue( connected( G , "A(2)", "B" , C ) );
        assertTrue( C.size() == 2 );
        assertTrue( C.front() == "A(2)" && C.back() == "B" );

        assertTrue( connected( G , "A(2)", "C(2)" , C ) );
        assertTrue( C.size() == 3 );
        assertTrue( C.front() == "A(2)" && C.back() == "C(2)" );
    }
    {
        std::list< std::string > C;
        std::list< std::string >::iterator it;
        assertTrue( ! connected( G , "D", "F" , C ) ); assertTrue( C.size() == 0 );
        assertTrue(   connected( G , "F", "D" , C ) ); assertTrue( C.size() == 5 );
        assertTrue( C.front() == "F" && C.back() == "D" );
        it = C.begin();
        assertTrue( *it == "F" ); // 1ero nodo en el camino
        it++;
        assertTrue( *it == "A(1)" || *it == "A(2)" || *it == "A(3)" ); // 2do nodo
        it++;
        assertTrue( *it == "B" ); // 3er nodo
        it++;
        assertTrue( *it == "C(1)" || *it == "C(2)" ); // 4to nodo
        it++;
        assertTrue( *it == "D" ); // 5to nodo
    }
    {
        ADH::Graph G;
        G.set( "1", "2", 2 ); {          //         1         //
            G.set( "2", "4", 4 );  {     //        / \        //
                G.set( "4", "8", 8 );    //       /   \       //
                G.set( "4", "9", 9 );    //     2       3     //
            }                            //    / \     / \    //
            G.set( "2", "5", 5 );  {     //    4 5     6 7    //
                G.set( "5", "10", 10 );  //   /\ /\   /\ /\   //
                G.set( "5", "11", 11 );  //   89 AB   CD EF   //
            }
        }
        G.set( "1", "3", 3 );  {
            G.set( "3", "6", 6 );  {
                G.set( "6", "12", 12 );
                G.set( "6", "13", 13 );
            }
            G.set( "3", "7", 7 );  {
                G.set( "7", "14", 14 );
                G.set( "7", "15", 15 );
            }
        }
        using namespace std;
        list< string > C; int val, i, j, k, n;
        for ( i=2; i<16; ++i ) {
            string i_str = TestCase::toString(i);
            for ( j=2; j<16; ++j ) {
                val = 666; C.clear(); C.push_back( "???" );
                string j_str = TestCase::toString(j), k_str;
                if ( i==j ) {
                    assertTrue( ! G.isArc    ( i_str , j_str, val ) );
                    assertTrue( val == 666 && "unchanged val" );
                    assertTrue_Msg( "connected( G ,"+i_str+" , "+j_str+')',  connected( G ,  i_str , j_str , C  ) );
                    assertTrue( C.size() >= 1 && C.front() == i_str );
                    assertTrue( ! connected( G , i_str , "1",   C   ) );
                    assertTrue( C.empty() );
                    assertTrue_Msg( "connected( G , 1 , "+i_str+')',  connected( G ,  "1" , i_str , C  ) );
                    assertTrue( C.size() >= 1 && C.back() == i_str );
                }
                else if ( i < j ) {
                    for ( (n=1, k=j); k>0 ; (k/=2,++n) ) {
                        k_str = TestCase::toString(k);
                        assertTrue_Msg( "connected( G ,"+k_str+" , "+j_str+')' ,
                                         connected( G ,  k_str , j_str , C  ) );
                        assertTrue_Msg(  "C.front() == "+k_str+ " && C.back() == "+j_str ,
                                        ( C.front() == k_str && C.back() == j_str ) );
                        assertTrue( C.size()  == n );
                        if ( k != j ) {
                            assertTrue_Msg( "! connected( G ,"+j_str+" , "+k_str+')' ,
                                             ! connected( G ,  j_str , k_str , C  ) );
                            assertTrue( C.empty() );
                        }
                    }
                }
            }
        }
    }
}

/** Prueba \c Graph::connected() con un grafo que tiene ciclos.
\code
          ---<----
         /        \
     A(1)         C(1)<-------+
    /    \       /    \       |
   /      \     /      \      |
F->--A(2)-->-B->        ->D->-+
   \      /     \      /
    \    /       \    /
     A(3)         C(2)
\endcode
*/
void test_Graph::test_connected_cycle() {
    Graph G = test_Graph::G; // evita cambiar el grafo de la clase
    // Crea el ciclo A(1)->B->C(1)->A(1)
    G.set( "C(1)" , "A(1)", 800 );
    // Crea el ciclo D->C(1)->D
    G.set(  "D"   , "C(1)", 1492 );
    std::list< std::string > C;
    assertTrue( ! connected( G , "D", "F" , C )    ); assertTrue( C.size() == 0 );

    assertTrue(   connected( G , "A(1)", "D" , C ) ); assertTrue( C.size() >= 4 );
    assertTrue(   connected( G , "D", "A(1)" , C ) ); assertTrue( C.size() >= 3 );

    assertTrue(   connected( G , "A(1)", "B" , C ) ); assertTrue( C.size() >= 2 );
    assertTrue(   connected( G , "B", "A(1)" , C ) ); assertTrue( C.size() >= 3 );

    assertTrue(   connected( G , "A(1)", "C(2)" , C ) ); assertTrue( C.size() >= 3 );
    assertTrue(   connected( G , "C(2)", "A(1)" , C ) ); assertTrue( C.size() >= 4 );
}

/// Prueba \c Graph::isVertex()
void test_Graph::test_isVertex() {
    {{ // 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" );
    }}
    {   Graph::Rep::const_iterator it = G.m_DICC.begin();
        for ( ; it != G.m_DICC.end(); ++it ) {
            assertTrue(   G.isVertex( it->first ) ) ;
            assertTrue( ! G.isVertex( it->first + "chungis") ) ;
        }
    }
    {   int val;
        Graph::Rep::const_iterator it = G.m_DICC.begin();  // recorre m_DICC[]
        for ( ; it != G.m_DICC.begin(); ++it ) {
            Graph::mapped_type::const_iterator jt = it->second.begin();
            for ( ; jt != it->second.end(); ++jt ) {
                assertTrue( G.isArc( it->first , jt->first , val ) );
                assertTrue( val == jt->second );
                assertTrue( ! G.isArc( 'c'+it->first ,     jt->first , val ) );
                assertTrue( ! G.isArc( 'c'+it->first , 'c'+jt->first , val ) );
                assertTrue( ! G.isArc(     it->first , 'c'+jt->first , val ) );
            }
        }
        assertTrue( ! G.isArc( "A(1)" , "O(1)" ,  val ) );
        assertTrue( ! G.isArc( "O(1)" , "A(1)" ,  val ) );
        assertTrue( ! G.isArc( "O(4)" , "O(3)" ,  val ) );
        assertTrue( ! G.isArc( "0(1)" ,  "B"   ,  val ) );
        assertTrue( ! G.isArc( "A(3)" ,  "F"   ,  val ) );
    }
}

/// Prueba \c Graph::test_vertexList()
void test_Graph::test_vertexList() {
    {{ // 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" );
    }}
}

/// Prueba \c Graph::test_isConnected()
void test_Graph::test_isConnected() {
    {{ // 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
    }}
}

/// Prueba \c Graph::test_isCircuit() que tiene ciclos.
void test_Graph::test_isCircuit() {
    {{ // test::isCircuit()
    }}

    /*        ---<----
             /        \
         A(1)         C(1)
        /    \       /    \
       /      \     /      \
    F->--A(2)-->-B->        ->D->-+
       \      /     \      /      |
        \    /       \    /       |
         A(3)<--------C(2)<-------+
    */
    Graph CH; // utilizando el grafo de la clase
    std::list<std::string> camino; // Lista para formar caminos a probar
    CH.set("F", "A(1)",  2 ); CH.set( "A(1)", "B",  2 );
    CH.set("F", "A(2)",  8 ); CH.set( "A(2)", "B",  8 );
    CH.set("F", "A(3)", 64 ); CH.set( "A(3)", "B", 64 );

    CH.set("B", "C(1)",  3 ); CH.set( "C(1)", "D",  3 );
    CH.set("B", "C(2)", 27 ); CH.set( "C(2)", "D", 27 );

    // Crea los ciclos
    CH.set( "C(1)" , "A(1)", 80 );
    CH.set(  "D"   , "C(2)", 14 );
    CH.set( "C(2)" , "A(3)", 59 );
    camino.push_back("A(3)");   camino.push_back("B");    camino.push_back("C(1)");
    camino.push_back("D");      camino.push_back("C(2)"); camino.push_back("A(3)");
    /* Esto forma el camino:
                 A(3) -> B -> C(1) -> D -> C(2)->+
                /|\                              |
                 +-------------------------------+
     */
    assertTrue( isCircuit(CH,camino) );
    // Si le hago "pop_back()" a "camino" no sería ciclo, pues
    // el primer y el último no son el mismo
    camino.pop_back();
    assertTrue( !isCircuit(CH,camino) );

    assertTrue( connected( CH,"A(2)", "A(1)", camino ) );
    /* Esto forma el camino:
                 A(2) -> B -> C(1) -> A(1)    Este no es un ciclo
     */
    assertTrue( !isCircuit(CH,camino ) );
    // No existe el ciclo aunque agregue el nodo de inicio otra vez
    camino.push_back("A(2)");
    assertTrue( !isCircuit(CH,camino) );

    assertTrue( !connected( CH,"A(1)", "F", camino ));

    // No existen ciclos en caminos a partir de "F"
    std::list<std::string> listTmp;
    CH.vertexList(listTmp);

    for ( std::list<std::string>::iterator iTmp = ++listTmp.begin();
          iTmp != listTmp.end(); ++iTmp
    ) {
         connected( CH,"F", *iTmp, camino );
         camino.push_back("F");
         assertTrue (!isCircuit(CH,camino));
    }

    // Una característica del grafo "G", es que no es conexo
    assertTrue( !isConnected(CH));
    // Además no es un árbol
    assertTrue( !isTree(CH));
    // Y tiene un arbol de expansión (spanning tree)
    Graph newG;
    assertTrue( spanningTree(CH,newG));
    assertTrue( isTree(newG));
    std::list<std::string> lT;
    newG.vertexList(lT);
    std::list<std::string> N_Nodos;
    int cant = 0;
    for(std::list<std::string>::iterator iT = lT.begin(); iT != lT.end(); ++iT){
        newG.vertexList(*iT, N_Nodos);
        cant += N_Nodos.size();
    }
    assertTrue(  cant+1 == lT.size() ); // Mido cantidad de aristas con cantidad de Nodos
}

/// Prueba \c Graph::test_spanningTree().
void test_Graph::test_spanningTree() {
    {{ // 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) );
    }}
}

} // namespace ADH

/// Programa principal para probar la clase \c ADH_Graph.
int main() {
    using namespace ADH;
    using namespace std;
    test_Graph tester;
    tester.setUp();
    if (1) {
        tester.do_dump(cout); cout << endl;
        tester.do_cout(cout); cout << endl;
    }
    tester.run();
    cout << tester.summary() << endl;
    cout << tester.report() << endl;
    tester.set_cycles(true); // aparte por si se encicla
    tester.run();
    cout << endl << endl;
    cout << tester.report() << endl;
    return 0;
}
// EOF: test_Graph.cpp