[B]asic module for [unit] program testing:
 All Classes Namespaces Files Functions Variables Typedefs Enumerator Friends Defines
ADH_Graph.h
Go to the documentation of this file.
00001 /* ADH_Graph.h  (C) 2007  adolfo@di-mare.com  */
00002 
00003 /** \file  ADH_Graph.h
00004     \brief Versión muy simplificada de un grafo implementado con \c std::map<>.
00005 
00006     \author Adolfo Di Mare <adolfo@di-mare.com>
00007     \date   2007
00008 */
00009 
00010 #ifndef ADH_Graph_h
00011 #define ADH_Graph_h   "Versión 1"
00012 
00013 #include <map>
00014 #include <set>
00015 #include <list>
00016 #include <string>
00017 #include <iostream>
00018 
00019 /// ADH: Adolfo Di Mare H.
00020 namespace ADH {} // Está acá para que Doxygen lo documente
00021 
00022 namespace ADH {
00023 
00024 /// Contenedor grapo dirigido en que los vértices son hileras y los valores de los arcos son enteros.
00025 /// - En el grado sólo están almacenados los vértices que participan en alguna arista.
00026 class Graph {
00027 public:
00028     typedef std::string                   key_type;     ///< Tipo de los vértices.
00029     typedef std::map<  std::string, int > mapped_type;  ///< Lista de aristas para un vértice.
00030 private:
00031     /// Abreviatura para el Rep, implementado con un diccionario.
00032     typedef std::map<  key_type, mapped_type > Rep;
00033 public:
00034     typedef Rep::value_type value_type;  ///< Nombre estándar del objeto contenido
00035     typedef value_type& reference; ///< Referencia al objeto contenido
00036     typedef const value_type& const_reference; ///< Referencia constante al objeto contenido
00037 private:
00038     /** Iteradores [CONST] simples para la clase \c "Graph".
00039         - Estos iteradores regresan parejas de valores del Rep.
00040         - No existen iteradores "no-const" para esta clase
00041         \dontinclude test_Graph.cpp
00042         \skipline    test::Rep_const_iterator()
00043         \until       }}
00044         \see         test_Graph::test_Rep_const_iterator()
00045     */
00046     class Rep_const_iterator {
00047         friend class Graph;
00048     public:
00049         Rep_const_iterator() : m_it() { } ///< Constructor
00050 
00051         /// Constructor de copia
00052         Rep_const_iterator( const Rep_const_iterator& o ) : m_it(o.m_it) { }  // copia el Rep directo
00053         Rep_const_iterator& operator=( const Rep_const_iterator& o ) {
00054             m_it = o.m_it; // la asignación op=() solo está definida para map<>::const_iterator
00055             return *this;
00056         } ///< Copia.
00057 
00058         friend bool operator == ( const Rep_const_iterator& p , const Rep_const_iterator& q ) {
00059             return p.m_it == q.m_it;
00060         } ///< ¿ <code>p == q</code> ?
00061         friend bool operator != ( const Rep_const_iterator& p , const Rep_const_iterator& q ) {
00062             return p.m_it != q.m_it;
00063         } ///< ¿ <code>p != q</code> ?
00064 
00065         Rep_const_iterator operator++(int)
00066             { Rep_const_iterator q = (*this); ++m_it; return q; } ///< \c it++
00067         Rep_const_iterator operator++() { ++m_it; return *this; } ///< \c ++it
00068         Rep_const_iterator operator--(int)
00069             { Rep_const_iterator q = (*this); --m_it; return q; } ///< \c it--
00070         Rep_const_iterator operator--() { --m_it; return *this; } ///< \c --it
00071 
00072         const value_type& operator*()  { return   *m_it ; } ///< \c *p
00073         const value_type* operator->() { return &(*m_it); } ///< \c p->
00074     private:
00075         Rep::const_iterator m_it; ///< Iterador [CONST] de \c "Graph"
00076     }; // Graph::Rep_const_iterator
00077 public:
00078     /** Iteradores [CONST] para obtener todos los vértices de un grafo.
00079         - No existen iteradores "no-const" para esta clase
00080         \dontinclude test_Graph.cpp
00081         \skipline    test::Rep_const_iterator()
00082         \until       }}
00083         \see         test_Graph::test_Rep_const_iterator()
00084     */
00085     class const_iterator {
00086         friend class Graph;
00087     public:
00088         const_iterator() : m_it() { } ///< Constructor
00089 
00090         /// Constructor de copia
00091         const_iterator( const const_iterator& o ) : m_it(o.m_it) { }  // copia el Rep directo
00092         const_iterator& operator=( const const_iterator& o ) {
00093             m_it = o.m_it; // la asignación op=() solo está definida para map<>::const_iterator
00094             return *this;
00095         } ///< Copia.
00096 
00097         friend bool operator == ( const const_iterator& p , const const_iterator& q ) {
00098             return p.m_it == q.m_it;
00099         } ///< ¿ <code>p == q</code> ?
00100         friend bool operator != ( const const_iterator& p , const const_iterator& q ) {
00101             return p.m_it != q.m_it;
00102         } ///< ¿ <code>p != q</code> ?
00103 
00104         const_iterator operator++(int)
00105             { const_iterator q = (*this); ++m_it; return q; } ///< \c it++
00106         const_iterator operator++() { ++m_it; return *this; } ///< \c ++it
00107         const_iterator operator--(int)
00108             { const_iterator q = (*this); --m_it; return q; } ///< \c it--
00109         const_iterator operator--() { --m_it; return *this; } ///< \c --it
00110 
00111         const key_type& operator*()  { return   m_it->first; }  ///< \c *p
00112         const key_type* operator->() { return &(m_it->first); } ///< \c p->
00113     private:
00114         Rep::const_iterator m_it; ///< Iterador [CONST] de \c "Graph"
00115     }; // Graph::Rep_const_iterator
00116     Graph() : m_DICC() { } ///< Constructor de vector
00117     Graph(const Graph& G) : m_DICC() { *this = G; } ///< Constructor de copia
00118     ~Graph() { } ///< Destructor
00119 
00120     bool empty() const { return m_DICC.empty(); } ///< Retorna \c "true" si el contenedor está vacío
00121 
00122     Graph& operator=(const Graph& G) {
00123         m_DICC = G.m_DICC; return *this; } ///< Copia <code>*this = G</code>
00124     void swap(Graph& M) { m_DICC.swap(M.m_DICC); } ///< Intercambia los valores de \c "M" <==> \c "*this"
00125     void clear() { m_DICC.clear(); } ///< Deja al grafo vacío
00126 private:
00127     /// Denota al primer valor del contenedor
00128     Rep_const_iterator begin_Rep() const { Rep_const_iterator p; p.m_it = m_DICC.begin(); return p; }
00129     /// Denota el valor que ya está fuera del contenedor
00130     Rep_const_iterator end_Rep  () const { Rep_const_iterator p; p.m_it = m_DICC.end();   return p; }
00131 public:
00132     /// Denota al primer valor del contenedor
00133     const_iterator begin() const { const_iterator p; p.m_it = m_DICC.begin(); return p; }
00134     /// Denota el valor que ya está fuera del contenedor
00135     const_iterator end  () const { const_iterator p; p.m_it = m_DICC.end();   return p; }
00136 
00137     friend std::ostream& operator<< (std::ostream &COUT, const Graph& G);
00138     friend void dump( std::ostream &COUT, const Graph& G );
00139 
00140     friend bool check_ok( const Graph & DDD );
00141     friend class test_Graph; ///< Datos de prueba de la clase
00142 
00143 public:
00144     bool isVertex( const std::string & vtx ) const;
00145     bool isArc( const std::string & src , const std::string & dst , int & val ) const;
00146     void set( const std::string & vtx );
00147     void set( const std::string & src , const std::string & dst , int val );
00148     void vertexList( std::list< std::string> & L ) const;
00149     void vertexList( std::string vtx , std::list< std::string> & L ) const;
00150 private:
00151     Rep m_DICC; ///< Diccionario que contiene los valores del grafo
00152 }; // Graph
00153 
00154 } // namespace ADH
00155 
00156 #endif // ADH_Graph_h
00157 
00158 // EOF: ADH_Graph.h