Modulo [B]asico para prueba [unit]aria de programas:
 Todo Clases Namespaces Archivos Funciones Variables 'typedefs' Valores de enumeraciones Amigas 'defines'
ADH_Graph_Lib.cpp
Ir a la documentación de este archivo.
00001 /* ADH_Graph_Lib.cpp (C) 2007  adolfo@di-mare.com  */
00002 
00003 /** \file  ADH_Graph_Lib.cpp
00004     \brief Archivo de implementación para \c ADH_Graph_Lib.h
00005 
00006     \author Adolfo Di Mare <adolfo@di-mare.com>
00007     \date   2007
00008 */
00009 
00010 #include "ADH_Graph.h"
00011 #include "ADH_Graph_Lib.h"
00012 
00013 #include <algorithm>
00014 
00015 namespace ADH {
00016 
00017 /// Graba el valor de \c "G" en el flujo \c "COUT".
00018 std::ostream& operator<< (std::ostream &COUT, const Graph& G) {
00019     Graph::Rep::const_iterator it = G.m_DICC.begin();  // recorre m_DICC[]
00020     for ( ; it != G.m_DICC.end(); ++it ) {
00021         COUT << it->first << " ==> [";
00022         Graph::mapped_type::const_iterator jt = it->second.begin();
00023         while ( jt != it->second.end() ) {
00024             COUT << '<' << jt->second << '>' << jt->first ;
00025             ++jt;
00026             if ( jt != it->second.end() ) {
00027                 COUT << " , ";
00028             }
00029         }
00030         COUT << ']' << std::endl;
00031     }
00032     return COUT;
00033 }  // operator <<
00034 
00035 /// Graba el valor de \c "G" en el flujo \c "COUT".
00036 void dump( std::ostream & COUT, const Graph& G ) {
00037     Graph::Rep::const_iterator it = G.m_DICC.begin();
00038     for ( ; it != G.m_DICC.end(); ++it ) {
00039         Graph::Rep::const_iterator jt = G.m_DICC.begin();
00040         for ( ; jt != G.m_DICC.end(); ++jt ) {
00041             int val = 666;
00042             if ( G.isArc( it->first , jt->first , val ) ) {
00043                 COUT << it->first << "->" << jt->first << " == " << val << std::endl;
00044             }
00045         }
00046     }
00047 }
00048 
00049 /** \fn bool ADH::connected_set( const Graph & G , std::set< std::string > & S ,
00050                   const std::string & src , const std::string & dst , std::list< std::string > & C );
00051 
00052     \brief Determina si existe un camino desde \c "src" hasta \c "dst" sin pasar por los nodos de \c "S".
00053     - Este es el paso recursivo desde el método públic \c connected().
00054     - Le agrega valores a la lista \c "C", pero no la borra si no encuentra el camino.
00055     - No agrega \c "src" al principio de \c "C" (tampoco lo agrega en otro lado).
00056     - El conjunto \c "S" contiene vértices que ya fueron visitados.
00057     - Se usa \c "S" para evitar que el programa se encicle cuando el grafo tiene ciclos.
00058 */
00059 
00060 bool connected_set(
00061     const Graph & G ,             // grafo en el que se trabaja
00062     std::set< std::string > & S , // conjunto de vértices ya visitados
00063     const std::string & src ,     // vértice de salida
00064     const std::string & dst ,     // vértice de llegada
00065     std::list< std::string > & C  // camino src->dst
00066 ) {
00067     if ( src == dst ) {
00068         C.push_back( dst );
00069         return true;
00070     }
00071     std::list< std::string > L;
00072     std::list< std::string >::const_iterator it;
00073     G.vertexList ( src ,  L );
00074 
00075     for ( it=L.begin(); it!=L.end(); ++it ) {
00076         if ( S.find( *it ) != S.end() ) {
00077             continue; // ya en una invocación previa lo procesó
00078         }
00079         S.insert( *it ); // recuerde que ya pasó por aquí
00080         C.push_back( src );
00081         if ( connected_set( G, S, *it, dst , C ) ) {
00082             return true;
00083         }
00084         else {
00085             C.pop_back(); // *it no es parte de la solución
00086         }
00087     }
00088     return false;
00089 }
00090 
00091 /** Determina si existe un camino en el grafo comenzando en \c "src" y terminando en \c "dst".
00092     - Si <code> src == dst </code> retorna \c "true"
00093       (un vértice siempre está conectado consigo mismo).
00094     - Retorna \c "true" cuando el camino existe, y \c "false" en caso contrario.
00095     - La lista \c "C" contiene la secuencia de nodos del camino.
00096     - Si no hay camino, la lista \c "C" queda vacía.
00097 
00098     \dontinclude test_Graph.cpp
00099     \skipline    test::diagram()
00100     \until       }}
00101     \skipline    test::connected()
00102     \until       }}
00103     \see         test_Graph::test_connected()
00104 */
00105 bool connected(
00106     const Graph & G ,             // grafo a examinar
00107     const std::string & src ,     // vértice de salida
00108     const std::string & dst ,     // vértice de llegada
00109     std::list< std::string > & C  // camino src->dst
00110 ) {
00111     using std::string;
00112     std::set< std::string > S;
00113     C.clear(); // la borra toda
00114     if ( ! ( G.isVertex(src) && G.isVertex(dst) ) ) {
00115         return false;
00116     }
00117     if ( connected_set ( G, S, src , dst , C ) ) {
00118     //  C.push_front( src );
00119         return true;
00120     }
00121     return false;
00122 }
00123 
00124 /** Determina si el grafo \c "G" está conectado.
00125     - Determnina si siempre existe un camino entre cualesquiera 2 nodos.
00126 
00127     \dontinclude test_Graph.cpp
00128     \skipline    test::isConnected()
00129     \until       }}
00130     \see         test_Graph::isConnected()
00131     \author Joseiby Hernadez Cedeño <joherce@yahoo.com>
00132 */
00133 bool isConnected( const Graph & G ) {
00134     std::list< std::string > TMP;
00135     std::list< std::string > G_Vertices;
00136     G.vertexList(G_Vertices);
00137     std::list< std::string >::const_iterator i , j ;
00138     // Doble "for" para que compare todos los nodos con todos
00139     for ( i = G_Vertices.begin(); i != G_Vertices.end() ; ++i ) {
00140         for ( j = G_Vertices.begin(); j != G_Vertices.end() ; ++j ) {
00141             // Si la conexión no se da retorna "false"
00142             if ( ! connected( G , *i , *j , TMP ) ) {
00143                 return false;
00144             }
00145         }
00146     }
00147     return true;
00148 }
00149 
00150 /** Determina si el camino \c "C" es un circuito.
00151     Para que sea un circuito debe:
00152     - Realmente ser un camino
00153     - Que el primer y ultimo nodo sean el mismo
00154 
00155     \dontinclude test_Graph.cpp
00156     \skipline    test::isCircuit()
00157     \until       }}
00158     \see         test_Graph::isCircuit()
00159     \author Joseiby Hernadez Cedeño <joherce@yahoo.com>
00160 */
00161 bool isCircuit( const Graph & G , std::list< std::string > &C ) {
00162     // Primero analizo que el primer y ultimo nodo de la lista "C" son el mismo
00163     if ( C.back() != C.front() ) {
00164         return false;
00165     }
00166 
00167     // Segundo se comprueba que el camino exista en el orden dado
00168     bool esCircuito = true;
00169     std::list< std::string >::iterator it2 = ++(C.begin());
00170     for (std::list< std::string >::iterator it1 = C.begin();
00171          it2 != C.end() && esCircuito; ++it1, ++it2
00172     ) {
00173         int ch;
00174         esCircuito = G.isArc(*it1, *it2, ch);
00175     }
00176     return esCircuito;
00177 }
00178 
00179 /** Determina si el grafo \c "G" es o no un árbol.
00180     Para que sea un árbol debe:
00181     - Haber una sola raiz (nodo del cual se llegué a todos).
00182     - Poder alcanzar cada uno de los nodos DIRECTAMENTE desde un solo nodo,
00183       excepto la raiz, la cual no tiene ningun "padre". Por ejemplo:
00184 \code
00185  _________1_______     <---- Raiz
00186 |         |       |
00187 \/       \/       \/
00188 A      __2__     __3__       A cada nodo solo lo "toca" un unico nodo:
00189       |     |   |     |      1 --> A     1 --> 2     1 --> 3
00190       \/   \/   \/    \/     2 --> 4     2 --> 5     3 --> 6
00191       4     5   6      7     3 --> 7     4 --> 8     6 --> 9
00192       |         |
00193       \/        \/           Lo cual no equivale a que solo ese este conectado con el nodo
00194       8         9
00195 \endcode
00196 
00197     \dontinclude test_Graph.cpp
00198     \skipline    test::isTree()
00199     \until       }}
00200     \see         test_Graph::isTree()
00201     \author Joseiby Hernadez Cedeño <joherce@yahoo.com>
00202 */
00203 bool isTree( const Graph& G ) {
00204     // Primero: busco la raiz -> Nodo único del cual se llegue a todos
00205     std::list< std::string > G_Raices; // Nodos que pueden ser la raiz del árbol
00206     std::list< std::string > G_Vertices;
00207     G.vertexList(G_Vertices); // lista con todos los vértices (nodos) que hay.
00208 
00209     for ( std::list< std::string >::iterator iter = G_Vertices.begin();
00210           iter != G_Vertices.end(); ++iter
00211     ) {
00212         bool esRaiz = true;
00213         std::list< std::string > TMP;
00214 
00215         // Se recorre la lista para buscar que se conecte con todos los demás nodos
00216         for (std::list< std::string >::iterator iter2 = G_Vertices.begin();
00217              iter2 != G_Vertices.end() && esRaiz; ++iter2
00218         ) {
00219            // Cuando esRaiz = false se sale del ciclo
00220             esRaiz = connected( G, *iter, *iter2, TMP );
00221         }
00222 
00223         if (esRaiz) {   // SI cumple con la caracteristica de raíz la agrego a la lista de raices
00224             G_Raices.push_back(*iter);
00225         }
00226     }
00227 
00228     if ( G_Raices.size() != 1) {  // Si se encontró más de una raiz o no se encontró
00229         return  false;    // Incumple una condición para ser árbol
00230     }
00231 
00232     // Segundo: Verifico que a un nodo sólo se llegue DIRECTAMENTE de un solo nodo
00233     std::list< std::string > G_Visitados; // Nodos que son accesados directamente
00234     for ( std::list< std::string >::iterator iter = G_Vertices.begin();
00235           iter != G_Vertices.end() ; ++iter
00236     ) {
00237         std::list< std::string > Visitados_Nodo; // Lista con lugares donde puede accesar un nodo en particular
00238         G.vertexList( *iter, Visitados_Nodo );
00239         // Busca si los nodos que puede accesar el nodo "*iter" ya fueron accesados por otro nodo
00240         for ( std::list< std::string >::iterator iterT = Visitados_Nodo.begin();
00241               iterT != Visitados_Nodo.end(); ++iterT
00242         ) {
00243             // Lo busco en la lista de los que ya fueron visitados
00244             if ( G_Visitados.end() == std::find( G_Visitados.begin(),G_Visitados.end(), *iterT ) ) {
00245                 G_Visitados.push_back(*iterT); // Agrega si no está
00246             } else { // Desde más de un nodo se llega al nodo
00247                 return false; // Incumple una condición para ser árbol
00248             }
00249         }
00250     }
00251 
00252     // Tercero: Verifico que pude accesar directamente a TODOS los nodos
00253     // Si se acceso a todos los nodos quiere decir que la longitud de "G_Visitados"
00254     // será menor en 1 a la de "lista de vertices" ya que la raiz no se cuenta
00255     return ( G_Visitados.size() == G_Vertices.size()-1 );
00256 } // isTree()
00257 
00258 /** Construye un árbol de expansión (<em>spanning tree</em>) \c "T" para el grafo \c "G".
00259     - Lo retorna en \c "T".
00260     - Si se pudo construir el árbol correctamente devuelve \c "true"
00261     - Si no lo pudo construir retorna \c "false" y no cambia el valor de \c "T".
00262     - Si el arbol de expansión se logra, este tendrá conexión con todos los nodos.
00263 \code
00264           ---<----                   Arbol de expansión
00265          /        \
00266      A(1)         C(1)                 A(1)         C(1)
00267     /    \       /    \               /            /    \
00268    /      \     /      \             /            /      \
00269 F->--A(2)-->-B->        ->D->-+   F->--A(2)-->-B->        ->D
00270    \      /     \      /      |      \            \
00271     \    /       \    /       |       \            \
00272      A(3)<--------C(2)<-------+        A(3)         C(2)
00273 \endcode
00274 
00275     Nota: Generalmente el árbol de expansión de un grafo se puede sacar por medio de
00276     ciertos algoritmos ya inventados como el algoritmo de Kruskal y el de Prim. Pero como
00277     se está trabajando con grafos dirigidos el algoritmo se vuelve complejo.
00278 
00279     En este caso lo que se hace es "imaginar" que el árbol no es dirigido y sacar un árbol
00280     de expansión a partir de los nodos y conexiones que se tienen. El arbol de expansión
00281     en este caso sería un arbol que contiene TODOS los nodos del grafo.
00282 
00283     \dontinclude test_Graph.cpp
00284     \skipline    test::spanningTree()
00285     \until       }}
00286     \see         test_Graph::spanningTree()
00287     \author Joseiby Hernadez Cedeño <joherce@yahoo.com>
00288 */
00289 bool spanningTree( const Graph & G , Graph & T ) {
00290     Graph RES;
00291     std::list<std::string> G_nodosUsados; // Guarda los nodos que ya fueron usados
00292     // Recorrer la lista de todos los nodos
00293     std::list<std::string> G_Vertices;
00294     G.vertexList(G_Vertices);
00295     for ( std::list< std::string >::iterator iter = G_Vertices.begin();
00296           iter != G_Vertices.end(); ++iter
00297         ) {
00298             std::list< std::string > G_Visitados; // Lista con lugares donde puede accesar un nodo en particular
00299             G.vertexList( *iter, G_Visitados );
00300             // Agrega la "fuente" si esta no está
00301             if ( G_nodosUsados.end() == std::find(G_nodosUsados.begin(),G_nodosUsados.end(), *iter) ) {
00302                 G_nodosUsados.push_back(*iter);
00303             }
00304 
00305             // Busca si los nodos que puede accesar el nodo "*iter" ya fueron accesados por otro nodo
00306             for ( std::list< std::string >::iterator iterT = G_Visitados.begin();
00307                   iterT != G_Visitados.end(); ++iterT
00308             ) {
00309                 // Basta con que uno de los nodos no esté en la lista de los usados para que la arista sea válida
00310                 if ( G_nodosUsados.end() == std::find( G_nodosUsados.begin(),G_nodosUsados.end(), *iter ) ||
00311                      G_nodosUsados.end() == std::find( G_nodosUsados.begin(),G_nodosUsados.end(), *iterT)
00312                 ) { // si no está agrega el vértice a la lista de los usados
00313                     G_nodosUsados.push_back(*iterT);
00314                     // Y agrega la arista al arbol de expansión
00315                     RES.set(*iter, *iterT, 0); // Como valor cero porque no me importa la distancia
00316                 }
00317             }
00318     }
00319     // Al terminar el recorrido, verifico que los "G_nodosUsados" fueron todos los vertices del grafo
00320     // Ya que la menera en que se fueron insertando los valores a "G_nodosUsados" lo permite, solo comparo tamaños
00321     if ( G_nodosUsados.size() == G_Vertices.size() ) {
00322         T = RES;
00323         return true;
00324     }
00325     else {
00326         return false;
00327     }
00328 }
00329 
00330 } // namespace ADH
00331 
00332 // EOF: ADH_Graph_Lib.cpp