ADH_Graph.cpp

Ir a la documentación de este archivo.

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

#include "ADH_Graph.h"

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

    \author Adolfo Di Mare <adolfo@di-mare.com>
    \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;
        }
    }
}

/** Retorna la lista de todos los vértices del grafo.
    - Deja la lista \c "L" vacía si no existe ningún vértice en el grafo.
*/
void Graph::vertexList( std::list< std::string> & L ) const {
    L.clear();
    Graph::Rep::const_iterator it = m_DICC.begin();
    for ( ; it != m_DICC.end(); ++it ) {
        L.push_back( it->first );
    }
}

/** Retorna la lista de todos los vértices a los que se llega con un arco desde \c "vtx".
    - Deja la lista \c "L" vacía si no existe el vértice \c "vtx".
    - Deja la lista \c "L" vacía si no existe ningún arco que comience con el vértice \c "vtx".

    \dontinclude test_Graph.cpp
    \skipline    test::diagram()
    \until       }}
    \skipline    test::vertexList()
    \until       }}
    \see         test_Graph::test_vertexList()
*/
void Graph::vertexList( std::string vtx , std::list< std::string> & L ) const {
    L.clear();
    Graph::Rep::const_iterator it = m_DICC.find( vtx );
    if ( it == m_DICC.end() ) {
        return; // no existe ese vértice
    }
    else {
        Graph::mapped_type::const_iterator jt = it->second.begin();
        for ( ; jt != it->second.end(); ++jt ) {
            L.push_back( jt->first );
        }
    }
}

} // namespace ADH

// EOF: ADH_Graph.cpp