fork(1) download 
  1. #ifndef GRAFO_H_
  2. #define GRAFO_H_
  3. #include <list>
  4. #include <iostream>
  5. #define INFINITO 9999999;
  6. //-----------------------------------------------------------------------------------------------//
  7. using namespace std;
  8. //--------------------------------------  CLASE GRAFO  ------------------------------------------//
  9. template <typename C> class Grafo
  10. {
  11.     public:
  12.     //--------------------------------------  CLASE GRAFO  ------------------------------------------//
  13.         class Arco
  14.         {
  15.             public:
  16.                 Arco();
  17.                 Arco(const Arco & otroArco);
  18.                 Arco(int adyacente, const C & costo);
  19.                 int devolverAdyacente() const;
  20.                 const C & devolverCosto() const;
  21.                 int vertice;
  22.                 C costo;
  23.         };
  24.     public:
  25.         Grafo();
  26.         Grafo(const Grafo & otroGrafo);
  27.         ~Grafo();
  28.         Grafo & operator = (const Grafo & otroGrafo);
  29.         bool estaVacio() const;   // Devuelve true si la cantidad de vértices es cero
  30.         int devolverLongitud() const;   // Indica la cantidad de vértices del grafo
  31.         bool existeVertice(int vertice) const;
  32.         bool existeArco(int origen, int destino) const;
  33.         const C & costoArco(int origen, int destino) const;  // PRE CONDICION: existeArco(origen, destino)
  34.         void devolverVertices(list<int> & vertices) const;
  35.         void devolverAdyacentes(int origen, list<Arco> & adyacentes) const;
  36.         void agregarVertice(int vertice);
  37.         void eliminarVertice(int vertice);  // POST CONDICION: Para todo vértice v != vertice: !existeArco(v, vertice) && !existeArco(vertice, v)
  38.         void agregarArco(int origen, int destino, const C & costo);  // PRE CONDICION: existeVertice(origen) && existeVertice(destino)  // POST CONDICION: existeArco(origen, destino)
  39.         void eliminarArco(int origen, int destino);  // POST CONDICION: !existeArco(origen, destino)
  40.         void vaciar();
  41.     private:
  42.         struct NGrafo{
  43.             int vertice;
  44.             list<Arco> adyacentes;
  45.         };
  46.         list<NGrafo> grafo;
  47. };
  48. //-----------------------------------------------------------------------------------------------//
  49. //------------------------------- Implementacion clase ARCO -------------------------------------//
  50. //-----------------------------------------------------------------------------------------------//
  51. template <typename C> Grafo<C>::Arco::Arco()
  52. {
  53. }
  54. //-----------------------------------------------------------------------------------------------//
  55. template <typename C> Grafo<C>::Arco::Arco(const Arco & otroArco)
  56. {
  57.     this->costo = otroArco.devolverCosto();
  58.     this->vertice = otroArco.devolverAdyacente();
  59. }
  60. //-----------------------------------------------------------------------------------------------//
  61. template <typename C> Grafo<C>::Arco::Arco(int adyacente, const C & costo)
  62. {
  63.     vertice = adyacente;
  64.     this->costo = costo;
  65. }
  66. //-----------------------------------------------------------------------------------------------//
  67. template <typename C> int Grafo<C>::Arco::devolverAdyacente() const
  68. {
  69.     return this->vertice;
  70. }
  71. //-----------------------------------------------------------------------------------------------//
  72. template <typename C> const C & Grafo<C>::Arco::devolverCosto() const
  73. {
  74.     return costo;
  75. }
  76. //-----------------------------------------------------------------------------------------------//
  77. //------------------------------- Implementacion clase GRAFO ------------------------------------//
  78. //-----------------------------------------------------------------------------------------------//
  79.  
  80. template <typename C> ostream & operator << (ostream & salida, const Grafo<C> & grafo)
  81. {
  82. 	list<int> vertices;   //Recorremos todos los vertices
  83. 	grafo.devolverVertices(vertices);
  84. 	list<int>::iterator v;
  85. 	v = vertices.begin();
  86. 	cout << endl << "//------------------------------- GRAFO ------------------------------------//" << endl << endl;
  87. 	while (v != vertices.end()) 
  88. 	{
  89. 		salida << "Vertice: " << *v << endl;  // Recorremos todos los adyacentes de cada vertice
  90. 		list<typename Grafo<C>::Arco> adyacentes;
  91. 		grafo.devolverAdyacentes(*v, adyacentes);
  92. 		typename list<typename Grafo<C>::Arco>::iterator ady;
  93. 		ady = adyacentes.begin();
  94. 		while (ady != adyacentes.end()) 
  95. 		{
  96. 			salida << "            " << "-> " << ady->devolverAdyacente() << " con costo: (" << ady->costo << ")" << endl;
  97. 			ady++;
  98. 		}
  99. 		v++;
  100. 		cout << endl;
  101. 	}
  102. 	cout << "//-------------------------------------------------------------------------//" << endl << endl;
  103. 	return salida;
  104. }
  105. //-----------------------------------------------------------------------------------------------//
  106. template <typename C> Grafo<C>::Grafo()
  107. {
  108. }
  109. //-----------------------------------------------------------------------------------------------//
  110. template <typename C> Grafo<C>::Grafo(const Grafo & otroGrafo)
  111. {
  112.     list<int> otroGrafo_vertices;
  113.     list<Arco> otroGrafo_adyacentes;
  114.     vaciar();
  115.     typename list<int>::const_iterator vertices;
  116.     otroGrafo.devolverVertices(otroGrafo_vertices);
  117.     for(vertices = otroGrafo_vertices.begin(); vertices != otroGrafo_vertices.end(); vertices++)
  118.         this->agregarVertice(*vertices);
  119.     typename list<int>::const_iterator otroGrafo_iterador;
  120.     typename list<Arco>::const_iterator otroGrafo_adyacentes_iterador;
  121.     for(vertices = otroGrafo_vertices.begin(); vertices != otroGrafo_vertices.end(); vertices++, otroGrafo_adyacentes_iterador++)
  122.     {
  123.         otroGrafo.devolverAdyacentes(*vertices,otroGrafo_adyacentes);
  124.         for(otroGrafo_adyacentes_iterador = otroGrafo_adyacentes.begin(); otroGrafo_adyacentes_iterador != otroGrafo_adyacentes.end(); otroGrafo_adyacentes_iterador++)
  125.             agregarArco(*vertices, otroGrafo_adyacentes_iterador->devolverAdyacente(), otroGrafo_adyacentes_iterador->devolverCosto());
  126.     }
  127. }
  128. //-----------------------------------------------------------------------------------------------//
  129. template <typename C> Grafo<C>::~Grafo()
  130. {
  131. }
  132. //-----------------------------------------------------------------------------------------------//
  133. template <typename C> Grafo<C> & Grafo<C>::operator = (const Grafo & otroGrafo)
  134. {
  135.     list<int> otroGrafo_vertices;
  136.     list<Arco> otroGrafo_adyacentes;
  137.     vaciar();
  138.     typename list<int>::const_iterator vertices;
  139.     otroGrafo.devolverVertices(otroGrafo_vertices);
  140.     for(vertices = otroGrafo_vertices.begin(); vertices != otroGrafo_vertices.end(); vertices++)
  141.         this->agregarVertice(*vertices);
  142.     typename list<int>::const_iterator otroGrafo_iterador;
  143.     typename list<Arco>::const_iterator otroGrafo_adyacentes_iterador;
  144.     for(vertices = otroGrafo_vertices.begin(); vertices != otroGrafo_vertices.end(); vertices++, otroGrafo_adyacentes_iterador++)
  145.     {
  146.         otroGrafo.devolverAdyacentes(*vertices,otroGrafo_adyacentes);
  147.         for(otroGrafo_adyacentes_iterador = otroGrafo_adyacentes.begin(); otroGrafo_adyacentes_iterador != otroGrafo_adyacentes.end(); otroGrafo_adyacentes_iterador++)
  148.             agregarArco(*vertices, otroGrafo_adyacentes_iterador->devolverAdyacente(), otroGrafo_adyacentes_iterador->devolverCosto());
  149.     }
  150. }
  151. //-----------------------------------------------------------------------------------------------//
  152. template <typename C> bool Grafo<C>::estaVacio() const
  153. {
  154.     return grafo.size();
  155. }
  156. //-----------------------------------------------------------------------------------------------//
  157. template <typename C> int Grafo<C>::devolverLongitud() const
  158. {
  159.     return grafo.size();
  160. }
  161. //-----------------------------------------------------------------------------------------------//
  162. template <typename C> bool Grafo<C>::existeVertice(int vertice) const
  163. {
  164.     typename list<NGrafo>::const_iterator it;
  165.     it = grafo.begin();
  166.     while ((it != grafo.end())&&(it->vertice != vertice))
  167.         it++;
  168.     if (it != grafo.end())
  169.         return true;
  170.     else 
  171.         return false;
  172. }
  173. //-----------------------------------------------------------------------------------------------//
  174. template <typename C> bool Grafo<C>::existeArco(int origen, int destino) const
  175. {
  176.     list<Arco> adyacentes;
  177.     devolverAdyacentes(origen,adyacentes);
  178.     if(adyacentes.size())
  179.     {
  180.         typename list<Arco>::const_iterator it;
  181.         it = adyacentes.begin();
  182.         while((it != adyacentes.end())&&(it->devolverAdyacente() != destino))
  183.             it++;
  184.         if (it != adyacentes.end())
  185.             return true;
  186.         else 
  187.             return false;
  188.     }
  189.     else 
  190.         return false;
  191. }
  192. //-----------------------------------------------------------------------------------------------//
  193. template <typename C> const C & Grafo<C>::costoArco(int origen, int destino) const
  194. {
  195.     list<Arco> adyacentes;
  196.     devolverAdyacentes(origen,adyacentes);
  197.     if (adyacentes.size())
  198.     {
  199.         typename list<Arco>::const_iterator it;
  200.         it = adyacentes.begin();
  201.         while ((it != adyacentes.end())&&(it->devolverAdyacente() != destino))
  202.             it++;
  203.         if (it != adyacentes.end())
  204.             return it->devolverCosto();
  205.     }
  206.     return INFINITO;
  207. }
  208. //-----------------------------------------------------------------------------------------------//
  209. template <typename C> void Grafo<C>::devolverVertices(list<int> & vertices) const
  210. {
  211.     typename list<NGrafo>::const_iterator it;
  212.     it = grafo.begin();
  213.     while (it != grafo.end())
  214.     {
  215.         vertices.push_back(it->vertice);
  216.         it++;
  217.     }
  218. }
  219. //-----------------------------------------------------------------------------------------------//
  220. template <typename C> void Grafo<C>::devolverAdyacentes(int origen, list<Arco> & adyacentes) const
  221. {
  222.     if(existeVertice(origen))
  223.     {
  224.         typename list<NGrafo>::const_iterator it;
  225.         it = grafo.begin();
  226.         while ((it != grafo.end())&&(it->vertice != origen))
  227.             it++;
  228.         adyacentes = it->adyacentes;
  229.     }
  230. }
  231. //-----------------------------------------------------------------------------------------------//
  232. template <typename C> void Grafo<C>::agregarVertice(int vertice)
  233. {
  234.     NGrafo Nuevo;
  235.     Nuevo.vertice = vertice;
  236.     this->grafo.push_back(Nuevo);
  237. }
  238. //-----------------------------------------------------------------------------------------------//
  239. template <typename C> void Grafo<C>::eliminarVertice(int vertice)
  240. {
  241.     typename list<NGrafo>::iterator it;
  242.     it = grafo.begin();
  243.     while((it != grafo.end())&&(it->vertice != vertice))
  244.         it++;
  245.     if(it != grafo.end())
  246.     {
  247.         it->adyacentes.clear();
  248.         grafo.erase(it);
  249.     }
  250.     else 
  251.         cout << "El elemento que desea borrar no existe" << endl;
  252. }
  253. //-----------------------------------------------------------------------------------------------//
  254. template <typename C> void Grafo<C>::agregarArco(int origen, int destino, const C & costo)
  255. {
  256.     // para hacer esta funcion, se verifica de que existan los vertices, si existen se busca la lista de adyacentes y se verifica de que no exista el arco.
  257.     typename list<NGrafo>::iterator begin;
  258.     typename list<NGrafo>::iterator origen_vertice;
  259.     typename list<Arco>::const_iterator it_adyacentes;
  260.     typename list<Arco>::const_iterator it_adyacentes_end;
  261.     begin = grafo.begin();
  262.     bool _origen = false;
  263.     bool _destino = false;   // se comienza con los dos vertices no encontrados (false)
  264.     while ((begin != grafo.end())&&((!_origen)||(!_destino)))
  265.     {
  266.         if ((begin->vertice == origen)&&(!_origen))
  267.         {
  268.             _origen = true;
  269.             it_adyacentes = begin->adyacentes.begin();
  270.             origen_vertice = begin;
  271.             it_adyacentes_end = begin->adyacentes.end();
  272.         }
  273.         if ((begin->vertice == destino)&&(!_destino))
  274.             _destino = true;
  275.         begin++;
  276.     }
  277.     if ((_origen)&&(_destino))
  278.     {   
  279.         while ((it_adyacentes != it_adyacentes_end)&&(it_adyacentes->devolverAdyacente() != destino))
  280.             it_adyacentes++;
  281.         if (it_adyacentes == it_adyacentes_end)
  282.         {
  283.             Arco nuevo(destino,costo);
  284.             origen_vertice->adyacentes.push_back(nuevo);
  285.         }
  286.     }
  287.     else 
  288.         cout << "No es posible agregar el arco, uno o mas vertices no existen" << endl;
  289. }
  290. //-----------------------------------------------------------------------------------------------//
  291. template <typename C> void Grafo<C>::eliminarArco(int origen, int destino)
  292. {
  293.     typename list<NGrafo>::iterator begin;
  294.     typename list<NGrafo>::iterator origen_vertice;
  295.     typename list<Arco>::iterator it_adyacentes;
  296.     typename list<Arco>::const_iterator it_adyacentes_end;
  297.     begin = grafo.begin();
  298.     bool _origen = false;
  299.     bool _destino = false;    // se comienza con los dos vertices no encontrados (false)
  300.     while ((begin != grafo.end())&&((!_origen)||(!_destino)))
  301.     {
  302.         if ((begin->vertice == origen)&&(!_origen))
  303.         {
  304.             _origen = true;
  305.             it_adyacentes = begin->adyacentes.begin();
  306.             origen_vertice = begin;
  307.             it_adyacentes_end = begin->adyacentes.end();
  308.         }
  309.         if ((begin->vertice == destino)&&(!_destino))
  310.             _destino = true;
  311.         begin++;
  312.     }
  313.     if ((_origen)&&(_destino))
  314.     {
  315.         while ((it_adyacentes != it_adyacentes_end)&&(it_adyacentes->devolverAdyacente() != destino))
  316.             it_adyacentes++;
  317.         if (it_adyacentes != it_adyacentes_end)
  318.             origen_vertice->adyacentes.erase(it_adyacentes);
  319.         else 
  320.             cout << "No es posible eliminar el arco, uno o mas vertices no existen" << endl;
  321.     }
  322.     else 
  323.         cout << "No es posible eliminar el arco, uno o mas vertices no existen" << endl;
  324. }
  325. //-----------------------------------------------------------------------------------------------//
  326. template <typename C> void Grafo<C>::vaciar()
  327. {
  328.     typename list<NGrafo>::iterator it;
  329.     typename list<Arco>::iterator borrar;
  330.     typename list<Arco>::iterator borrar_aux;
  331.     it = grafo.begin();
  332.     while(it!=grafo.end())
  333.     {
  334.         borrar = it->adyacentes.begin();
  335.         while(borrar != it->adyacentes.end())
  336.         {
  337.             borrar_aux = borrar;
  338.             borrar++;
  339.             it->adyacentes.erase(borrar_aux);
  340.         }
  341.         it++;
  342.     }
  343.     grafo.clear();
  344. }
  345. //-----------------------------------------------------------------------------------------------//
  346. #endif /* GRAFO_H_ */
  347.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
compilation info 
/usr/lib/gcc/i486-linux-gnu/4.8/../../../i386-linux-gnu/crt1.o: In function `_start':
(.text+0x18): undefined reference to `main'
collect2: error: ld returned 1 exit status
stdout 
Standard output is empty
https://ideone.com/1N5dfc
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!