ADH_Graph.cpp

Ir a la documentación de este archivo.

/* ADH_Graph.cpp (C) 2007  [email protected]  */

#include "ADH_Graph.h"

/** \file  ADH_Graph.cpp
    \brief Archivo de implementaci¢n para \c ADH_Graph.h

    \author Adolfo Di Mare <[email protected]>
    \date   2007
*/


namespace ADH {

/** Verifica la invariante del grafo.
    - Regresa \c "true" si el grafo \c "DDD" contiene un valor correcto
    - Podría retornar \c "true" para un grafo lista cuyo valor está corrupto
    - Podría no retornar si el grafo tiene su valor corrupto

    - Como los valores del grafo están ordenados, verifica
      que la lista que DDD contiene esté ordenada

    \par Rep Diagrama de la clase
    \code
        m_DICC[]
    +------+-----------------------------------+
    |      | +---------+---------+-----------+ |
    |  F   | | A(1)=>2 | A(2)=>8 | A(3)==>64 | |
    |      | +---------+---------+-----------+ |
    +------+-----------------------------------+
    |      | +------+                          |         A(1)         C(1)
    | A(1) | | B=>2 |                          |        /    \       /    \
    |      | +------+                          |       /      \     /      \
    +------+-----------------------------------+    F----A(2)----B--        --D
    |      | +------+                          |       \      /     \      /
    | A(2) | | B=>8 |                          |        \    /       \    /
    |      | +------+                          |         A(3)         C(2)
    +------+-----------------------------------+
    |      | +-------+                         |
    | A(3) | | B=>64 |                         |    G.set("F", "A(1)",  2 ); G.set( "A(1)", "B",  2 );
    |      | +-------+                         |    G.set("F", "A(2)",  8 ); G.set( "A(2)", "B",  8 );
    +------+-----------------------------------+    G.set("F", "A(3)", 64 ); G.set( "A(3)", "B", 64 );
    |      | +---------+----------+            |
    |  B   | | C(1)=>3 | C(2)=>27 |            |    G.set("B", "C(1)",  3 ); G.set( "C(1)", "D",  3 );
    |      | +---------+----------+            |    G.set("B", "C(2)", 27 ); G.set( "C(2)", "D", 27 );
    +------+-----------------------------------+
    |      | +------+                          |
    | C(1) | | D=>2 |                          |
    |      | +------+                          |
    +------+-----------------------------------+
    |      | +------+                          |
    | C(2) | | D=>8 |                          |
    |      | +------+                          |
    +------+-----------------------------------+
    |      | +-+                               |
    |  D   | | |                               |     D no es salida de ninguna arista
    |      | +-+                               |     - Su diccionario está vacío
    +------+-----------------------------------+
    \endcode

    - El grafo está implementado como un diccionario que contiene otro diccionario.
    - La llave del diccionario principal es el vértice que comienza un arco.
    - Cada vértice tiene asociado un diccionario cuya llave es el vértice de destino.
      Este es el diccionario que representa cada arista.
    - El valor numérico asociado en el diccionario de cada arista es el valor de la arista.
    - Si un vértice no participa en ninguna arista, tampoco aparece en el grafo.
/// - En el grado sólo están almacenados los vértices que participan en alguna arista.
*/
bool check_ok( const Graph & DDD ) {
    if ( & DDD == 0 ) {
        /// - Invariante: ningún objeto puede estar almacenado en la posición nula.
        return false;
    }
    return true;
}

/// Establece que el grafo tiene la arista \c src->dst con valor \c "val".
/// - Si ya la arista estaba en el grafo, no la agrega ni le cambia el valor asociado.
void Graph::set( const std::string & src , const std::string & dst , int val ) {
    {   // Agrega primero los 2 vértices del arco (si no han sido agregados antes)
        m_DICC.insert( make_pair( src, Rep::mapped_type() ) );
        m_DICC.insert( make_pair( dst, Rep::mapped_type() ) ); // lo agrega si no estaba
    }
    {   Rep::iterator it = m_DICC.find( src );
        // Ya existe ese vértice en el diccionario
        it->second.insert( make_pair( dst , val ) );
    }
    return;

/*  Nota:
    No es posible implementar esta operación usando 2 iteradores para recorrer
    "m_DICC". Si uno lo hace, el programa explota en tiempo de ejecución.
    - Los iteradores del diccionario std::map<> no se pueden copiar, pues no
      tienen su "operator=()" definido.
    - Un diccionario sólo puede tener un iterador que no sea "const", que es el
      único que puede cambiarlo. Los otros iteradores deben ser "const".
    - Así se evita que, al usar más de 1 iterador, el diccionario quede modificado
      de una forma indeseable.
    - Como no existe std::map<>::iterator.operator=(), lo más saludable al usar
      un iterador para modificar std::map<> es incluir en bloques { } el código
      en donde está definido el iterador, porque la única forma de inicializar
      std::map<>::iterator es usando su constructor:
      { Rep::iterator it = m_DICC.find( src ); ...  }
*/
}

/// Establece que el grafo tiene el vértice \c vtx.
void Graph::set( const std::string & vtx ) {
#if 1
        {   // Agrega el vértice sin arco (diccionario asociado vacío)
        m_DICC.insert( make_pair( vtx, Rep::mapped_type() ) );
        }
#else
        Rep::iterator it = m_DICC.find( vtx );
    if ( it == m_DICC.end() ) {
        // Agrega el vértice sin aristas.
        Rep::mapped_type D;
        m_DICC.insert( make_pair( vtx , D ) );
    }
#endif
}

/** Retorna \c "true" si existe el vértice \c vtx.

    \dontinclude test_Graph.cpp
    \skipline    test::isVertex()
    \until       }}
    \see         test_Graph::test_isVertex()
*/
bool Graph::isVertex( const std::string & vtx ) const {
    Graph::Rep::const_iterator it = m_DICC.find( vtx );
    return ( it != m_DICC.end() );
}

/** Retorna \c "true" si existe el arco \c src->dst.
    - Si el arco existe, en \c val se copia el valor asociado al arco.
    - Si el arco no existe, retorna \c "false" y no cambia el valor de \c val.

    \dontinclude test_Graph.cpp
    \skipline    test::isVertex()
    \until       }}
    \see         test_Graph::test_isVertex()
*/
bool Graph::isArc( const std::string & src , const std::string & dst , int & val ) const {
    Graph::Rep::const_iterator it = m_DICC.find( src );
    if ( it == m_DICC.end() ) {
        return false;
    }
    else {
        // Ya existe ese vértice en el diccionario
        Graph::mapped_type::const_iterator jt = it->second.find( dst );
        if ( jt == it->second.end() ) {
            return false;
        }
        else {
            val = jt->second;
            return true;
        }
    }
}

/// 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;
            }
        }
    }
}

/** Determina si existe un camino en el grafo comenzando en \c "src" y terminando en \c "dst".
    - 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 Graph::connected( const std::string & src , const std::string & dst , std::list< std::string > & C ) {
    int val = 0;
        bool res = false;
        Graph::Rep::const_iterator it = m_DICC.find( src );
        
    if ( it == m_DICC.end() ) {
        return false;
    }
    else {

                C.push_back(src);
                for (int i = 0; i != it->second.size(); ++i ) {
                        std::map<  std::string, int >::const_iterator jt = it->second.begin();
                        for ( ; jt != it->second.end(); ++jt ) {
                                if ( isArc(jt->first, dst, val)){
                                        C.push_back(jt->first);
                                        C.push_back(dst);
                                        res = true;
                                        return res;
                                }
                                else{
                                        res = connected(jt->first, dst, C);                             
                                }

                        }
                
                        //++it
                }

        }

        return res;
}


} // namespace ADH

// EOF: ADH_Graph.cpp

---

Hosted by www.Geocities.ws