Desarrolladores:
nodo.hpp
/*! \par Fichero: nodo.hpp Nodo representa la clase nodo definida mediante template (plantilla) */ #ifndef _NODO_HPP_ #define _NODO_HPP_ #include "arbol.hpp" namespace IA { //! Definición de la plantilla de la clase Nodo template < class T > class Nodo { //! \name Atributos privados de la clase Nodo private: T _dato; //!< Dato almacenado por el Nodo std::vector <Nodo <T> *> _hijo; //!< Vector de punteros a nodos hijos del Nodo Nodo <T> * _padre; //!< Puntero al padre del Nodo Arbol<T> * _root; //!< Puntero al arbol del que procede int _clave; //!< Identificador unico de nodo en el arbol del que procede //! \name Funciones o métodos públicos de la clase Nodo public: //! \name Constructores de la clase Nodo /*! \brief Constructor que crea un Nodo a partir del dato que va a contener \attention Función sobrecargada \param dato de tipo T pasado como referencia constante \param padre puntero al nodo padre \pre Ninguna \post Ninguna \sa Nodo() */ inline Nodo(T const & dato, Nodo <T> const * padre) { setDato(dato); setPadre(padre); setArbol(padre->getArbol());//el árbol de este nodo, serál mismo que de su padre setClave(_root->getID()); _root->addID(); _root->addHijosTotales(); setNumeroHijos(0); } /*! \brief Constructor que crea un Nodo a partir del dato que va a contener \attention Función sobrecargada \param dato de tipo T pasado como referencia constante \param root puntero al arbol del que depende \pre Ninguna \post Ninguna \sa Nodo() */ inline Nodo(T const & dato, Arbol<T> * root) { setDato(dato); setPadre(NULL); setArbol(root); setClave(_root->getID()); _root->addID(); _root->addHijosTotales(); setNumeroHijos(0); } /*! \brief Constructor de "copia" que crea un Nodo a partir de otro Nodo, indicando el padre \attention Función sobrecargada \param q de tipo Nodo pasado como puntero constante \param padre puntero constante \pre El Nodo q debe existir \post Ninguna \sa Nodo() */ inline Nodo(Nodo const * q, Nodo <T> const * padre) { setDato(q->getDato()); setPadre(padre); setArbol(padre->getArbol()); setClave(_root->getID()); _root->addID(); _root->addHijosTotales(); setVectorHijos(q->getVectorHijos()); } /*! \brief Constructor de "copia" que crea un Nodo a partir de otro Nodo, indicando el arbol \attention Función sobrecargada \param q de tipo Nodo pasado como puntero constante \param root puntero de tipo arbol \pre El Nodo q debe existir \post Ninguna \sa Nodo() */ inline Nodo(Nodo const * q, Arbol<T> * root) { setDato(q->getDato()); setPadre(NULL); setArbol(root); setClave(_root->getID()); _root->addID(); _root->addHijosTotales(); setVectorHijos(q->getVectorHijos()); } //! \name Destructor de la clase Nodo /*! \brief Destructor que elimina el Nodo recursivamente llamando a su vez al destructor de sus hijos \param q de tipo Nodo pasado como puntero constante \post Ninguna \sa pullHijosTotales(), podarNodo() */ inline ~Nodo() { _root->pullHijosTotales(); podarNodo(); } //! \name Funciones de consulta de Nodo /*! \brief Devuelve la referencia constante del dato que contiene un Nodo \return referencia constante a la componente "dato" del Nodo (tipo T) \pre El Nodo debe existir \post Ninguna */ inline T const & getDato()const { return _dato; } /*! \brief Devuelve la referencia del dato que contiene un Nodo \return referencia a la componente "dato" del Nodo (tipo T) \pre El Nodo debe existir \post Ninguna */ inline T & getDato() { return _dato; } /*! \brief Devuelve el puntero constante del padre de un Nodo \return puntero constante a la componente "padre" del Nodo \pre El Nodo debe existir \post Ninguna */ inline Nodo <T> const * getPadre()const { return _padre; } /*! \brief Devuelve el puntero del padre de un Nodo \return puntero a la componente "padre" del Nodo \pre El Nodo debe existir \post Ninguna */ inline Nodo <T> * getPadre() { return _padre; } /*! \brief Devuelve el numero de hijos de un Nodo \return el numero de hijos del Nodo \pre El Nodo debe existir \post Ninguna */ inline int getNumeroHijos()const { return _hijo.size(); } /*! \brief Devuelve el puntero de un Nodo hijo \return puntero a Nodo \param pos de tipo int indica la posición del hijo dentro del vector de hijos \pre El Nodo debe existir \post Ninguna */ inline Nodo <T> * getPunteroHijo(int pos){ return _hijo[pos]; } /*! \brief Devuelve la referencia constante del vector de Hijos Nodo \return el vector de hijos del Nodo \pre El Nodo debe existir \post Ninguna */ inline std::vector <Nodo <T> *> const & getVectorHijos()const { return _hijo; } /*! \brief Devuelve la referencia constante del dato que contiene un NodoArbol \return referencia constante a la componente "dato" del NodoArbol (tipo T) \pre El NodoArbol debe existir \post Ninguna */ inline int const & getClave()const { return _clave; } /*! \brief Devuelve la referencia constante del dato que contiene un NodoArbol \return referencia constante a la componente "dato" del NodoArbol (tipo T) \pre El NodoArbol debe existir \post Ninguna */ inline Arbol<T> const * getArbol()const { return _root; } //! \name Funciones de modificación de Nodo /*! \brief Asigna un valor "v" al "dato" de un Nodo \param v referencia constante de tipo T \pre El Nodo debe existir \post Ninguna */ inline void setDato(T const & v) { _dato = v; } /*! \brief Asigna un valor "v" a "padre" de un Nodo \param v puntero constante de tipo T \pre El Nodo debe existir \post Ninguna */ inline void setPadre( Nodo <T> const * v) { _padre = const_cast<Nodo <T> *> (v); } /*! \brief Asigna un valor "v" al numero de elementos del vector "hijo" de un Nodo \param v entero constante \pre El Nodo debe existir \post Ninguna */ inline void setNumeroHijos( int v) { _hijo.resize(v,NULL); } /*! \brief Replica el vector de Nodos en el del Nodo \param hijo referencia constante a un vector de punteros de nodos \pre El Nodo debe existir \post Ninguna \sa setNumeroHijos(), getNumeroHijos() */ inline void setVectorHijos( std::vector <Nodo <T> *> const & hijo ) { int i; setNumeroHijos(hijo.size()); for(i=0;i<getNumeroHijos();i++){ _hijo[i]=new Nodo(hijo[i],this); } } /*! \brief Asigna un valor "v" a la "clave" de un Nodo \param v referencia constante de tipo int \pre El NodoArbol debe existir \post Ninguna */ inline void setClave(int const & v) { _clave = v; } /*! \brief Asigna un nuevo arbol "v" al arbol del nodo \param v puntero constante de tipo arbol \pre El nodo debe existir \post Ninguna */ inline void setArbol(Arbol<T> const * v) { _root = const_cast <Arbol<T> *>(v); } /*! \brief Añade un hijo al Nodo y le asigna el valor "v", se añade al final del vector de hijos \param v constante de tipo T que es el valor que tendrá el hijo \pre El Nodo debe existir \post Ninguna \sa setNumeroHijos(), getNumeroHijos() */ inline void addHijo( T const & v) { Nodo <T> * aux = new Nodo <T>(v, this); setNumeroHijos(getNumeroHijos()+1); _hijo[getNumeroHijos()-1]=aux; //coloca en nuevo nodo hijo al final del vector de hijos } /*! \brief Inserta en la posicion "pos" a un hijo y le asigna el valor "v", por defecto se inserta al principio del vector \param v T referencia constante \param pos entero constante, por defecto 0 \pre El Nodo debe existir \post Ninguna */ inline void putHijo( T const & v, int pos=0){ Nodo <T> * aux = new Nodo <T>(v, this); _hijo.insert(_hijo.begin()+pos,aux); } /*! \brief Elimina a un hijo del Nodo, por defecto se borra el primer hijo \param v int, posición dentro del vector de hijos, por defecto 0 \pre El Nodo debe existir \post Disminuye en uno el numero de hijos \sa */ inline void delHijo( int pos=0 ) { delete _hijo[pos]; _hijo.erase(_hijo.begin()+pos); //además de eliminar la posición indicada, disminuye en uno el numero de elementos del vector } /*! \brief Elimina a todos los hijos de un Nodo \pre El Nodo debe existir \post Ninguna \sa getNumeroHijos(), delHijo() */ inline void podarNodo(){ while(getNumeroHijos()){ delHijo();//elimina el primer hijo por defecto } } }; // Fin de la definición de la clase Nodo } // \brief Fin de namespace IA. // _NODO_HPP_ #endif
arbol.hpp
/*! \par Fichero: arbol.hpp Arbol representa la clase arbol definida mediante template (plantilla) */ #ifndef _ARBOL_HPP_ #define _ARBOL_HPP_ // Facilita la entrada y salida #include <iostream> // Utilizamso el contenedor Vector STL #include <vector> namespace IA { template < class T > class Nodo; //! Definición de la plantilla de la clase Arbol template < class T > class Arbol { //! \name Atributos privados de la clase Arbol private: Nodo <T> * _raiz; //!< Puntero al nodo raiz Nodo <T> * _cursor; //!< Puntero al nodo cursor int _clave; //!< Ultimo numero dado como ID unica dentro del arbol int _hijosTotales; //!< Numero de hijos dentro del arbol //! \name Funciones o métodos públicos de la clase Arbol public: //! \name Constructores de la clase Arbol /*! \brief Constructor que crea un Arbol \attention Función sobrecargada \pre Ninguna \post Ninguna \sa setCursor(), setRaiz() */ Arbol() { setCursor(NULL); setRaiz(NULL); _clave=0; _hijosTotales=0; } /*! \brief Constructor de "copia" que crea un Arbol a partir de otro Arbol \attention Función sobrecargada \param q de tipo Arbol pasado como referencia constante \pre El Arbol q debe existir \post Ninguna \sa setRaiz(), getRaiz(), setCursor() */ Arbol(Arbol<T> const & q ) { _clave=0; _hijosTotales=0; setRaiz(new Nodo<T>(q.getRaiz(),this)); setCursor(getRaiz()); } /*! \brief Constructor de "copia" que crea un Arbol a partir de otro Arbol \attention Función sobrecargada \param q de tipo Arbol pasado como puntero constante \pre El Arbol q debe existir \post Ninguna \sa setRaiz(), getRaiz(), setCursor() */ Arbol(Arbol<T> const * q ) { _clave=0; _hijosTotales=0; setRaiz(new Nodo<T>(q->getRaiz(),this)); setCursor(getRaiz()); } //! \name Destructor de la clase Arbol /*! \brief Destructor que elimina el Arbol recursivamente llamando a su vez al destructor de sus hijos \param q de tipo Arbol pasado como puntero constante \post Ninguna \sa setCursor(), getRaiz(), podarRama() */ ~Arbol() { setCursor(getRaiz()); podarRama(); } //! \name Funciones de consulta de Arbol /*! \brief Devuelve la referencia constante de la clave del ultimo nodo insertado \return referencia constante a _clave de tipo int \pre Ninguna \post Ninguna \sa */ inline const int & getID() const { return _clave; } /*! \brief Devuelve la referencia constante del numero de hijos totales del arbol \return referencia constante a _hijosTotales de tipo int \pre Ninguna \post Ninguna \sa */ inline const int & getHijosTotales()const { return _hijosTotales; } /*! \brief Devuelve la referencia del numero de hijos totales del arbol \return referencia a _hijosTotales de tipo int \pre Ninguna \post Ninguna \sa */ inline int & getHijosTotales() { return _hijosTotales; } /*! \brief Devuelve el numero de hijos del nodo en el que este situado el cursor. Si el cursor esta a NULL devuelve el numero de hijos de la raiz y pone el cursor a la raiz \return tamaño del vector _hijo \pre Ninguna \post Ninguna \sa getRaiz(), getCursor(), getNumeroHijos() */ inline int getNumeroHijos() { if(getRaiz()&&getCursor()) return getCursor()->getNumeroHijos(); else if(getRaiz()) { setCursor(getRaiz()); return getCursor()->getNumeroHijos(); } return 0; } /*! \brief Devuelve la referencia constante del dato que contiene el cursor o en su defecto la raiz \return referencia constante de tipo T a la componente "dato" del Nodo apuntado por el cursor o por la raiz \pre Ninguna \post Ninguna \sa getCursor(), getRaiz(), getDato() */ inline T const & getDato()const { if(getCursor()&&getRaiz()) return getCursor()->getDato(); else if(getRaiz()){ return getRaiz()->getDato(); } } /*! \brief Devuelve la referencia del dato que contiene el cursor o en su defecto la raiz \return referencia de tipo T a la componente "dato" del Nodo apuntado por el cursor o por la raiz \pre Ninguna \post Ninguna \sa getCursor(), getRaiz(), getDato() */ inline T & getDato() { if(getCursor()&&getRaiz()) return getCursor()->getDato(); else if(getRaiz()){ setCursor(getRaiz()); return getCursor()->getDato(); } } /*! \brief Devuelve la referencia constante del dato del hijo del nodo que es apuntado por cursor o por la raiz si el cursor esta a NULL \return referencia constante de tipo T a la componente "dato" del hijo del Nodo apuntado por el cursor o por la raiz \pre Ninguna \post Ninguna \sa getCursor(), getRaiz(), getPunteroHijo(), getDato() */ inline T const & getDatoHijo(int pos)const { if(getCursor()&&getRaiz()) return getCursor()->getPunteroHijo(pos)->getDato(); else if(getRaiz()){ return getRaiz()->getPunteroHijo(pos)->getDato(); } } /*! \brief Devuelve la referencia del dato del hijo del nodo que es apuntado por cursor o por la raiz si el cursor esta a NULL \return referencia de tipo T a la componente "dato" del hijo del Nodo apuntado por el cursor o por la raiz \pre Ninguna \post Ninguna \sa getCursor(), getPunteroHijo(), getDato() */ inline T & getDatoHijo(int pos) { if(getCursor()&&getRaiz()) return getCursor()->getPunteroHijo(pos)->getDato(); else if(getRaiz()){ setCursor(getRaiz()); return getCursor()->getPunteroHijo(pos)->getDato(); } } /*! \brief Devuelve la referencia constante a la clave del nodo apuntado por el cursor o en su defecto la raiz \return referencia constante de tipo T a la clave del nodo \pre Ninguna \post Ninguna \sa getCursor(), getClave() */ inline int const & getClave()const { if(getCursor()&&getRaiz()) return getCursor()->getClave(); else if(getRaiz()){ return getRaiz()->getClave(); } } /*! \brief Devuelve la referencia a la clave del nodo apuntado por el cursor o en su defecto la raiz. Ademas, si el cursor está a NULL, lo pone a apuntando a la raiz \return referencia de tipo T a la clave del nodo \pre Ninguna \post Ninguna \sa getCursor(), getClave() */ inline int & getClave() { if(getCursor()&&getRaiz()) return getCursor()->getClave(); else if(getRaiz()){ setCursor(getRaiz()); return getCursor()->getClave(); } } /*! \brief Devuelve el puntero del cursor de manera constante \return _cursor de tipo Nodo <T> const * \pre Ninguna \post Ninguna \sa */ inline Nodo <T> const * getCursor()const { return _cursor; } /*! \brief Devuelve el puntero del cursor \return _cursor de tipo Nodo <T> * \pre Ninguna \post Ninguna \sa */ inline Nodo <T> * getCursor() { return _cursor; } /*! \brief Devuelve el puntero de la raiz de manera constante \return _raiz de tipo Nodo <T> const * \pre Ninguna \post Ninguna \sa */ inline Nodo <T> const * getRaiz()const { return _raiz; } /*! \brief Devuelve el puntero de la raiz \return _raiz de tipo Nodo <T> const \pre Ninguna \post Ninguna \sa */ inline Nodo <T> * getRaiz() { return _raiz; } //! \name Funciones de modificación de Nodo /*! \brief Asigna un valor "v" al "dato" del Nodo apuntado por cursor, o si este está a NULL al de la raiz \param v referencia constante de tipo T \pre Ninguna \post Ninguna \sa getCursor(), getRaiz(), setDato() */ inline void setDato(T const & v) { if(getCursor()&&getRaiz()) getCursor()->setDato(v); else if(getRaiz()){ setCursor(getRaiz()); getCursor()->setDato(v); } } /*! \brief Asigna un valor "v" al "dato" del hijo numero "pos" del nodo apuntado por el cursor o por la raiz si el cursor está a NULL \param v referencia constante de tipo T, pos tipo int \pre Ninguna \post Ninguna \sa getCursor(), getRaiz(), getPunteroHijo(), setDato() */ inline void setDatoHijo(T const & v, int pos) { if(getCursor()&&getRaiz()) getCursor()->getPunteroHijo(pos)->setDato(v); else if(getRaiz()){ setCursor(getRaiz()); getCursor()->getPunteroHijo(pos)->setDato(v); } } /*! \brief Asigna un valor "v" al cursor \param v puntero constante de tipo Nodo <T> \pre Ninguna \post Ninguna \sa */ inline void setCursor( Nodo <T> const * v) { _cursor = const_cast<Nodo <T> *> (v); } /*! \brief Asigna un valor "v" a la raiz \param v puntero constante de tipo Nodo <T> \pre Ninguna \post Ninguna \sa */ inline void setRaiz( Nodo <T> const * v) { _raiz = const_cast<Nodo <T> *> (v); } /*! \brief Elimina el sub-arbol del cursor, incluido este y pone el nuevo cursor apuntado al padre del nodo borrado. \pre Ninguna \post Ninguna \sa getRaiz(), getCursor(), setRaiz(), setCursor(), getPadre() */ inline void podarRama() { Nodo <T> * aux; if(getRaiz()&&getCursor()){ if(getRaiz()==getCursor()){ delete getCursor(); setRaiz(NULL); setCursor(NULL); } else{ aux=getCursor()->getPadre(); delete getCursor(); setCursor(aux); } } } /*! \brief Incrementa en uno la clave \pre Ninguna \post Ninguna \sa */ inline void addID() { _clave++; } /*! \brief Incrementa en uno el numero de hijos totales \pre Ninguna \post Ninguna \sa */ inline void addHijosTotales() { _hijosTotales++; } /*! \brief Decrementa en uno el numero de hijos totales \pre Ninguna \post Ninguna \sa */ inline void pullHijosTotales() { _hijosTotales--; } /*! \brief Añade un hijo al Nodo apuntado por cursor (si no está a NULL), o a la raiz (si existe), o por el contrario crea la raiz y le asigna el valor "dato". Siempre se añade al final del vector de hijos \param dato constante de tipo T que es el valor que tendrá el hijo \pre Ninguna \post Ninguna \sa getRaiz(), getCursor(), addHijo(), setRaiz(), setCursor */ void addHijo(T const & dato) { if(getRaiz()&&getCursor()){ getCursor()->addHijo(dato); } else if(getRaiz()){ setCursor(getRaiz()); getCursor()->addHijo(dato); } else{ setRaiz(new Nodo<T>(dato,this)); setCursor(getRaiz()); } } /*! \brief Inserta un hijo al Nodo apuntado por el cursor en la posicion "pos" del vector de hijos y le asigna el valor "v", por defecto se inserta al principio del vector. Si el cursor estuviese a NULL se lo inserta a la raiz, y si esta tambien estuviera a NULL, crea la raiz y le añade el hijo \param dato de tipo T referencia constante \param pos entero constante, por defecto 0 \pre Ninguna \post Ninguna \sa getRaiz(), getCursor(), putHijo(), setCursor(), setRaiz() */ void putHijo(T const & dato, int pos=0) { if(getRaiz()&&getCursor()){ getCursor()->putHijo(dato,pos); } else if(getRaiz()){ setCursor(getRaiz()); getCursor()->putHijo(dato,pos); } else{ setRaiz(new Nodo<T>(dato,this)); setCursor(getRaiz()); } } /*! \brief Elimina el hijo del Nodo apuntado por el cursor que ocupa la posicion "pos" en el vector de hijos, por defecto se borra el primer hijo. Si el cursor está a NULL, lo hace con respecto a la raiz \param int pos, por defecto a cero \pre Ninguna \post Disminuye en uno el numero de hijos \sa getRaiz(), getCursor(), delHijo(),setCursor() */ void delHijo(int pos=0) { if(getRaiz()&&getCursor()) getCursor()->delHijo(pos); else if(getRaiz()){ setCursor(getRaiz()); getCursor()->delHijo(pos); } } /*! \brief Sube el cursor un nodo hacia arriba, es decir, el nuevo nodo es el padre del antiguo cursor. \pre Ningua \post Ninguna \sa getCursor(), setCursor(), getPadre() */ void subiraPadre(){ if(getCursor()) setCursor(getCursor()->getPadre()); } /*! \brief Baja el cursor al hijo del nodo apuntado por el cursor que ocupa la posicion "pos" en el vector de hijos \pre Ningua \post Ninguna \sa getCursor(), setCursor(), getPunteroHijo() */ void bajaraHijo(int pos){ if(getCursor()) setCursor(getCursor()->getPunteroHijo(pos)); } /*! \brief Coloca el cursor en la raiz \pre Ningua \post Ninguna \sa getRaiz(), setCursor() */ void subiraRaiz(){ setCursor(getRaiz()); } class iterator{ //! \name Atributos privados de la clase iterator private: Arbol <T> & _arbol; //!< Referencia a un arbol //! \name Atributos protegidos de la clase iterator protected: std::vector<typeof(Nodo <T> *)> _frontera; //!< Vector de punteros a nodo, que guarda los que se encuentran en frontera std::vector<typeof(Nodo <T> *)> _explorados; //!< Vector de punteros a nodo, que guarda los que se han explorado //! \name Funciones o métodos públicos de la clase iterator public: //! \name Constructores de la clase iterator /*! \brief Constructor del iterador \attention Función sobrecargada \param x referencia a un arbol \pre Ninguna \post Ninguna */ iterator(Arbol <T> & x): _arbol(x) //inicializa el arbol con el arbol x pasado como argumento { _explorados.clear(); _frontera.clear(); _frontera.resize(1,_arbol.getRaiz());//aumenta a 1 el tamaño del vector frontera, y rellena este contenido con el nodo raiz } /*! \brief Constructor de copia del iterador \attention Función sobrecargada \param it referencia constante del iterador a copiar \pre Ninguna \post Ninguna */ iterator(const iterator& it) : _arbol(it._arbol), _frontera(it._frontera), _explorados(it._explorados){} //! \name Destructor de la clase iterator /*! \brief Destructor que elimina el Iterador \post Ninguna */ ~iterator() { _frontera.clear(); _explorados.clear(); } /*! \brief Método de sobrecarga del metodo virtual puro ++ \attention Función sobrecargada \pre Ninguna \post Ninguna */ virtual iterator & operator++()=0; /*! \brief Sobrecarga del operador *, devuelve el dato del primer nodo del vector frontera \attention Función sobrecargada \pre que haya algún nodo en frontera \post Ninguna */ T const & operator*() { return _frontera[0]->getDato(); } /*! \brief Coloca el cursor del arbol en el primer nodo que haya en frontera \pre que exista en arbol y que haya algún nodo en frontera \post Ninguna \sa setCursor() */ void irA() { if(_frontera.size()) _arbol.setCursor(_frontera[0]); } /*! \brief Obtiene el número de nodos que hay en frontera \pre que exista en arbol y que haya algún nodo en frontera \post Ninguna */ int getElementosFrontera() { return _frontera.size(); } };//Fin de la clase iterator class profundidad: public Arbol<T>::iterator { //! \name Funciones o métodos públicos de la clase profundidad public: //! \name Constructores de la clase profundidad /*! \brief Constructor de profundidad \attention Función sobrecargada \param x referencia a un arbol \pre Ninguna \post Ninguna \sa iterator() */ profundidad(Arbol <T> & x):iterator(x){ } //genera un iterador basado en el arbol pasado como argumento /*! \brief Constructor de copia de profundidad \attention Función sobrecargada \param it referencia constante del iterador a copiar \pre Ninguna \post Ninguna \sa iterator() */ profundidad(const profundidad& it):iterator(it){} /*! \brief sobrecarga del operador ++ del iterador \attention Función sobrecargada \pre Ninguna \post Ninguna \sa getVectorHijos(), */ iterator & operator++() { std::vector <Nodo <T> *> aux = iterator::_frontera[0]->getVectorHijos(); //guarda en aux el vector de hijos del primer nodo de frontera iterator::_explorados.resize(iterator::_explorados.size()+1,iterator::_frontera[0]);//aumenta en uno el vector explorador iterator::_frontera.erase(iterator::_frontera.begin()); //elimina del vector frontera el primer nodo if(aux.size()) { for(int x=0;x<aux.size();x++) { iterator::_frontera.insert(iterator::_frontera.begin(),aux[aux.size()-1-x]);//se añaden al principio de frontera los nodos del vector aux empezando por el final /* Ejemplo Clarificador fronteraInicial=[1,5,8] aux=[2,7,9,0] frontera1=[0,1,5,8] frontera2=[9,0,1,5,8] frontera3=[7,9,0,1,5,8] frontera4=[2,7,9,0,1,5,8] fronteraFinal=[2,7,9,0,1,5,8] */ } } return *this; } };//Fin de la clase profundidad class amplitud: public Arbol<T>::iterator { //! \name Funciones o métodos públicos de la clase amplitud public: //! \name Constructores de la clase profundidad /*! \brief Constructor de amplitud \attention Función sobrecargada \param x referencia a un arbol \pre Ninguna \post Ninguna \sa iterator() */ amplitud(Arbol <T> & x):iterator(x){ } /*! \brief Constructor de copia de amplitud \attention Función sobrecargada \param it referencia constante del iterador a copiar \pre Ninguna \post Ninguna \sa iterator() */ amplitud(const amplitud& it):iterator(it){} /*! \brief sobrecarga del operador ++ del iterador \attention Función sobrecargada \pre Ninguna \post Ninguna \sa getVectorHijos(), */ iterator & operator++() { std::vector <Nodo <T> *> aux = iterator::_frontera[0]->getVectorHijos(); //guarda en aux el vector de hijos del primer nodo de frontera iterator::_explorados.resize(iterator::_explorados.size()+1,iterator::_frontera[0]); //aumenta en uno el vector explorador iterator::_frontera.erase(iterator::_frontera.begin()); //elimina del vector frontera el primer nodo if(aux.size()) { for(int x=0;x<aux.size();x++) { iterator::_frontera.insert(iterator::_frontera.end(),aux[x]);//añade al final de frontera los nodos del vector aux } } return *this; } };//Fin de la clase amplitud }; // Fin de la definición de la clase Arbol } // \brief Fin de namespace IA. // _ARBOL_HPP_ #endif #include "nodo.hpp"
sudoku.hpp
/*! \par Fichero: sudoku.hpp Clase Sudoku */ #ifndef __SUDOKU_HPP__ #define __SUDOKU_HPP__ #include <vector> #include <iostream> #include <algorithm> //! Definición de la clase Sudoku class Sudoku{ //! \name Atributos privados de la clase Sudoku private: std::vector <typeof(std::vector <int>)> _matriz; //!< Matriz que representa el sudoku struct Casilla { //!< Almacena las coordenadas de una casilla del sudoku int x; int y; }; //! \name Funciones o métodos públicos de la clase Nodo public: struct CasPos { //Estructura formada por una casilla y por un vector de posibilidades Casilla cas; std::vector <int> Posibilidades; static bool compara (CasPos i,CasPos j) { return ((i.Posibilidades).size())<((j.Posibilidades).size()); } }; //! \name Constructores de la clase Sudoku /*! \brief Constructor que crea un Sudoku inicializando todas sus casillas a cero \attention Función sobrecargada \pre Ninguna \post Ninguna */ Sudoku(){ _matriz.resize(9); for(int x=0;x<9;x++){ _matriz[x].resize(9); for(int y=0;y<9;y++){ _matriz[x][y]=0; } } } /*! \brief Constructor de "copia" que crea un Sudoku a partir de otro \attention Función sobrecargada \param Una matriz de 9 por 9 \pre Ninguna \post Ninguna */ Sudoku(int matriz[9][9]){ _matriz.resize(9); for(int x=0;x<9;x++){ _matriz[x].resize(9); for(int y=0;y<9;y++){ _matriz[x][y]=matriz[x][y]; } } } //! \name Destructor de la clase Nodo /*! \brief Destructor que elimina el Sudoku \post Ninguna */ ~Sudoku(){ for(int x=0;x<9;x++) _matriz[x].resize(0); _matriz.resize(0); } /*! \brief Funcion que indica si el sudoku está resuelto \return Devuelve true si no hay casillas vacias y si el sudoku tiene posibilidades \pre Ninguna \post Ninguna \sa CasillasVacias(), EsCoherente() */ bool EstaResuelto() const{ return CasillasVacias().size()==0&&EsCoherente(); } /*! \brief Rellena un vector de estructuras Casilla con las coordenadas de aquellas casillas que estan vacias \return vector de estructuras Casilla \pre Ninguna \post Ninguna */ std::vector <Casilla> CasillasVacias() const{ Casilla aux; std::vector <Casilla> casillas; casillas.resize(0); for(int x=0;x<9;x++){ for(int y=0;y<9;y++){ if(_matriz[x][y]==0){ aux.x=x; aux.y=y; casillas.resize(casillas.size()+1,aux); } } } return casillas; } /*! \brief Esta funcion comprueba si se puede poner un numero en una casilla \return Devuelve true si se puede poner, false si no. \param coordenada x, coordenada y, y el numero \pre Ninguna \post Ninguna \sa EsFCol(), EsFFil(),EsFCua() */ bool EsFactible(int x, int y, int num)const{ return EsFCol(y,num)&&EsFFil(x,num)&&EsFCua(x,y,num); } /*! \brief Comprueba si el numero pasado por argumento se puede colocar en la columna indicada revisando toda la columna \return Si no se encuentra el numero en la columna devuelve true, si lo encuentra false \param coordenada y de la columna y el numero que se quiere comprobar si es posible poner en esa columna \pre Ninguna \post Ninguna */ bool EsFCol(int y,int num)const { for(int x=0;x<9;x++) if(_matriz[x][y]==num) { return false; } return true; } /*! \brief Comprueba si el numero pasado por argumento se puede colocar en la fila indicada revisando toda la fila \return Si no se encuentra el numero en la fila devuelve true, si lo encuentra false \param coordenada x de la fila y el numero que se quiere comprobar si es posible poner en esa fila \pre Ninguna \post Ninguna */ bool EsFFil(int x,int num)const { for(int y=0;y<9;y++) if(_matriz[x][y]==num) { return false; } return true; } /*! \brief Comprueba si un numero se puede poner en el cuadrado de 3 por 3 que le corresponde segun sus coordenadas, tambien pasadas a la funcion \return Si el numero se puede poner devuelve true, en caso contrario false \param numero de tipo int, coordenada x de tipo int, coordenada y de tipo int \pre Ninguna \post Ninguna */ bool EsFCua(int x, int y,int num)const{ int aumentox=(x/3)*3; int aumentoy=(y/3)*3; for(x=0;x<9;x++) if(_matriz[aumentox+x/3][aumentoy+x%3]==num) { return false; } return true; } /*! \brief General un vector de números posibles para cada casilla vacia, y todos estos se guardan en un vector \pre Ninguna \post Ninguna \sa CasillasVacias(), Posibilidades(), sort() */ std::vector <CasPos> VectorPosibilidades() const { std::vector<Casilla> vectorVacias = CasillasVacias();//vector con todas las coordenadas de las casillas vacias std::vector <CasPos> vectorPosibles ; CasPos aux; vectorPosibles.resize(0); for(int x=0;x<vectorVacias.size();x++) { aux.cas=vectorVacias[x];//va guardando en aux las coordenadas de cada casillas vacia aux.Posibilidades=Posibilidades(vectorVacias[x]);//guarda en aux los posibles valores que puede tomar esa casilla vectorPosibles.resize(vectorPosibles.size()+1,aux); } //Actualmente tenemos en vectorPosibles, un elemento CasPos por cada casilla vacia, y cada elmento CasPos tiene un vector de posibles valores que puede tomar esa casilla sort(vectorPosibles.begin(),vectorPosibles.end(),CasPos::compara);//Se ordena el vectorPosibles, dejando en primer lugar las casillas actualmente vacias que tengan menos elementos posibles (más seguro acertar) return vectorPosibles; } /*! \brief Aplica el cambio en el sudoku a la casilla con menor número de posibilidades, es decir la más probable en acierto. \pre Ninguna \post Ninguna \sa VectorPosibilidades(), setNum() */ void Aplicar(int x){ CasPos casilla=VectorPosibilidades()[0];//casilla toma el valor de la CasPos con menor número de posibilidades SetNum(casilla.cas.x,casilla.cas.y,casilla.Posibilidades[x]); } /*! \brief Obtiene el número de posibilidades de la casilla que menos posibilidades tiene \pre Ninguna \post Ninguna \sa VectorPosibilidades() */ int getPosibilidades(){ return VectorPosibilidades()[0].Posibilidades.size(); } /*! \brief Devuelve un vector con los posibles número que pueden ir en la casilla dada, cumpliendo las normal del sudoku \param casilla de tipo Casilla, es una casilla con coordenadas X e Y dentro de la matriz del soduku \pre Ninguna \post Ninguna \sa esFactible() */ std::vector <int> Posibilidades(Casilla casilla)const { std::vector <int> aux; aux.resize(0); for(int num=1;num<10;num++){ if(EsFactible(casilla.x,casilla.y,num)) aux.resize(aux.size()+1,num);//si es factible aumenta en uno el tamaño del vector de posibilidades, y añade el número como posibilidad } return aux; } /*! \brief Comprueba que el sudoku resultado cumple todas las normas, para ello comprueba que ninguna casilla tenga otra posibilidad \pre Ninguna \post Ninguna \sa VectorPosibilidades() */ bool EsCoherente()const { std::vector <CasPos> pos= VectorPosibilidades(); for(int x=0;x<pos.size();x++){ if((pos[x].Posibilidades).size()==0) return false; } return true; } /*! \brief escribe el número pasado, en la casilla indicada por sus coordenadas \param x de tipo int, coordenada x de la matriz sudoku \param y de tipo int, coordenada y de la matriz sudoku \param num de tipo int, numero que se escribiría en la matriz de sudoku \pre que la matriz exista \post Ninguna */ void SetNum(int x, int y, int num) { _matriz[x][y]=num; } /*! \brief Obtiene un número de una casilla dadas sus coordenadas \param x de tipo int, coordenada x de la matriz sudoku \param y de tipo int, coordenada y de la matriz sudoku \pre Ninguna \post Ninguna */ int GetNum(int x, int y) { return _matriz[x][y]; } /*! \brief Sobrecarga del operador de asignación, copia elemento a elemento la matriz del sudoku \attention Función sobrecargada \param p referencia cosntante de tipo sudoku \pre Ninguna \post Ninguna */ Sudoku & operator = (const Sudoku &p) { for(int x=0;x<9;x++) { for(int y=0;y<9;y++) { _matriz[x][y]=p._matriz[x][y]; } } } /*! \brief Sobrecarga del operador de comparación, devuelve verdadero o falso si dos sudokus son iguales o no \attention Función sobrecargada \param p referencia cosntante de tipo sudoku \pre Ninguna \post Ninguna */ bool operator == (const Sudoku &p) { for(int x=0;x<9;x++) { for(int y=0;y<9;y++) { if(_matriz[x][y]!=p._matriz[x][y]) return false; } } return true; } /*! \brief Sobrecarga del operador de salida \attention Función sobrecargada, función amiga \param o referencia al flujo de salida por pantalla \param p referencia cosntante de tipo sudoku \pre Ninguna \post Ninguna */ friend std::ostream& operator << (std::ostream &o,const Sudoku &p); };// Fin de la definición de la clase Sudoku /*! \brief Imprimir por pantalla el sudoku \attention Función sobrecargada \param o referencia al flujo de salida por pantalla \param p referencia cosntante de tipo sudoku \pre Ninguna \post Ninguna */ std::ostream& operator << (std::ostream &o,const Sudoku &p) { o<<"\n\n|-|-|-|-SUDOKU-|-|-|-|\n"; for(int x=0;x<9;x++) { if(x%3==0) o<<"\n "; for(int y=0;y<9;y++) { if(y%3==0) o<<" "; o<<p._matriz[x][y]<<" "; } o<<"\n "; } o<<"\n\n"; return o; } #endif
main.hpp
#include "arbol.hpp" #include "sudoku.hpp" #include <iostream> #include <ctime> #include <cstdlib> #include <fstream> using namespace std; using namespace IA; #define BORRAR cout << "\33[2J" Sudoku leerSudoku(); void pausa(); int main() { Arbol <Sudoku> * arbol=new Arbol <Sudoku>; /* Sudoku de prueba int matriz[9][9]= { {0,0,0,2,7,0,6,0,0}, {5,0,0,0,0,8,0,0,4}, {0,6,0,0,0,9,5,0,0}, {0,0,0,7,0,0,0,0,1}, {7,8,0,0,9,0,0,4,2}, {3,0,0,0,0,6,0,0,0}, {0,0,8,1,0,0,0,5,0}, {6,0,0,9,0,0,0,0,3}, {0,0,4,0,2,3,0,0,0}, }; Sudoku aux(matriz); */ //Lectura del fichero system("clear"); Sudoku aux=leerSudoku(); arbol->addHijo(aux); Arbol<Sudoku>::iterator & it = *(new Arbol<Sudoku>::profundidad(*arbol)); for(int y=0;it.getElementosFrontera()&&!((*it).EstaResuelto());y++)//desde y=0 mientras que en frontera haya algún elmento y este el nodo no esté resuelto { cout<<endl<<y+1<<"º Iteracion"<<endl; aux=arbol->getDato();//guarda en aux el sudoku actual apuntado por el cursor del arbol if(aux.VectorPosibilidades().size()) { //Añade a un sudoku los hijos posibles que sean coherentes, es decir que cumplan las reglas del sudoku for(int x=0;x<(arbol->getDato()).getPosibilidades();x++) { aux=arbol->getDato(); aux.Aplicar(x); if(aux.EsCoherente()) { arbol->addHijo(aux); } } } //Julio escribe esto: ++it;//Pasa al siguiente elemento en frontera y mete este en explorados cout<<(*it);//imprime por pantalla el sodoku que esta el primero en frontera(actual) it.irA();//pone el cursor del arbol en el primero en frontera(actual), asi en la siguiente iteracion se podra evaluar los hijos que generara y añadirselos con funciones de arbol cout<<"Casillas Vacias"<<endl; cout<<aux.VectorPosibilidades().size()<<endl; } system("clear"); if(aux.VectorPosibilidades().size()) { cout<<"Numero minimo de posibilidades por casilla"<<endl; cout<<aux.VectorPosibilidades()[0].Posibilidades.size()<<endl; cout<<"El Sudoku no tiene solución"<<endl; pausa(); } else{ cout<<"Sodoku Inicial"; cout<<arbol->getRaiz()->getDato(); cout<<"Sodoku Solucion"; cout<<aux; cout<<"Resuelto con "<< arbol->getHijosTotales() << " hijos totales"<<endl; pausa(); } delete ⁢ delete arbol; return 0; } Sudoku leerSudoku() { string nombreFichero; char basura; int matriz[9][9], dato; cout << "\n\n\tCargar Sudoku\n\nLos ficheros de sudokus actuales son:\n\n"; system("ls *.sdk"); cout << "\nIndique el nombre completo del sudoku que desea cargar: "; cin >> nombreFichero; cin.get(basura); ifstream ficheroEntrada; //Se usa la función c.str para leer el nombre como en C ficheroEntrada.open(nombreFichero.c_str(), ios::in); // Se comprueba que se ha abierto el fichero correctamente if (!ficheroEntrada) { cout << "Error al abrir el fichero\n"; exit(1); } for(int i=0; i<81;i++) { ficheroEntrada>> dato; matriz[i/9][i%9]=dato; } ficheroEntrada.close(); Sudoku sudoku(matriz); cout << "\n\nEl Sudoku \"" << nombreFichero <<"\" ha sido cargado con éxito:\n" << sudoku << "\n\n\tPulse una tecla para obtener la solución."<<endl; pausa(); BORRAR; return sudoku; } void pausa() { char caracter; // Se espera que pulse enter cout << "\nPulse ENTER para continuar--> "; cin.get(caracter); }
Para compilar y ejecutar el programa, basta con descargar los cuatro archivos, y guardarlos en un mismo directorio, y teclear en el terminal
g++ main.cpp -o sudoku.exe
Y para ejecutar:
./sudoku.exe
Para utilizar el programa basta con crear un fichero de texto plano (usando el bloc de notas, por ejemplo) y escribir en cada linea los 9 números que tiene el sudoku que queremos resolver, separando cada número por un espacio, y separando cada fila del sudoku por un intro. Guardad este archivo con extensión .sdk Os dejamos un archivo con un sudoku de prueba.
Os facilitamos también el programa ejecutable sudoku.exe
No hay comentarios:
Publicar un comentario