ADH_Graph_Lib.cpp

Ir a la documentación de este archivo.

/* ADH_Graph_Lib.cpp (C) 2007  adolfo@di-mare.com  */

/** \file  ADH_Graph_Lib.cpp
    \brief Archivo de implementación para \c ADH_Graph_Lib.h

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

#include "ADH_Graph.h"
#include "ADH_Graph_Lib.h"

#include <algorithm>

namespace ADH {

/// Graba el valor de \c "G" en el flujo \c "COUT".
std::ostream& operator<< (std::ostream &COUT, const Graph& G) {
    Graph::Rep::const_iterator it = G.m_DICC.begin();  // recorre m_DICC[]
    for ( ; it != G.m_DICC.end(); ++it ) {
        COUT << it->first << " ==> [";
        Graph::mapped_type::const_iterator jt = it->second.begin();
        while ( jt != it->second.end() ) {
            COUT << '<' << jt->second << '>' << jt->first ;
            ++jt;
            if ( jt != it->second.end() ) {
                COUT << " , ";
            }
        }
        COUT << ']' << std::endl;
    }
    return COUT;
}  // operator <<

/// Graba el valor de \c "G" en el flujo \c "COUT".
void dump( std::ostream & COUT, const Graph& G ) {
    Graph::Rep::const_iterator it = G.m_DICC.begin();
    for ( ; it != G.m_DICC.end(); ++it ) {
        Graph::Rep::const_iterator jt = G.m_DICC.begin();
        for ( ; jt != G.m_DICC.end(); ++jt ) {
            int val = 666;
            if ( G.isArc( it->first , jt->first , val ) ) {
                COUT << it->first << "->" << jt->first << " == " << val << std::endl;
            }
        }
    }
}

/** \fn bool ADH::connected_set( const Graph & G , std::set< std::string > & S ,
                  const std::string & src , const std::string & dst , std::list< std::string > & C );

    \brief Determina si existe un camino desde \c "src" hasta \c "dst" sin pasar por los nodos de \c "S".
    - Este es el paso recursivo desde el método públic \c connected().
    - Le agrega valores a la lista \c "C", pero no la borra si no encuentra el camino.
    - No agrega \c "src" al principio de \c "C" (tampoco lo agrega en otro lado).
    - El conjunto \c "S" contiene vértices que ya fueron visitados.
    - Se usa \c "S" para evitar que el programa se encicle cuando el grafo tiene ciclos.
*/

bool connected_set(
    const Graph & G ,             // grafo en el que se trabaja
    std::set< std::string > & S , // conjunto de vértices ya visitados
    const std::string & src ,     // vértice de salida
    const std::string & dst ,     // vértice de llegada
    std::list< std::string > & C  // camino src->dst
) {
    if ( src == dst ) {
        C.push_back( dst );
        return true;
    }
    std::list< std::string > L;
    std::list< std::string >::const_iterator it;
    G.vertexList ( src ,  L );

    for ( it=L.begin(); it!=L.end(); ++it ) {
        if ( S.find( *it ) != S.end() ) {
            continue; // ya en una invocación previa lo procesó
        }
        S.insert( *it ); // recuerde que ya pasó por aquí
        C.push_back( src );
        if ( connected_set( G, S, *it, dst , C ) ) {
            return true;
        }
        else {
            C.pop_back(); // *it no es parte de la solución
        }
    }
    return false;
}

/** Determina si existe un camino en el grafo comenzando en \c "src" y terminando en \c "dst".
    - Si <code> src == dst </code> retorna \c "true"
      (un vértice siempre está conectado consigo mismo).
    - Retorna \c "true" cuando el camino existe, y \c "false" en caso contrario.
    - La lista \c "C" contiene la secuencia de nodos del camino.
    - Si no hay camino, la lista \c "C" queda vacía.

    \dontinclude test_Graph.cpp
    \skipline    test::diagram()
    \until       }}
    \skipline    test::connected()
    \until       }}
    \see         test_Graph::test_connected()
*/
bool connected(
    const Graph & G ,             // grafo a examinar
    const std::string & src ,     // vértice de salida
    const std::string & dst ,     // vértice de llegada
    std::list< std::string > & C  // camino src->dst
) {
    using std::string;
    std::set< std::string > S;
    C.clear(); // la borra toda
    if ( ! ( G.isVertex(src) && G.isVertex(dst) ) ) {
        return false;
    }
    if ( connected_set ( G, S, src , dst , C ) ) {
    //  C.push_front( src );
        return true;
    }
    return false;
}

/** Determina si el grafo \c "G" está conectado.
    - Determnina si siempre existe un camino entre cualesquiera 2 nodos.

    \dontinclude test_Graph.cpp
    \skipline    test::isConnected()
    \until       }}
    \see         test_Graph::isConnected()
    \author Joseiby Hernadez Cedeño <joherce@yahoo.com>
*/
bool isConnected( const Graph & G ) {
    std::list< std::string > TMP;
    std::list< std::string > G_Vertices;
    G.vertexList(G_Vertices);
    std::list< std::string >::const_iterator i , j ;
    // Doble "for" para que compare todos los nodos con todos
    for ( i = G_Vertices.begin(); i != G_Vertices.end() ; ++i ) {
        for ( j = G_Vertices.begin(); j != G_Vertices.end() ; ++j ) {
            // Si la conexión no se da retorna "false"
            if ( ! connected( G , *i , *j , TMP ) ) {
                return false;
            }
        }
    }
    return true;
}

/** Determina si el camino \c "C" es un circuito.
    Para que sea un circuito debe:
    - Realmente ser un camino
    - Que el primer y ultimo nodo sean el mismo

    \dontinclude test_Graph.cpp
    \skipline    test::isCircuit()
    \until       }}
    \see         test_Graph::isCircuit()
    \author Joseiby Hernadez Cedeño <joherce@yahoo.com>
*/
bool isCircuit( const Graph & G , std::list< std::string > &C ) {
    // Primero analizo que el primer y ultimo nodo de la lista "C" son el mismo
    if ( C.back() != C.front() ) {
        return false;
    }

    // Segundo se comprueba que el camino exista en el orden dado
    bool esCircuito = true;
    std::list< std::string >::iterator it2 = ++(C.begin());
    for (std::list< std::string >::iterator it1 = C.begin();
         it2 != C.end() && esCircuito; ++it1, ++it2
    ) {
        int ch;
        esCircuito = G.isArc(*it1, *it2, ch);
    }
    return esCircuito;
}

/** Determina si el grafo \c "G" es o no un árbol.
    Para que sea un árbol debe:
    - Haber una sola raiz (nodo del cual se llegué a todos).
    - Poder alcanzar cada uno de los nodos DIRECTAMENTE desde un solo nodo,
      excepto la raiz, la cual no tiene ningun "padre". Por ejemplo:
\code
 _________1_______     <---- Raiz
|         |       |
\/       \/       \/
A      __2__     __3__       A cada nodo solo lo "toca" un unico nodo:
      |     |   |     |      1 --> A     1 --> 2     1 --> 3
      \/   \/   \/    \/     2 --> 4     2 --> 5     3 --> 6
      4     5   6      7     3 --> 7     4 --> 8     6 --> 9
      |         |
      \/        \/           Lo cual no equivale a que solo ese este conectado con el nodo
      8         9
\endcode

    \dontinclude test_Graph.cpp
    \skipline    test::isTree()
    \until       }}
    \see         test_Graph::isTree()
    \author Joseiby Hernadez Cedeño <joherce@yahoo.com>
*/
bool isTree( const Graph& G ) {
    // Primero: busco la raiz -> Nodo único del cual se llegue a todos
    std::list< std::string > G_Raices; // Nodos que pueden ser la raiz del árbol
    std::list< std::string > G_Vertices;
    G.vertexList(G_Vertices); // lista con todos los vértices (nodos) que hay.

    for ( std::list< std::string >::iterator iter = G_Vertices.begin();
          iter != G_Vertices.end(); ++iter
    ) {
        bool esRaiz = true;
        std::list< std::string > TMP;

        // Se recorre la lista para buscar que se conecte con todos los demás nodos
        for (std::list< std::string >::iterator iter2 = G_Vertices.begin();
             iter2 != G_Vertices.end() && esRaiz; ++iter2
        ) {
           // Cuando esRaiz = false se sale del ciclo
            esRaiz = connected( G, *iter, *iter2, TMP );
        }

        if (esRaiz) {   // SI cumple con la caracteristica de raíz la agrego a la lista de raices
            G_Raices.push_back(*iter);
        }
    }

    if ( G_Raices.size() != 1) {  // Si se encontró más de una raiz o no se encontró
        return  false;    // Incumple una condición para ser árbol
    }

    // Segundo: Verifico que a un nodo sólo se llegue DIRECTAMENTE de un solo nodo
    std::list< std::string > G_Visitados; // Nodos que son accesados directamente
    for ( std::list< std::string >::iterator iter = G_Vertices.begin();
          iter != G_Vertices.end() ; ++iter
    ) {
        std::list< std::string > Visitados_Nodo; // Lista con lugares donde puede accesar un nodo en particular
        G.vertexList( *iter, Visitados_Nodo );
        // Busca si los nodos que puede accesar el nodo "*iter" ya fueron accesados por otro nodo
        for ( std::list< std::string >::iterator iterT = Visitados_Nodo.begin();
              iterT != Visitados_Nodo.end(); ++iterT
        ) {
            // Lo busco en la lista de los que ya fueron visitados
            if ( G_Visitados.end() == std::find( G_Visitados.begin(),G_Visitados.end(), *iterT ) ) {
                G_Visitados.push_back(*iterT); // Agrega si no está
            } else { // Desde más de un nodo se llega al nodo
                return false; // Incumple una condición para ser árbol
            }
        }
    }

    // Tercero: Verifico que pude accesar directamente a TODOS los nodos
    // Si se acceso a todos los nodos quiere decir que la longitud de "G_Visitados"
    // será menor en 1 a la de "lista de vertices" ya que la raiz no se cuenta
    return ( G_Visitados.size() == G_Vertices.size()-1 );
} // isTree()

/** Construye un árbol de expansión (<em>spanning tree</em>) \c "T" para el grafo \c "G".
    - Lo retorna en \c "T".
    - Si se pudo construir el árbol correctamente devuelve \c "true"
    - Si no lo pudo construir retorna \c "false" y no cambia el valor de \c "T".
    - Si el arbol de expansión se logra, este tendrá conexión con todos los nodos.
\code
          ---<----                   Arbol de expansión
         /        \
     A(1)         C(1)                 A(1)         C(1)
    /    \       /    \               /            /    \
   /      \     /      \             /            /      \
F->--A(2)-->-B->        ->D->-+   F->--A(2)-->-B->        ->D
   \      /     \      /      |      \            \
    \    /       \    /       |       \            \
     A(3)<--------C(2)<-------+        A(3)         C(2)
\endcode

    Nota: Generalmente el árbol de expansión de un grafo se puede sacar por medio de
    ciertos algoritmos ya inventados como el algoritmo de Kruskal y el de Prim. Pero como
    se está trabajando con grafos dirigidos el algoritmo se vuelve complejo.

    En este caso lo que se hace es "imaginar" que el árbol no es dirigido y sacar un árbol
    de expansión a partir de los nodos y conexiones que se tienen. El arbol de expansión
    en este caso sería un arbol que contiene TODOS los nodos del grafo.

    \dontinclude test_Graph.cpp
    \skipline    test::spanningTree()
    \until       }}
    \see         test_Graph::spanningTree()
    \author Joseiby Hernadez Cedeño <joherce@yahoo.com>
*/
bool spanningTree( const Graph & G , Graph & T ) {
    Graph RES;
    std::list<std::string> G_nodosUsados; // Guarda los nodos que ya fueron usados
    // Recorrer la lista de todos los nodos
    std::list<std::string> G_Vertices;
    G.vertexList(G_Vertices);
    for ( std::list< std::string >::iterator iter = G_Vertices.begin();
          iter != G_Vertices.end(); ++iter
        ) {
            std::list< std::string > G_Visitados; // Lista con lugares donde puede accesar un nodo en particular
            G.vertexList( *iter, G_Visitados );
            // Agrega la "fuente" si esta no está
            if ( G_nodosUsados.end() == std::find(G_nodosUsados.begin(),G_nodosUsados.end(), *iter) ) {
                G_nodosUsados.push_back(*iter);
            }

            // Busca si los nodos que puede accesar el nodo "*iter" ya fueron accesados por otro nodo
            for ( std::list< std::string >::iterator iterT = G_Visitados.begin();
                  iterT != G_Visitados.end(); ++iterT
            ) {
                // Basta con que uno de los nodos no esté en la lista de los usados para que la arista sea válida
                if ( G_nodosUsados.end() == std::find( G_nodosUsados.begin(),G_nodosUsados.end(), *iter ) ||
                     G_nodosUsados.end() == std::find( G_nodosUsados.begin(),G_nodosUsados.end(), *iterT)
                ) { // si no está agrega el vértice a la lista de los usados
                    G_nodosUsados.push_back(*iterT);
                    // Y agrega la arista al arbol de expansión
                    RES.set(*iter, *iterT, 0); // Como valor cero porque no me importa la distancia
                }
            }
    }
    // Al terminar el recorrido, verifico que los "G_nodosUsados" fueron todos los vertices del grafo
    // Ya que la menera en que se fueron insertando los valores a "G_nodosUsados" lo permite, solo comparo tamaños
    if ( G_nodosUsados.size() == G_Vertices.size() ) {
        T = RES;
        return true;
    }
    else {
        return false;
    }
}

} // namespace ADH

// EOF: ADH_Graph_Lib.cpp