[B]asic module for [unit] program testing:
 All Classes Namespaces Files Functions Variables Typedefs Enumerator Friends Defines
test_Graph.cpp
Go to the documentation of this file.
00001 // test_Graph.cpp (c) adolfo@di-mare.com
00002 
00003 /** \file  test_Graph.cpp
00004     \brief Datos de prueba para la clase \c ADH_Graph.
00005 
00006     \author Adolfo Di Mare <adolfo@di-mare.com>
00007     \date   2007
00008 */
00009 
00010 #include "BUnit.h"
00011 #include "ADH_Graph.h"
00012 #include "ADH_Graph_Lib.h"
00013 #include <algorithm>
00014 
00015 namespace ADH {
00016 
00017 /// Clase simple para probar la clase \c ADH_Graph.
00018 class test_Graph : public TestCase {
00019     bool m_cycle; ///< Indica si \c run() invoca \c test_connected_cycle();.
00020     Graph G;  ///< Valor usado en las pruebas.
00021 public:
00022     test_Graph() : G(), m_cycle(false) {} ///< Constructor por defecto.
00023     void test_connected();
00024     void test_connected_cycle();
00025     void test_isVertex();
00026     void test_vertexList();
00027     void setUp();
00028     void do_cout( std::ostream & COUT );
00029     void do_dump( std::ostream & COUT );
00030     void test_Rep_const_iterator();
00031     void test_isConnected();
00032     void test_isCircuit();
00033     void test_spanningTree();
00034     bool run();
00035     void set_cycles( bool v ) {
00036         m_cycle = v;
00037     } ///< Define si \c run() invoca \c test_connected_cycle();.
00038 }; // test_Graph
00039 
00040 /// Ejecuta las pruebas para \c test_Graph.
00041 bool test_Graph::run() {
00042     test_connected();
00043     if ( m_cycle ) { test_connected_cycle(); }
00044     test_isVertex();
00045     test_vertexList();
00046     test_Rep_const_iterator();
00047     test_isConnected();
00048     test_isCircuit();
00049     test_spanningTree();
00050     return wasSuccessful();
00051 }
00052 
00053 /*
00054     {{ // test::diagram()
00055          A(1)         C(1)        O(1)---->O(2)
00056         /    \       /    \       /|\       |
00057        /      \     /      \       |        |
00058     F->--A(2)-->-B->        ->D    |        |
00059        \      /     \      /       |        |
00060         \    /       \    /        |       \|/
00061          A(3)         C(2)        O(4)<----O(3)
00062     }}
00063 */
00064 void test_Graph::setUp() {
00065     G.set("F", "A(1)",  2 ); G.set( "A(1)", "B",  2 );
00066     G.set("F", "A(2)",  8 ); G.set( "A(2)", "B",  8 );
00067     G.set("F", "A(3)", 64 ); G.set( "A(3)", "B", 64 );
00068 
00069     G.set("B", "C(1)",  3 ); G.set( "C(1)", "D",  3 );
00070     G.set("B", "C(2)", 27 ); G.set( "C(2)", "D", 27 );
00071 
00072     G.set("O(1)", "O(2)", 2*2*2 );
00073     G.set("O(2)", "O(3)", 3*3*3 );
00074     G.set("O(3)", "O(4)", 5*5*5 );
00075     G.set("O(4)", "O(1)", 7*7*7 );
00076 }
00077 
00078 /// Graba en \c COUT el valor de \c G (Fixture).
00079 void test_Graph::do_cout( std::ostream & COUT ) {
00080     COUT << G;
00081 }
00082 
00083 /// Graba en \c COUT el valor de \c G (Fixture).
00084 void test_Graph::do_dump( std::ostream & COUT ) {
00085     Graph G;
00086     G.set("O(1)", "O(2)", 2*2*2 );
00087     G.set("O(2)", "O(3)", 3*3*3 );
00088     G.set("O(3)", "O(4)", 5*5*5 );
00089     G.set("O(4)", "O(1)", 7*7*7 );
00090     ADH::dump( COUT , G );
00091 }
00092 
00093 /// Prueba \c Graph::Rep_const_iterator().
00094 void test_Graph::test_Rep_const_iterator() {
00095     {{ // test::Rep_const_iterator()
00096         Graph Tree;
00097         Tree.set("root", "child(1)", 1 );
00098         Tree.set("root", "child(2)", 2*2 );
00099         Tree.set("root", "child(3)", 3*3*3);
00100         Graph::Rep_const_iterator it, jt; int val = int();
00101         for ( it = Tree.begin_Rep() ; it != Tree.end_Rep() ; ++it ) {
00102             for ( jt = Tree.begin_Rep() ; jt != Tree.end_Rep() ; ++jt ) {
00103                 if ( Tree.isArc( it->first , jt->first , val ) ) {
00104                     assertTrue( it->first == "root" );
00105                     assertTrue( jt->first.substr(0,5) == "child" );
00106                 }
00107             }
00108         }
00109     }}
00110 }
00111 
00112 /// Prueba \c Graph::connected().
00113 void test_Graph::test_connected() {
00114     {{ // test::connected()
00115         std::list< std::string > C; // camino en el grafo
00116         std::list< std::string >::iterator it;
00117 
00118         assertTrue( ! connected( G , "???" , "???",  C ) ); // no existe el vértice
00119         assertTrue( ! connected( G ,  "F" ,  "O(4)", C ) ); // grafo no conexo
00120         assertTrue( C.size() == 0 );
00121         assertTrue( ! connected( G , "D" , "F"   , C ) ); // el grafo es dirigido
00122         assertTrue( C.size() == 0 );
00123 
00124         assertTrue( connected( G , "F" , "F", C ) );       // si está conectado
00125         assertTrue( C.size() == 1 && C.front() == "F" ); // porque ya está ahí
00126 
00127         assertTrue( ! connected( G , "D", "A(2)" , C ) ); assertTrue( C.size() == 0 );
00128         assertTrue( connected( G , "A(2)" , "D", C ) );   assertTrue( C.size() == 4 );
00129         assertTrue( C.front() == "A(2)" && C.back() == "D" );
00130         it = C.begin(); it++;
00131         assertTrue( *it == "B" ); // 2do nodo en el camino
00132         it++;
00133         assertTrue( *it == "C(1)" || *it == "C(2)" ); // 3er nodo en el camino
00134     }}
00135     {  // resto de las pruebas
00136         std::list< std::string > C;
00137         std::list< std::string >::iterator it;
00138         assertTrue( connected( G , "A(2)", "B" , C ) );
00139         assertTrue( C.size() == 2 );
00140         assertTrue( C.front() == "A(2)" && C.back() == "B" );
00141 
00142         assertTrue( connected( G , "A(2)", "C(2)" , C ) );
00143         assertTrue( C.size() == 3 );
00144         assertTrue( C.front() == "A(2)" && C.back() == "C(2)" );
00145     }
00146     {
00147         std::list< std::string > C;
00148         std::list< std::string >::iterator it;
00149         assertTrue( ! connected( G , "D", "F" , C ) ); assertTrue( C.size() == 0 );
00150         assertTrue(   connected( G , "F", "D" , C ) ); assertTrue( C.size() == 5 );
00151         assertTrue( C.front() == "F" && C.back() == "D" );
00152         it = C.begin();
00153         assertTrue( *it == "F" ); // 1ero nodo en el camino
00154         it++;
00155         assertTrue( *it == "A(1)" || *it == "A(2)" || *it == "A(3)" ); // 2do nodo
00156         it++;
00157         assertTrue( *it == "B" ); // 3er nodo
00158         it++;
00159         assertTrue( *it == "C(1)" || *it == "C(2)" ); // 4to nodo
00160         it++;
00161         assertTrue( *it == "D" ); // 5to nodo
00162     }
00163     {
00164         ADH::Graph G;
00165         G.set( "1", "2", 2 ); {          //         1         //
00166             G.set( "2", "4", 4 );  {     //        / \        //
00167                 G.set( "4", "8", 8 );    //       /   \       //
00168                 G.set( "4", "9", 9 );    //     2       3     //
00169             }                            //    / \     / \    //
00170             G.set( "2", "5", 5 );  {     //    4 5     6 7    //
00171                 G.set( "5", "10", 10 );  //   /\ /\   /\ /\   //
00172                 G.set( "5", "11", 11 );  //   89 AB   CD EF   //
00173             }
00174         }
00175         G.set( "1", "3", 3 );  {
00176             G.set( "3", "6", 6 );  {
00177                 G.set( "6", "12", 12 );
00178                 G.set( "6", "13", 13 );
00179             }
00180             G.set( "3", "7", 7 );  {
00181                 G.set( "7", "14", 14 );
00182                 G.set( "7", "15", 15 );
00183             }
00184         }
00185         using namespace std;
00186         list< string > C; int val, i, j, k, n;
00187         for ( i=2; i<16; ++i ) {
00188             string i_str = TestCase::toString(i);
00189             for ( j=2; j<16; ++j ) {
00190                 val = 666; C.clear(); C.push_back( "???" );
00191                 string j_str = TestCase::toString(j), k_str;
00192                 if ( i==j ) {
00193                     assertTrue( ! G.isArc    ( i_str , j_str, val ) );
00194                     assertTrue( val == 666 && "unchanged val" );
00195                     assertTrue_Msg( "connected( G ,"+i_str+" , "+j_str+')',  connected( G ,  i_str , j_str , C  ) );
00196                     assertTrue( C.size() >= 1 && C.front() == i_str );
00197                     assertTrue( ! connected( G , i_str , "1",   C   ) );
00198                     assertTrue( C.empty() );
00199                     assertTrue_Msg( "connected( G , 1 , "+i_str+')',  connected( G ,  "1" , i_str , C  ) );
00200                     assertTrue( C.size() >= 1 && C.back() == i_str );
00201                 }
00202                 else if ( i < j ) {
00203                     for ( (n=1, k=j); k>0 ; (k/=2,++n) ) {
00204                         k_str = TestCase::toString(k);
00205                         assertTrue_Msg( "connected( G ,"+k_str+" , "+j_str+')' ,
00206                                          connected( G ,  k_str , j_str , C  ) );
00207                         assertTrue_Msg(  "C.front() == "+k_str+ " && C.back() == "+j_str ,
00208                                         ( C.front() == k_str && C.back() == j_str ) );
00209                         assertTrue( C.size()  == n );
00210                         if ( k != j ) {
00211                             assertTrue_Msg( "! connected( G ,"+j_str+" , "+k_str+')' ,
00212                                              ! connected( G ,  j_str , k_str , C  ) );
00213                             assertTrue( C.empty() );
00214                         }
00215                     }
00216                 }
00217             }
00218         }
00219     }
00220 }
00221 
00222 /** Prueba \c Graph::connected() con un grafo que tiene ciclos.
00223 \code
00224           ---<----
00225          /        \
00226      A(1)         C(1)<-------+
00227     /    \       /    \       |
00228    /      \     /      \      |
00229 F->--A(2)-->-B->        ->D->-+
00230    \      /     \      /
00231     \    /       \    /
00232      A(3)         C(2)
00233 \endcode
00234 */
00235 void test_Graph::test_connected_cycle() {
00236     Graph G = test_Graph::G; // evita cambiar el grafo de la clase
00237     // Crea el ciclo A(1)->B->C(1)->A(1)
00238     G.set( "C(1)" , "A(1)", 800 );
00239     // Crea el ciclo D->C(1)->D
00240     G.set(  "D"   , "C(1)", 1492 );
00241     std::list< std::string > C;
00242     assertTrue( ! connected( G , "D", "F" , C )    ); assertTrue( C.size() == 0 );
00243 
00244     assertTrue(   connected( G , "A(1)", "D" , C ) ); assertTrue( C.size() >= 4 );
00245     assertTrue(   connected( G , "D", "A(1)" , C ) ); assertTrue( C.size() >= 3 );
00246 
00247     assertTrue(   connected( G , "A(1)", "B" , C ) ); assertTrue( C.size() >= 2 );
00248     assertTrue(   connected( G , "B", "A(1)" , C ) ); assertTrue( C.size() >= 3 );
00249 
00250     assertTrue(   connected( G , "A(1)", "C(2)" , C ) ); assertTrue( C.size() >= 3 );
00251     assertTrue(   connected( G , "C(2)", "A(1)" , C ) ); assertTrue( C.size() >= 4 );
00252 }
00253 
00254 /// Prueba \c Graph::isVertex()
00255 void test_Graph::test_isVertex() {
00256     {{ // test::isVertex()
00257         Graph G; int val = 666;
00258         G.set( "F", "D", 2*2*2 );
00259         assertTrue( G.isVertex( "F" ) ) ;
00260         assertTrue( G.isVertex( "D" ) ) ;
00261         assertTrue( val == 666 && "initial val" );
00262         assertTrue( G.isArc( "F" , "D", val ) );
00263         assertTrue( val == 2*2*2 && "returned val" );
00264         val = 666;
00265         assertTrue( ! G.isArc( "D" , "F", val ) );
00266         assertTrue( val == 666 && "unchanged val" );
00267     }}
00268     {   Graph::Rep::const_iterator it = G.m_DICC.begin();
00269         for ( ; it != G.m_DICC.end(); ++it ) {
00270             assertTrue(   G.isVertex( it->first ) ) ;
00271             assertTrue( ! G.isVertex( it->first + "chungis") ) ;
00272         }
00273     }
00274     {   int val;
00275         Graph::Rep::const_iterator it = G.m_DICC.begin();  // recorre m_DICC[]
00276         for ( ; it != G.m_DICC.begin(); ++it ) {
00277             Graph::mapped_type::const_iterator jt = it->second.begin();
00278             for ( ; jt != it->second.end(); ++jt ) {
00279                 assertTrue( G.isArc( it->first , jt->first , val ) );
00280                 assertTrue( val == jt->second );
00281                 assertTrue( ! G.isArc( 'c'+it->first ,     jt->first , val ) );
00282                 assertTrue( ! G.isArc( 'c'+it->first , 'c'+jt->first , val ) );
00283                 assertTrue( ! G.isArc(     it->first , 'c'+jt->first , val ) );
00284             }
00285         }
00286         assertTrue( ! G.isArc( "A(1)" , "O(1)" ,  val ) );
00287         assertTrue( ! G.isArc( "O(1)" , "A(1)" ,  val ) );
00288         assertTrue( ! G.isArc( "O(4)" , "O(3)" ,  val ) );
00289         assertTrue( ! G.isArc( "0(1)" ,  "B"   ,  val ) );
00290         assertTrue( ! G.isArc( "A(3)" ,  "F"   ,  val ) );
00291     }
00292 }
00293 
00294 /// Prueba \c Graph::test_vertexList()
00295 void test_Graph::test_vertexList() {
00296     {{ // test::vertexList()
00297         std::list< std::string > L;
00298         G.vertexList( L );
00299         assertTrue( L.size() == 12 );
00300 
00301         G.vertexList( "F", L );
00302         assertTrue( L.size() == 3 );
00303         assertTrue( find(L.begin(), L.end() ,"A(1)") != L.end() );
00304         assertTrue( find(L.begin(), L.end() ,"A(2)") != L.end() );
00305         assertTrue( find(L.begin(), L.end() ,"A(3)") != L.end() );
00306 
00307         G.vertexList( "D", L );
00308         assertTrue( L.empty() );
00309 
00310         G.vertexList( "A(2)", L );
00311         assertTrue( L.size() == 1 );
00312         assertTrue( L.front() == "B" );
00313     }}
00314 }
00315 
00316 /// Prueba \c Graph::test_isConnected()
00317 void test_Graph::test_isConnected() {
00318     {{ // test::isConnected()
00319         Graph G;
00320         std::list<std::string> C;
00321         std::list<std::string> tmp;
00322         G.set("M(1)", "M(2)", 13 );  //  M(1)<------->M(2)<--
00323         G.set("M(2)", "M(3)", 15 );  //   /\           |    |
00324         G.set("M(3)", "M(4)", 17 );  //   |            |    |
00325         G.set("M(4)", "M(2)", 19 );  //   |            \/   |
00326         G.set("M(2)", "M(1)", 23 );  //  M(4)<------- M(3)  |
00327         G.set("M(4)", "M(1)", 29 );  //   |                 |
00328                                      //   +------->---------+
00329         assertTrue( isConnected(G) );
00330         G.vertexList( C );
00331 
00332         // Con este doble ciclo se prueba que "isConnected()"  funciona ya que dan los mismos resultados
00333         for ( std::list< std::string >::iterator it = C.begin(); it != C.end(); ++it ) {
00334             for ( std::list< std::string >::iterator jt = C.begin(); jt != C.end(); ++jt ) {
00335                 assertTrue ( connected( G , *it , *jt , tmp ) );
00336             }
00337         }
00338         assertTrue( !isTree( G ) ); // No cuenta con las características de un árbol
00339     }}
00340 }
00341 
00342 /// Prueba \c Graph::test_isCircuit() que tiene ciclos.
00343 void test_Graph::test_isCircuit() {
00344     {{ // test::isCircuit()
00345     }}
00346 
00347     /*        ---<----
00348              /        \
00349          A(1)         C(1)
00350         /    \       /    \
00351        /      \     /      \
00352     F->--A(2)-->-B->        ->D->-+
00353        \      /     \      /      |
00354         \    /       \    /       |
00355          A(3)<--------C(2)<-------+
00356     */
00357     Graph CH; // utilizando el grafo de la clase
00358     std::list<std::string> camino; // Lista para formar caminos a probar
00359     CH.set("F", "A(1)",  2 ); CH.set( "A(1)", "B",  2 );
00360     CH.set("F", "A(2)",  8 ); CH.set( "A(2)", "B",  8 );
00361     CH.set("F", "A(3)", 64 ); CH.set( "A(3)", "B", 64 );
00362 
00363     CH.set("B", "C(1)",  3 ); CH.set( "C(1)", "D",  3 );
00364     CH.set("B", "C(2)", 27 ); CH.set( "C(2)", "D", 27 );
00365 
00366     // Crea los ciclos
00367     CH.set( "C(1)" , "A(1)", 80 );
00368     CH.set(  "D"   , "C(2)", 14 );
00369     CH.set( "C(2)" , "A(3)", 59 );
00370     camino.push_back("A(3)");   camino.push_back("B");    camino.push_back("C(1)");
00371     camino.push_back("D");      camino.push_back("C(2)"); camino.push_back("A(3)");
00372     /* Esto forma el camino:
00373                  A(3) -> B -> C(1) -> D -> C(2)->+
00374                 /|\                              |
00375                  +-------------------------------+
00376      */
00377     assertTrue( isCircuit(CH,camino) );
00378     // Si le hago "pop_back()" a "camino" no sería ciclo, pues
00379     // el primer y el último no son el mismo
00380     camino.pop_back();
00381     assertTrue( !isCircuit(CH,camino) );
00382 
00383     assertTrue( connected( CH,"A(2)", "A(1)", camino ) );
00384     /* Esto forma el camino:
00385                  A(2) -> B -> C(1) -> A(1)    Este no es un ciclo
00386      */
00387     assertTrue( !isCircuit(CH,camino ) );
00388     // No existe el ciclo aunque agregue el nodo de inicio otra vez
00389     camino.push_back("A(2)");
00390     assertTrue( !isCircuit(CH,camino) );
00391 
00392     assertTrue( !connected( CH,"A(1)", "F", camino ));
00393 
00394     // No existen ciclos en caminos a partir de "F"
00395     std::list<std::string> listTmp;
00396     CH.vertexList(listTmp);
00397 
00398     for ( std::list<std::string>::iterator iTmp = ++listTmp.begin();
00399           iTmp != listTmp.end(); ++iTmp
00400     ) {
00401          connected( CH,"F", *iTmp, camino );
00402          camino.push_back("F");
00403          assertTrue (!isCircuit(CH,camino));
00404     }
00405 
00406     // Una característica del grafo "G", es que no es conexo
00407     assertTrue( !isConnected(CH));
00408     // Además no es un árbol
00409     assertTrue( !isTree(CH));
00410     // Y tiene un arbol de expansión (spanning tree)
00411     Graph newG;
00412     assertTrue( spanningTree(CH,newG));
00413     assertTrue( isTree(newG));
00414     std::list<std::string> lT;
00415     newG.vertexList(lT);
00416     std::list<std::string> N_Nodos;
00417     int cant = 0;
00418     for(std::list<std::string>::iterator iT = lT.begin(); iT != lT.end(); ++iT){
00419         newG.vertexList(*iT, N_Nodos);
00420         cant += N_Nodos.size();
00421     }
00422     assertTrue(  cant+1 == lT.size() ); // Mido cantidad de aristas con cantidad de Nodos
00423 }
00424 
00425 /// Prueba \c Graph::test_spanningTree().
00426 void test_Graph::test_spanningTree() {
00427     {{ // test::spanningTree()
00428         Graph G;                                          //      B----->D
00429         G.set( "A", "B",  10 );   G.set( "A", "C",  12 ); //     /|    / |
00430         G.set( "C", "B",  14 );   G.set( "C", "D",  21 ); //    / |   /  |
00431         G.set( "C", "E",  16 );   G.set( "D", "B",  20 ); // A-> /|\ /   |
00432         G.set( "D", "E",  18 );                           //    \ | /    |
00433                                                           //     \|/    \|/
00434         // Tiene un arbol de expansión (spanning tree)    //      C----->E
00435         Graph T;
00436         assertTrue( spanningTree(G,T));
00437         assertTrue( isTree(T));
00438         std::list<std::string> T_Vertices;
00439         T.vertexList(T_Vertices);
00440         std::list<std::string> N_Nodos;
00441         int cant = 0;
00442         for( std::list<std::string>::iterator iT = T_Vertices.begin(); iT != T_Vertices.end(); ++iT ) {
00443             T.vertexList(*iT, N_Nodos);
00444             cant += N_Nodos.size();
00445         }
00446         assertTrue(  cant +1 == T_Vertices.size()); // Mido cantidad de aristas con cantidad de Nodos
00447 
00448         // El árbol de expansión no es un conexo
00449         assertTrue( !isConnected(T) );
00450 
00451         // En este caso es un árbol
00452         assertTrue( isTree(T) );
00453     }}
00454 }
00455 
00456 } // namespace ADH
00457 
00458 /// Programa principal para probar la clase \c ADH_Graph.
00459 int main() {
00460     using namespace ADH;
00461     using namespace std;
00462     test_Graph tester;
00463     tester.setUp();
00464     if (1) {
00465         tester.do_dump(cout); cout << endl;
00466         tester.do_cout(cout); cout << endl;
00467     }
00468     tester.run();
00469     cout << tester.summary() << endl;
00470     cout << tester.report() << endl;
00471     tester.set_cycles(true); // aparte por si se encicla
00472     tester.run();
00473     cout << endl << endl;
00474     cout << tester.report() << endl;
00475     return 0;
00476 }
00477 // EOF: test_Graph.cpp