ADH_Graph.h

Go to the documentation of this file.

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

/** \file  ADH_Graph.h
    \brief Versión muy simplificada de un grafo implementado con \c std::map<>.

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

#ifndef ADH_Graph_h
#define ADH_Graph_h   "Versión 1"

#include <map>
#include <set>
#include <list>
#include <string>
#include <iostream>

/// ADH: Adolfo Di Mare H.
namespace ADH {} // Está acá para que Doxygen lo documente

namespace ADH {

/// Contenedor grapo dirigido en que los vértices son hileras y los valores de los arcos son enteros.
/// - En el grado sólo están almacenados los vértices que participan en alguna arista.
class Graph {
public:
    typedef std::string                   key_type;     ///< Tipo de los vértices.
    typedef std::map<  std::string, int > mapped_type;  ///< Lista de aristas para un vértice.
private:
    /// Abreviatura para el Rep, implementado con un diccionario.
    typedef std::map<  key_type, mapped_type > Rep;
public:
    typedef Rep::value_type value_type;  ///< Nombre estándar del objeto contenido
    typedef value_type& reference; ///< Referencia al objeto contenido
    typedef const value_type& const_reference; ///< Referencia constante al objeto contenido
private:
    /** Iteradores [CONST] simples para la clase \c "Graph".
        - Estos iteradores regresan parejas de valores del Rep.
        - No existen iteradores "no-const" para esta clase
        \dontinclude test_Graph.cpp
        \skipline    test::Rep_const_iterator()
        \until       }}
        \see         test_Graph::test_Rep_const_iterator()
    */
    class Rep_const_iterator {
        friend class Graph;
    public:
        Rep_const_iterator() : m_it() { } ///< Constructor

        /// Constructor de copia
        Rep_const_iterator( const Rep_const_iterator& o ) : m_it(o.m_it) { }  // copia el Rep directo
        Rep_const_iterator& operator=( const Rep_const_iterator& o ) {
            m_it = o.m_it; // la asignación op=() solo está definida para map<>::const_iterator
            return *this;
        } ///< Copia.

        friend bool operator == ( const Rep_const_iterator& p , const Rep_const_iterator& q ) {
            return p.m_it == q.m_it;
        } ///< ¿ <code>p == q</code> ?
        friend bool operator != ( const Rep_const_iterator& p , const Rep_const_iterator& q ) {
            return p.m_it != q.m_it;
        } ///< ¿ <code>p != q</code> ?

        Rep_const_iterator operator++(int)
            { Rep_const_iterator q = (*this); ++m_it; return q; } ///< \c it++
        Rep_const_iterator operator++() { ++m_it; return *this; } ///< \c ++it
        Rep_const_iterator operator--(int)
            { Rep_const_iterator q = (*this); --m_it; return q; } ///< \c it--
        Rep_const_iterator operator--() { --m_it; return *this; } ///< \c --it

        const value_type& operator*()  { return   *m_it ; } ///< \c *p
        const value_type* operator->() { return &(*m_it); } ///< \c p->
    private:
        Rep::const_iterator m_it; ///< Iterador [CONST] de \c "Graph"
    }; // Graph::Rep_const_iterator
public:
    /** Iteradores [CONST] para obtener todos los vértices de un grafo.
        - No existen iteradores "no-const" para esta clase
        \dontinclude test_Graph.cpp
        \skipline    test::Rep_const_iterator()
        \until       }}
        \see         test_Graph::test_Rep_const_iterator()
    */
    class const_iterator {
        friend class Graph;
    public:
        const_iterator() : m_it() { } ///< Constructor

        /// Constructor de copia
        const_iterator( const const_iterator& o ) : m_it(o.m_it) { }  // copia el Rep directo
        const_iterator& operator=( const const_iterator& o ) {
            m_it = o.m_it; // la asignación op=() solo está definida para map<>::const_iterator
            return *this;
        } ///< Copia.

        friend bool operator == ( const const_iterator& p , const const_iterator& q ) {
            return p.m_it == q.m_it;
        } ///< ¿ <code>p == q</code> ?
        friend bool operator != ( const const_iterator& p , const const_iterator& q ) {
            return p.m_it != q.m_it;
        } ///< ¿ <code>p != q</code> ?

        const_iterator operator++(int)
            { const_iterator q = (*this); ++m_it; return q; } ///< \c it++
        const_iterator operator++() { ++m_it; return *this; } ///< \c ++it
        const_iterator operator--(int)
            { const_iterator q = (*this); --m_it; return q; } ///< \c it--
        const_iterator operator--() { --m_it; return *this; } ///< \c --it

        const key_type& operator*()  { return   m_it->first; }  ///< \c *p
        const key_type* operator->() { return &(m_it->first); } ///< \c p->
    private:
        Rep::const_iterator m_it; ///< Iterador [CONST] de \c "Graph"
    }; // Graph::Rep_const_iterator
    Graph() : m_DICC() { } ///< Constructor de vector
    Graph(const Graph& G) : m_DICC() { *this = G; } ///< Constructor de copia
    ~Graph() { } ///< Destructor

    bool empty() const { return m_DICC.empty(); } ///< Retorna \c "true" si el contenedor está vacío

    Graph& operator=(const Graph& G) {
        m_DICC = G.m_DICC; return *this; } ///< Copia <code>*this = G</code>
    void swap(Graph& M) { m_DICC.swap(M.m_DICC); } ///< Intercambia los valores de \c "M" <==> \c "*this"
    void clear() { m_DICC.clear(); } ///< Deja al grafo vacío
private:
    /// Denota al primer valor del contenedor
    Rep_const_iterator begin_Rep() const { Rep_const_iterator p; p.m_it = m_DICC.begin(); return p; }
    /// Denota el valor que ya está fuera del contenedor
    Rep_const_iterator end_Rep  () const { Rep_const_iterator p; p.m_it = m_DICC.end();   return p; }
public:
    /// Denota al primer valor del contenedor
    const_iterator begin() const { const_iterator p; p.m_it = m_DICC.begin(); return p; }
    /// Denota el valor que ya está fuera del contenedor
    const_iterator end  () const { const_iterator p; p.m_it = m_DICC.end();   return p; }

    friend std::ostream& operator<< (std::ostream &COUT, const Graph& G);
    friend void dump( std::ostream &COUT, const Graph& G );

    friend bool check_ok( const Graph & DDD );
    friend class test_Graph; ///< Datos de prueba de la clase

public:
    bool isVertex( const std::string & vtx ) const;
    bool isArc( const std::string & src , const std::string & dst , int & val ) const;
    void set( const std::string & vtx );
    void set( const std::string & src , const std::string & dst , int val );
    void vertexList( std::list< std::string> & L ) const;
    void vertexList( std::string vtx , std::list< std::string> & L ) const;
private:
    Rep m_DICC; ///< Diccionario que contiene los valores del grafo
}; // Graph

} // namespace ADH

#endif // ADH_Graph_h

// EOF: ADH_Graph.h