[B]asic module for [unit] program testing:
 All Classes Namespaces Files Functions Variables Typedefs Enumerator Friends Defines
ADH_Graph.cpp
Go to the documentation of this file.
00001 /* ADH_Graph.cpp (C) 2007  adolfo@di-mare.com  */
00002 
00003 #include "ADH_Graph.h"
00004 
00005 /** \file  ADH_Graph.cpp
00006     \brief Archivo de implementación para \c ADH_Graph.h
00007 
00008     \author Adolfo Di Mare <adolfo@di-mare.com>
00009     \date   2007
00010 */
00011 
00012 
00013 namespace ADH {
00014 
00015 /** Verifica la invariante del grafo.
00016     - Regresa \c "true" si el grafo \c "DDD" contiene un valor correcto
00017     - Podría retornar \c "true" para un grafo lista cuyo valor está corrupto
00018     - Podría no retornar si el grafo tiene su valor corrupto
00019 
00020     - Como los valores del grafo están ordenados, verifica
00021       que la lista que DDD contiene esté ordenada
00022 
00023     \par Rep Diagrama de la clase
00024     \code
00025     m_DICC[]
00026     +------+----------------------------------+
00027     |      | +---------+---------+----------+ |
00028     |  F   | | A(1)=>2 | A(2)=>8 | A(3)=>64 | |
00029     |      | +---------+---------+----------+ |
00030     +------+----------------------------------+
00031     |      | +------+                         |         A(1)         C(1)
00032     | A(1) | | B=>2 |                         |        /    \       /    \
00033     |      | +------+                         |       /      \     /      \
00034     +------+----------------------------------+    F----A(2)----B--        --D
00035     |      | +------+                         |       \      /     \      /
00036     | A(2) | | B=>8 |                         |        \    /       \    /
00037     |      | +------+                         |         A(3)         C(2)
00038     +------+----------------------------------+
00039     |      | +-------+                        |
00040     | A(3) | | B=>64 |                        |    G.set("F", "A(1)",  2 ); G.set( "A(1)", "B",  2 );
00041     |      | +-------+                        |    G.set("F", "A(2)",  8 ); G.set( "A(2)", "B",  8 );
00042     +------+----------------------------------+    G.set("F", "A(3)", 64 ); G.set( "A(3)", "B", 64 );
00043     |      | +---------+----------+           |
00044     |  B   | | C(1)=>3 | C(2)=>27 |           |    G.set("B", "C(1)",  3 ); G.set( "C(1)", "D",  3 );
00045     |      | +---------+----------+           |    G.set("B", "C(2)", 27 ); G.set( "C(2)", "D", 27 );
00046     +------+----------------------------------+
00047     |      | +------+                         |
00048     | C(1) | | D=>2 |                         |
00049     |      | +------+                         |
00050     +------+----------------------------------+
00051     |      | +------+                         |
00052     | C(2) | | D=>8 |                         |
00053     |      | +------+                         |
00054     +------+----------------------------------+
00055     |      | +-+                              |
00056     |  D   | | |                              |     D no es salida de ninguna arista
00057     |      | +-+                              |     - Su diccionario está vacío
00058     +------+----------------------------------+
00059     \endcode
00060 
00061     - El grafo está implementado como un diccionario que contiene otro diccionario.
00062     - La llave del diccionario principal es el vértice que comienza un arco.
00063     - Cada vértice tiene asociado un diccionario cuya llave es el vértice de destino.
00064       Este es el diccionario que representa cada arista.
00065     - El valor numérico asociado en el diccionario de cada arista es el valor de la arista.
00066     - Si un vértice no participa en ninguna arista, tampoco aparece en el grafo.
00067 /// - En el grado sólo están almacenados los vértices que participan en alguna arista.
00068 */
00069 bool check_ok( const Graph & DDD ) {
00070     if ( & DDD == 0 ) {
00071         /// - Invariante: ningún objeto puede estar almacenado en la posición nula.
00072         return false;
00073     }
00074     return true;
00075 }
00076 
00077 /// Establece que el grafo tiene la arista \c src->dst con valor \c "val".
00078 /// - Si ya la arista estaba en el grafo, no la agrega ni le cambia el valor asociado.
00079 void Graph::set( const std::string & src , const std::string & dst , int val ) {
00080     {   // Agrega primero los 2 vértices del arco (si no han sido agregados antes)
00081         m_DICC.insert( make_pair( src, Rep::mapped_type() ) );
00082         m_DICC.insert( make_pair( dst, Rep::mapped_type() ) ); // lo agrega si no estaba
00083     }
00084     {   Rep::iterator it = m_DICC.find( src );
00085         // Ya existe ese vértice en el diccionario
00086         it->second.insert( make_pair( dst , val ) );
00087     }
00088     return;
00089 
00090 /*  Nota:
00091     No es posible implementar esta operación usando 2 iteradores para recorrer
00092     "m_DICC". Si uno lo hace, el programa explota en tiempo de ejecución.
00093     - Los iteradores del diccionario std::map<> no se pueden copiar, pues no
00094       tienen su "operator=()" definido.
00095     - Un diccionario sólo puede tener un iterador que no sea "const", que es el
00096       único que puede cambiarlo. Los otros iteradores deben ser "const".
00097     - Así se evita que, al usar más de 1 iterador, el diccionario quede modificado
00098       de una forma indeseable.
00099     - Como no existe std::map<>::iterator.operator=(), lo más saludable al usar
00100       un iterador para modificar std::map<> es incluir en bloques { } el código
00101       en donde está definido el iterador, porque la única forma de inicializar
00102       std::map<>::iterator es usando su constructor:
00103       { Rep::iterator it = m_DICC.find( src ); ...  }
00104 */
00105 }
00106 
00107 /// Establece que el grafo tiene el vértice \c vtx.
00108 void Graph::set( const std::string & vtx ) {
00109 #if 1
00110     {   // Agrega el vértice sin arco (diccionario asociado vacío)
00111         m_DICC.insert( make_pair( vtx, Rep::mapped_type() ) );
00112     }
00113 #else
00114     Rep::iterator it = m_DICC.find( vtx );
00115     if ( it == m_DICC.end() ) {
00116         // Agrega el vértice sin aristas.
00117         Rep::mapped_type D;
00118         m_DICC.insert( make_pair( vtx , D ) );
00119     }
00120 #endif
00121 }
00122 
00123 /** Retorna \c "true" si existe el vértice \c vtx.
00124 
00125     \dontinclude test_Graph.cpp
00126     \skipline    test::isVertex()
00127     \until       }}
00128     \see         test_Graph::test_isVertex()
00129 */
00130 bool Graph::isVertex( const std::string & vtx ) const {
00131     Graph::Rep::const_iterator it = m_DICC.find( vtx );
00132     return ( it != m_DICC.end() );
00133 }
00134 
00135 /** Retorna \c "true" si existe el arco \c src->dst.
00136     - Si el arco existe, en \c val se copia el valor asociado al arco.
00137     - Si el arco no existe, retorna \c "false" y no cambia el valor de \c val.
00138 
00139     \dontinclude test_Graph.cpp
00140     \skipline    test::isVertex()
00141     \until       }}
00142     \see         test_Graph::test_isVertex()
00143 */
00144 bool Graph::isArc( const std::string & src , const std::string & dst , int & val ) const {
00145     Graph::Rep::const_iterator it = m_DICC.find( src );
00146     if ( it == m_DICC.end() ) {
00147         return false;
00148     }
00149     else {
00150         // Ya existe ese vértice en el diccionario
00151         Graph::mapped_type::const_iterator jt = it->second.find( dst );
00152         if ( jt == it->second.end() ) {
00153             return false;
00154         }
00155         else {
00156             val = jt->second;
00157             return true;
00158         }
00159     }
00160 }
00161 
00162 /** Retorna la lista de todos los vértices del grafo.
00163     - Deja la lista \c "L" vacía si no existe ningún vértice en el grafo.
00164 */
00165 void Graph::vertexList( std::list< std::string> & L ) const {
00166     L.clear();
00167     Graph::Rep::const_iterator it = m_DICC.begin();
00168     for ( ; it != m_DICC.end(); ++it ) {
00169         L.push_back( it->first );
00170     }
00171 }
00172 
00173 /** Retorna la lista de todos los vértices a los que se llega con un arco desde \c "vtx".
00174     - Deja la lista \c "L" vacía si no existe el vértice \c "vtx".
00175     - Deja la lista \c "L" vacía si no existe ningún arco que comience con el vértice \c "vtx".
00176 
00177     \dontinclude test_Graph.cpp
00178     \skipline    test::diagram()
00179     \until       }}
00180     \skipline    test::vertexList()
00181     \until       }}
00182     \see         test_Graph::test_vertexList()
00183 */
00184 void Graph::vertexList( std::string vtx , std::list< std::string> & L ) const {
00185     L.clear();
00186     Graph::Rep::const_iterator it = m_DICC.find( vtx );
00187     if ( it == m_DICC.end() ) {
00188         return; // no existe ese vértice
00189     }
00190     else {
00191         Graph::mapped_type::const_iterator jt = it->second.begin();
00192         for ( ; jt != it->second.end(); ++jt ) {
00193             L.push_back( jt->first );
00194         }
00195     }
00196 }
00197 
00198 } // namespace ADH
00199 
00200 // EOF: ADH_Graph.cpp