|
Modulo [B]asico para prueba [unit]aria de programas:
|
|
Modulo [B]asico para prueba [unit]aria de programas:
|
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
1.8.0
