El siguiente trabajo se basa en la implementación de un método llamado connected, el cual es parte importante del programa. Esta clase deberá contar con todos los metodos necesarios para la construccion de grafos, para que así pueda funcionar con la clase test_Graph.h.

Dirección Internet en dónde está la documentación:

http://www.geocities.com/elsiecv21/Documentacion7.htm

http://www.geocities.com/arsoro1986/Tarea7.htm

Descripción del problema a resolver:

Planteo:

Un Grafo G(V,A) tiene 2 componentes principales: V, que es un conjunto de vértices, y A, el conjunto de arcos o aristas, que es un conjunto de enlaces entre los vértices (en este caso, los enlaces sí tienen dirección). Si los valores de los arcos son números y los vértices son hileras, una manera de representar el grafo es utilizar una tabla como la siguiente:

Fuente->Base(1) == 12   Medio->Fin(1) == 13   Fuera->Adentro == 13

Fuente->Medio   ==  6   Medio->Fin(2) == 23   Adentro->Fuera == 13

Fuente->Base(3) == -3   Medio->Fin(3) == -7

Base(1)->Medio == -3    Fin(1)->Destino == 1

Base(2)->Medio == 10    Fin(2)->Destino == 0

Base(3)->Medio == 20    Fin(3)->Destino == 1

             Base(1)                          Fin(1)

             /        \                            /       \

            /          \                          /         \

Fuente---------------Medio--------- Fin(2)---Destino   Fuera -- Adentro

             \          /                         \          /

              \        /                           \        /

             Base(3)                          Fin(3)

Objetivos:

El objetivo es implementar el grafo usando un diccionario std::map<> en que la llave sea una hilera (pues los vértices son hileras), y el como valor asociado use lista que almacene parejas de valores, en donde esté la hilera que identifica que identifica al vértice de destino, junto con el valor numérico asociado al vértice.

El método booleano conectado() del grafo retorna "true" si existe una secuencia de aristas que permiten ir desde un vértice hasta otro. Además, conectado() también calcula y retorna la lista de nodos que hay que visitar para llegar de un nodo a otro. Por ejemplo, conectado() debe producir la lista ( "Base(1)" , "Medio" , "Fin(2)" ) que es el camino de ir desde "Base(1)" hasta "Fin(2)" a un costo de 20==(-3+23).

Requerimientos:

· Alguna herramienta para compilar programas ya sea; DevCpp, Visual Studio, o Borland u otro.

· Doxygen; herramienta para hacer documentación.

· Alojamiento en Internet para publicar la solución.

Resolución del problema:

            Para resolver el problema es necesario implementar el método llamado ‘connected’, utilizando recursividad, el cual recorre todos los posibles caminos hasta encontrar la ruta que conecte los nodos consultados.

Abstracción:

Operaciones / métodos:

class const_iterator:

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

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

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 value_type& operator*() { return *m_it ; } ///< \c *p

const value_type* operator->() { return &(*m_it); } ///< \c p->

class Graph:

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"

/// 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 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

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);

bool connected( const std::string & src , const std::string & dst , std::list< std::string > & C );

Especificación del programa:

El programa es una serie de casos y datos de pruebas para la clase ADH_Graph.

Especificación de la clase:

La clase “ADH_Graph” contiene todos los métodos necesarios para la construcción de un grafo.

La clase “const_iterator” permite crear un iterador sobre un grafo.

Arquitectura de la clase

test_Graph.cpp

test_ Graph.obj

test_rational.exe

Implementación

Modelo de la clase:

            ADH_Graph à  const_iterator

Invariante de la clase:

            No posee invariante.

Compilador usado:

Microsoft Visual Studio 2005.

¿Cómo compilar el programa?

Abrir el archivo .test_Graph, darle click en la opción build, ahí seleccionar build test_Graph.

Guía de uso del programa

Este es un programa de prueba que realiza diversas operaciones con grafos. El programa se ejecuta automáticamente por lo que no es necesario ingresarle ningún dato.

Codigo Fuente:

Class ADH_Graph.h

#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

public:

/** Iteradores [CONST] simples para la clase \c "Graph".

- No existen iteradores "no-const" para esta clase

\dontinclude test_Graph.cpp

\skipline test::const_iterator()

\until }}

\see test_Graph::test_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 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::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"

/// 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 );

bool connected( const std::string & src , const std::string & dst , std::list< std::string > & C );

private:

Rep m_DICC; ///< Diccionario que contiene los valores del grafo

}; // Graph

} // namespace ADH

#endif // ADH_Graph_h

Class ADH_Graph.cpp

#include "ADH_Graph.h"

/** \file ADH_Graph.cpp

\brief Archivo de implementaci¢n para \c ADH_Graph.h

\author Adolfo Di Mare <[email protected]>

\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;

}

/// Graba el valor de \c "G" en el flujo \c "COUT".

std::ostream& operator<< (std::ostream &COUT, const Graph& G) {

Graph::Rep::const_iterator it = G.m_DICC.begin(); // recorre m_DICC[]

for ( ; it != G.m_DICC.end(); ++it ) {

COUT << it->first << " ==> [";

Graph::mapped_type::const_iterator jt = it->second.begin();

while ( jt != it->second.end() ) {

COUT << '<' << jt->second << '>' << jt->first ;

++jt;

if ( jt != it->second.end() ) {

COUT << " , ";

}

COUT << ']' << std::endl;

}

return COUT;

} // operator <<

/// Graba el valor de \c "G" en el flujo \c "COUT".

void dump( std::ostream & COUT, const Graph& G ) {

Graph::Rep::const_iterator it = G.m_DICC.begin();

for ( ; it != G.m_DICC.end(); ++it ) {

Graph::Rep::const_iterator jt = G.m_DICC.begin();

for ( ; jt != G.m_DICC.end(); ++jt ) {

int val = 666;

if ( G.isArc( it->first , jt->first , val ) ) {

COUT << it->first << "->" << jt->first << " == " << val << std::endl;

}

/** Determina si existe un camino en el grafo comenzando en \c "src" y terminando en \c "dst".

- Retorna \c "true" cuando el camino existe, y \c "false" en caso contrario.

- La lista \c "C" contiene la secuencia de nodos del camino.

- Si no hay camino, la lista \c "C" queda vacía.

\dontinclude test_Graph.cpp

\skipline test::diagram()

\until }}

\skipline test::connected()

\until }}

\see test_Graph::test_connected()

bool Graph::connected( const std::string & src , const std::string & dst , std::list< std::string > & C ) {

int val = 0;

bool res = false;

Graph::Rep::const_iterator it = m_DICC.find( src );

if ( it == m_DICC.end() ) {

return false;

}

else {

C.push_back(src);

for (int i = 0; i != it->second.size(); ++i ) {

std::map< std::string, int >::const_iterator jt = it->second.begin();

for ( ; jt != it->second.end(); ++jt ) {

if ( isArc(jt->first, dst, val)){

C.push_back(jt->first);

C.push_back(dst);

res = true;

return res;

}

else{

res = connected(jt->first, dst, C);

}

//++it

}

return res;

}

} // namespace ADH

Class ADH_test.h

#ifndef ADH_test_h

#define ADH_test_h ///< Evita la inclusión múltiple

#include <list> // std::list

#include <string> // class std::string

#include <sstream> // class basic_ostringstream<T,Ch>

#include <cstdio> // memcpy()+strlen()

#include <typeinfo> // class std::type_info ==> char* typeid().name();

#include <algorithm> // find()

// using namespace std;

/// Definido por la biblioteca C++ estándar.

namespace std {} // Está acá para que Doxygen lo documente

/// Escuela de Ciencias de la Computación e Informática.

/// \see http:www.ecci.ucr.ac.cr

namespace ECCI { }

/// Clase privada que contiene los datos de cada prueba no exitosa.

class TestCaseError {

const char * m_fname; ///< Nombre del archivo en donde se produjo el error.

int m_lineno; ///< Número de línea del archivo en donde se produjo el error.

const char * m_label; ///< Mensaje descriptivo del error.

bool m_destroy_label; ///< Indica si el destructor debe retornar la memoria de \c m_label.

private:

TestCaseError() :

m_fname(""), m_lineno(0), m_label(""), m_destroy_label(false)

{ } ///< Constructor por defecto.

TestCaseError(const char * fname, int line, const char * label, bool destroy )

: m_fname(fname), m_lineno(line), m_label(label), m_destroy_label(destroy)

{ } ///< Constructor.

public:

~TestCaseError() { if (m_destroy_label) { delete [] m_label; } } ///< Destructor.

TestCaseError( const TestCaseError& o ) {

m_fname = o.m_fname; m_lineno = o.m_lineno; m_label = o.m_label;

m_destroy_label = o.m_destroy_label;

const_cast<TestCaseError*>(&o)->m_destroy_label = false; // evita doble destrucción de m_label

// const_cast<bool>(o.m_destroy_label) = false; // no compila

} ///< Constructor de copia.

void operator = ( TestCaseError& o ) {

m_fname = o.m_fname; m_lineno = o.m_lineno; m_label = o.m_label;

m_destroy_label = o.m_destroy_label;

o.m_destroy_label = false; // evita doble destrucción de m_label

} ///< Copiador usado al insertar en el contenedor.

friend class TestCase; ///< Caso de prueba.

template <class TestCase> friend void do_toXML( const TestCase * tc , std::basic_ostringstream<char> & ost );

template <class TestCase> friend void do_toString( const TestCase * tc , std::basic_ostringstream<char> & ost );

}; // TestCaseError

/// Cada caso de prueba es una instancia derivada de esta clase abstracta.

/// - Siempre es obligatorio implementar \c TestCase::run().

class TestCase {

protected:

int m_pass; ///< Cantidad de pruebas exitosas

int m_error; ///< Cantidad de pruebas que han producido error

const char * m_name; ///< Nombre del caso de prueba

bool m_test_suite_destroy; ///< Indica si la prueba está en memoria dinámica.

/// Contenedor para registrar las pruebas que han producido error.

std::list<TestCaseError> m_errorList;

public:

TestCase(const char * name=0);

virtual ~TestCase() { } ///< Destructor

/// [virtual] ==> Ejecuta la prueba y retorna \c "false" si produce error.

/// [***] Siempre es necesario redefinir el método \c run().

/// \see runBare().

virtual bool run() = 0;

void runBare();

bool Run() { return run(); } ///< Sinónimo de \c run()

bool runTest() { return run(); } ///< Sinónimo de \c run()

virtual void setUp();

virtual void tearDown();

int countTestCases() const { return 1; } ///< Cantidad de casos de prueba que serán ejecutados.

/// Cantidad total de pruebas realizadas.

/// - Sinónimo de <code>successCount()+errorCount()+failureCount()</code>.

/// \see reset().

int runCount() const { return successCount()+errorCount(); }

/// Cantidad de pruebas que han producido error. \see reset().

virtual int errorCount() const { return m_error; }

/// Siempre retorna \c 0 (cero): "Cantidad de fallas".

/// - ADH_test no hace diferencia entre "errores" y "fallas"

/// \see http://osdir.com/ml/java.junit.user/2002-06/msg00114.html

int failureCount() const { return 0; }

virtual int successCount() const { return m_pass; } ///< Cantidad de pruebas exitosas. \see reset().

/// Retorna \c "true" si todas las pruebas han sido exitosas.

/// - Sinónimo de <code>(successCount() == runCount())</code>

bool wasSuccessful() const { return successCount() == runCount(); }

virtual void reset();

public:

/// Obtiene el nombre de la prueba. \see setName().

std::string getName() const;

void setName( const char * name=0 );

virtual const std::string toString() const;

virtual const std::string summary() const;

virtual const std::string toXML() const;

/// Retorna la hilera encabezado \c summary() seguido de errores \c toString().

const std::string report() const { return summary() + '\n' + toString(); }

const std::string errorString() const { return toString(); } ///< Sinónimo de \c toString()

template <class T> static std::string toString( const T & val );

protected:

void recordSuccess() { ++m_pass; } ///< Registra como exitoso el resultado de una prueba

void recordError( const char* label, const char* fname, int lineno, bool must_copy=false);

void recordError( const std::string& label, const char* fname, int lineno );

void testThis( bool cond, const std::string& label, const char* fname, long lineno);

void testThis( bool cond, const char* label, const char* fname, long lineno, bool must_copy=false);

template <class TestCase> friend void do_toXML( const TestCase * tc , std::basic_ostringstream<char> & ost );

template <class TestCase> friend void do_toString( const TestCase * tc , std::basic_ostringstream<char> & ost );

template <class TestCase> friend class TestSuite; ///< Colección de pruebas.

int nPass() const { return m_pass; } ///< Sinónimo de \c successCount() [OBSOLETO] \deprecated

int nError() const { return m_error; } ///< Sinónimo de \c errorCount() [OBSOLETO] \deprecated

private:

virtual bool iAmTestSuite() const { return false; } ///< Retorna \c false para \c TestCase.

TestCase(const TestCase&); ///< \c "private" evita la copia de casos de prueba

TestCase& operator=(const TestCase&); ///< \c "private" evita la copia de casos de prueba

friend class test_ADH_test; ///< Clase de prueba para \c ADH_test.h

}; // TestCase

/// NO IMPLEMENTADO ==> Colección de pruebas.

template <class TC> class TestSuite : public TestCase { };

/** Constructor.

- Si no se indica el nombre en \c "name", el nombre se obtiene con <code>typeid(*this).name()</code>.

\dontinclude test_ADH_test.cpp

\skipline test::constructor()

\until }}

\see test_ADH_test::test_constructor()

inline TestCase::TestCase(const char * name) :

m_pass(0), m_error(0), m_name(name), m_test_suite_destroy(false), m_errorList() { }

/** Elimina todas las pruebas realizadas.

- Anula los contadores de pruebas porque deja la clase en el estado

inicial que tuvo al ser construida.

- Borra el registro de pruebas no exitosas.

- No borra el nombre de la prueba.

\dontinclude test_ADH_test.cpp

\skipline test::reset()

\until }}

\see test_ADH_test::test_reset()

inline void TestCase::reset() {

m_pass = m_error = 0;

m_errorList.clear();

}

inline std::string TestCase::getName() const {

return ( m_name != 0 ? m_name : typeid(*this).name() );

}

/** Le cambia el nombre a la prueba.

\dontinclude test_ADH_test.cpp

\skipline test::setName()

\until }}

\see test_ADH_test::test_setName()

inline void TestCase::setName( const char * name ) {

m_name = name;

}

/** Ejecuta la prueba <code>setUp(); run(); tearDown();</code>.

- A diferencia de \c run(), este método si establece el ambiente

de prueba invocando \c setUp() y \c tearDown() antes y después

de hacer la prueba.

\dontinclude test_ADH_test.cpp

\skipline test::run()

\until }}

\see test_ADH_test::test_run()

inline void TestCase::runBare( ) { setUp(); run(); tearDown(); }

/// Establece el ambiente para la ejecución de la prueba

/// \see TestCase::setUp()

typedef TestCase TestFixture;

/** Establece el ambiente en que se realizará cada prueba.

- Como \c TestCase::run() es un método abstracto,

para facilitar la programación lo usual es que el

programador no incluya invocaciones a

\c TestCase::setUp() y \c TestCase::tearDown()

pues es más simple dejar que lo haga

\c TestSuite<TestCase>::runBare().

- A diferencia de \c TestCase::runBare(), el método

\c TestCase::run() no establece el ambiente de prueba

porque no invoca ni a \c TestCase::setUp() antes de

la prueba ni a \c TestCase::tearDown() después .

- \c TestSuite<TestCase>::runBare() invoca los métodos

\c TestCase::setUp() y \c TestCase::tearDown()

cuando ejecuta cada prueba.

- Por eso, si el programador cliente quiere que cada

prueba se ejecute luego de establecer el ambiente de

la prueba, lo más práctico es que agregue sus

pruebas a una colección de pruebas \c TestSuite para

ejecutarlas con \c TestSuite<TestCase>::runBare().

inline void TestCase::setUp() { }

/// Destruye el ambiente de prueba

inline void TestCase::tearDown() {}

/** Efectúa la prueba y registra el resultado.

- Si la prueba es exitosa sólo incrementa la cantidad de éxitos \c successCount().

- Si la prueba no tiene éxito reporta en \c toString() el hecho.

- La prueba es \c "cond".

- Los valores \c "fname" y \c "lineno" indican el archivo y el renglón

en donde se ejecuta la prueba.

- Usualmente los valores de \c "fname" y \c "lineno" se obtienen con

las macros globales \c "__FILE__" y \c "__LINE__".

- El valor \c "must_copy" indica que es necesario hacer una copia de la

hilera \c "label", copia que será destruida cuando el registro de

pruebas no exitosas sea borrado.

- En la mayor parte de los casos, la hilera \c "label" es una constante

generada por el preprocesador al usar la macro \c \#cond y por eso su

memoria no debe ser retornada.

Este método es invocado usando la macro \c ADH_test_TEST().

\dontinclude test_ADH_test.cpp

\skipline test::testThis()

\until }}

\see test_ADH_test::test_testThis()

inline void TestCase::testThis( bool cond, const char * label, const char* fname, long lineno, bool must_copy ) {

if (cond) {

recordSuccess();

}

else {

recordError( label, fname, lineno, must_copy );

}

inline void TestCase::testThis( bool cond, const std::string& label, const char* fname, long lineno ) {

testThis( cond, label.c_str(), fname, lineno, true /* must_copy == true */ );

} ///< Sinónimo de \c testThis();

/** Registra que la prueba no tuvo éxito.

- Los valores \c "fname" y \c "lineno" indican el archivo y el renglón

en donde se ejecuta la prueba.

- Usualmente los valores de \c "fname" y \c "lineno" se obtienen con

las macros globales \c "__FILE__" y \c "__LINE__".

- El valor \c "must_copy" indica que es necesario hacer una copia de la

hilera \c "label", copia que será destruida cuando el registro de

pruebas no exitosas sea borrado.

- En la mayor parte de los casos, la hilera \c "label" es una constante

generada por el preprocesador al usar la macro \c \#cond y por eso su

memoria no debe ser retornada.

Este método es invocado usando la macro \c ADH_test_ERROR().

inline void TestCase::recordError( const char* label, const char* fname, int lineno, bool must_copy ) {

if ( must_copy ) {

size_t len = strlen(label)+1;

char* str = new char[ len ]; // hace la copia del mensaje de error

memcpy( str, label, len );

label = str;

}

m_errorList.push_back( TestCaseError ( fname, lineno, label, must_copy ) );

m_error++;

}

/// Registra que la prueba no tuvo éxito.

/// - En \c ADH_test.h no se hace diferencia entre "fallas" y "errores".

inline void TestCase::recordError( const std::string& label, const char* fname, int lineno ) {

recordError( label.c_str(), fname, lineno, true /* must_copy == true */ );

/* Nota: como aquí se obtiene memoria dinámica para "str" hay que marcar

el campo "TestCase::m_destroy_label" con el valor "true" de manera

que el destructor de "TestCaseError" retorne esa memoria.

}

/** Hilera "enooorme" que contiene copia del registro de pruebas no exitosas, separados por \c "\n".

\code

=\_error: 1 == 0

=/ (125) X:\DIR\SubDir\test_ADH_test.cpp

=\_error: 4 == 0

=/ (128) X:\DIR\SubDir\test_ADH_test.cpp

\endcode

inline const std::string TestCase::toString() const {

// typedef basic_ostringstream<char> ostringstream;

std::basic_ostringstream<char> ost; // ostringstream ost;

do_toString( this , ost );

return ost.str();

}

/// Le agrega a \c ost la hilera de todas las pruebas no exitosas de \c *tc.

template <class TestCase>

void do_toString( const TestCase * tc , std::basic_ostringstream<char> & ost ) {

std::list<TestCaseError>::const_iterator it = tc->m_errorList.begin();

for ( ; it != tc->m_errorList.end(); ++it) {

ost << "=\\_error: " << it->m_label << " \n=/ ("

<< it->m_lineno << ") " << it->m_fname << "\n";

}

return;

/* NOTA

La implementación de "TestCase::toString()" está hecha invocando esta

función emplantillada para que sea el compilador el responsable de

remover versiones duplicadas de esta misma rutina, las que se producen

cuando este archivo de encabezado ("ADH_test.h") es incluido en varios

archivos "*.cpp". Todo esto hay que hacerlo para que "ADH_test.h" quepa,

completo, en un único archivo de encabezado.

}

/** Hilera XML que contiene una copia de las pruebas no exitosas.

\code

\endcode

inline const std::string TestCase::toXML() const {

// typedef basic_ostringstream<char> ostringstream;

std::basic_ostringstream<char> ost; // ostringstream ost;

do_toXML( this , ost );

return ost.str();

}

/// Le agrega a \c ost la hilera de todas las pruebas no exitosas de \c *tc en formato XML.

template <class TestCase>

void do_toXML( const TestCase * tc , std::basic_ostringstream<char> & ost ) {

std::list<TestCaseError>::const_iterator it = tc->m_errorList.begin();

for ( ; it != tc->m_errorList.end(); ++it ) {

ost << "<error file=\"" << it->m_fname

<< "\" line=\"" << it->m_lineno

<< "\" message=\"" << it->m_label << "\"/>" << std::endl;

}

return;

/* Nota:

La implementación de "TestCase::toXML()" está hecha invocando a la

función emplantillada "do_toXML()" para que el compilador se encargue

de evitar la declaración múltiple que ocurre cuando "ADH_test.h" es

incluido en varios archivos "*.cpp" diferentes en el mismo proyecto.

}

/// [ADH_test] Macros propios de \c ADH_test.h

#define TEST_ADH_test()

#undef TEST_ADH_test

/** [ADH_test] Efectúa la prueba \c "cond y registra el resultado.

- Es más elegante usar assertTrue() que hace lo mismo.

- Si la prueba \c "cond" tiene éxito invoca el método

\c TestCase::recordSuccess().

- Si la prueba \c "cond" no tiene éxito invoca el método

\c TestCase::recordError().

- Esta es una una macro que invoca el método

\c TestCase::testThis().

\dontinclude test_ADH_test.cpp

\skipline test::ADH_test_macro()

\until }}

\see test_ADH_test::test_ADH_test_macro()

#define ADH_test_TEST(cond) testThis( cond, #cond, __FILE__, __LINE__ )

/// [ADH_test] Macro similar a \c ADH_test_TEST() que usa el mensaje \c "msg".

/// - El mensaje \c "msg" debe ser una hilera literal o un objeto que pueda

/// convertirse en <code>(const char *)</code>.

#define ADH_test_TEST_Msg(msg, cond) testThis( cond, msg, __FILE__, __LINE__ )

/** [ADH_test] Registra como "error" el resultado de una prueba.

- El programador cliente es quien determinó que la prueba

no tuvo éxito y por eso quiere registrar ese hecho.

- Está implementado comun una macro que invoca

el método \c TestCase::recordError().

\see ADH_test_TEST()

\code

if (22==33) {

ADH_test_ERROR("! (22==33)"); // Registra el error

}

\endcode

#define ADH_test_ERROR(msg) recordError( msg, __FILE__, __LINE__ )

/** [ADH_test] Registra como "exitoso" el resultado de una prueba.

- El programador cliente es quien determinó que la prueba

fue exitosa y por eso quiere registrar ese hecho.

- Generalmente se usa después de atrapar una excepción que

se supone debió ser lanzada como resultado de la prueba.

- Está implementado comun una macro que invoca

el método \c TestCase::recordSuccess().

\see ADH_test_TEST()

#define ADH_test_SUCCESS() recordSuccess()

/// [ADH_test] Efectúa la prueba para determinar si <code>(expected == actual)</code>.

/// - Si la prueba tiene éxito invoca el método

/// \c TestCase::recordSuccess().

/// - Si la prueba no tiene éxito invoca el método

/// \c TestCase::recordError().

/// - Esta es una una macro que invoca el método

/// \c TestCase::testThis().

/// \see ADH_test_TEST()

#define ADH_test_EQUAL(expected, actual) \

testThis( (expected) == (actual), #expected " == " #actual, __FILE__, __LINE__ )

/// [ADH_test] Efectúa la prueba para determinar si <code>expected == actual</code>.

/// - Si la prueba tiene éxito invoca el método

/// \c TestCase::recordSuccess().

/// - Si la prueba no tiene éxito invoca el método

/// \c TestCase::recordError().

/// - Esta es una una macro que invoca el método

/// \c TestCase::testThis().

/// - Registra el mensaje \c "MSG" si la prueba no tiene éxito.

/// \see ADH_test_TEST()

#define ADH_test_EQUAL_Msg(MSG, expected, actual) \

testThis( (expected) == (actual), MSG, __FILE__, __LINE__ )

/// Retorna un hilera que contiene el nombre, cantidad de éxitos y cantidad de errores de la prueba.

inline const std::string TestCase::summary() const {

std::string res = "TestCase [" + getName() + ']';

res += " (OK: " + TestCase::toString( successCount() ) + ')';

res += " (ERROR: " + TestCase::toString( errorCount() ) + ')';

return res;

}

// ¿¿¿ TestSuite ???

//inline bool check_ok<int>( const int & ) { return true; }

//template<class unsigned> inline bool check_ok( const unsigned & ) { return true; }

//template<class int> inline bool check_ok( const long & ) { return true; }

//template<class int> inline bool check_ok( const flota & ) { return true; }

//template<class int> inline bool check_ok( const double & ) { return true; }

template <class T> bool check_ok( const T& ); ///< Declaración genérica para \c check_ok()

inline bool check_ok( const signed char & ) { return true; } ///< \c check_ok<>()==true por defecto (por si el programador no lo ha implementado)

inline bool check_ok( const unsigned char & ) { return true; } ///< \c check_ok<>()==true por defecto (por si el programador no lo ha implementado)

inline bool check_ok( const signed int & ) { return true; } ///< \c check_ok<>()==true por defecto (por si el programador no lo ha implementado)

inline bool check_ok( const unsigned int& ) { return true; } ///< \c check_ok<>()==true por defecto (por si el programador no lo ha implementado)

inline bool check_ok( const signed long & ) { return true; } ///< \c check_ok<>()==true por defecto (por si el programador no lo ha implementado)

inline bool check_ok( const unsigned long & ) { return true; } ///< \c check_ok<>()==true por defecto (por si el programador no lo ha implementado)

inline bool check_ok( const float & ) { return true; } ///< \c check_ok<>()==true por defecto (por si el programador no lo ha implementado)

inline bool check_ok( const double & ) { return true; } ///< \c check_ok<>()==true por defecto (por si el programador no lo ha implementado)

inline bool check_ok( const long double & ) { return true; } ///< \c check_ok<>()==true por defecto (por si el programador no lo ha implementado)

/// Retorna una hilera que contiene el valor de \c val.

/// - \c toString() with standard C++

template <class T>

std::string TestCase::toString( const T & val ) {

// typedef basic_ostringstream<char> ostringstream;

std::basic_ostringstream<char> temp; // ostringstream temp;

temp << val;

return temp.str( );

}

/// [CppUnit] Macros propios de \c CppUnit http://cppunit.sourceforge.net/doc/lastest

#define CPPUNIT_ADH_test()

#undef CPPUNIT_ADH_test

/// [CppUnit] Assertions that a condition is true.

/// \see http://cppunit.sourceforge.net/doc/lastest/group___assertions.html#ga0

#define CPPUNIT_ASSERT(condition) ADH_test_TEST(condition)

/// [CppUnit] Assertion with a user specified message.

/// \see http://cppunit.sourceforge.net/doc/lastest/group___assertions.html#ga1

#define CPPUNIT_ASSERT_MESSAGE(message, condition) CPPUNIT_ASSERT(condition)

/// [CppUnit] Fails with the specified message.

/// \see http://cppunit.sourceforge.net/doc/lastest/group___assertions.html#ga2

#define CPPUNIT_FAIL(message) ADH_test_ERROR(message)

/// [CppUnit] Asserts that two values are equals.

/// \see http://cppunit.sourceforge.net/doc/lastest/group___assertions.html#ga3

#define CPPUNIT_ASSERT_EQUAL(expected, actual) ADH_test_EQUAL(expected, actual)

/// [CppUnit] Asserts that two values are equals, provides additional messafe on failure.

/// \see http://cppunit.sourceforge.net/doc/lastest/group___assertions.html#ga4

#define CPPUNIT_ASSERT_EQUAL_MESSAGE(message, expected, actual) \

ADH_test_EQUAL_Msg(message, expected, actual)

/// [CppUnit] Macro for primitive value comparisons.

/// \see http://cppunit.sourceforge.net/doc/lastest/group___assertions.html#ga5

#define CPPUNIT_ASSERT_DOUBLES_EQUAL(expected, actual, delta) \

assertEquals_Delta(expected, actual, delta)

/// [CppUnit] Asserts that the given expression throws an exception of the specified type.

/// \see http://cppunit.sourceforge.net/doc/lastest/group___assertions.html#ga6

#define CPPUNIT_ASSERT_THROW(expression, ExceptionType) \

do { \

bool cpputExceptionThrown_ = false; \

try { \

expression; \

} catch ( const ExceptionType & ) { \

cpputExceptionThrown_ = true; \

} \

if ( cpputExceptionThrown_ ) { \

break; \

} \

ADH_test_ERROR( \

"Expected exception: " #ExceptionType ) \

} while ( false )

/// [CppUnit] Asserts that the given expression does not throw any exceptions.

/// \see http://cppunit.sourceforge.net/doc/lastest/group___assertions.html#ga7

#define CPPUNIT_ASSERT_NO_THROW(expression) \

do { \

try { \

expression; \

} catch ( ... ) { \

ADH_test_ERROR("Unexpected exception caught"); \

} \

} while ( false )

/// [CppUnit] Asserts that an assertion fail.

/// \see http://cppunit.sourceforge.net/doc/lastest/group___assertions.html#ga8

#define CPPUNIT_ASSERT_ASSERTION_FAIL(assertion) \

CPPUNIT_ASSERT_THROW( assertion, CPPUNIT_NS::Exception )

/// [CppUnit] Asserts that an assertion pass.

/// \see http://cppunit.sourceforge.net/doc/lastest/group___assertions.html#ga9

#define CPPUNIT_ASSERT_ASSERTION_PASS(assertion) \

CPPUNIT_ASSERT_NO_THROW( assertion )

// /// Concatena la hilera \c THIS con la hilera \c THAT

// #define ADH_test_CAT( THIS, THAT ) (std::string(THIS) + std::string(THAT).c_str())

#define JUnit_ADH_test()

#undef JUnit_ADH_test

/// [JUnit] Macros propios de \c JUnit http://junit.sourceforge.net/javadoc/junit/framework/Assert.html

/// Asserts that two objects are equal.

/// \see http://junit.sourceforge.net/javadoc/junit/framework/Assert.html#assertEquals(java.lang.Object,%20java.lang.Object)

#define assertEquals( EXPECTED, ACTUAL ) ADH_test_EQUAL(EXPECTED, ACTUAL)

/// Asserts that two objects are equal (with message).

/// \see http://junit.sourceforge.net/javadoc/junit/framework/Assert.html#assertEquals(java.lang.String,%20java.lang.Object,%20java.lang.Object)

#define assertEquals_Msg( MSG, EXPECTED, ACTUAL ) ADH_test_EQUAL_Msg(MSG, EXPECTED, ACTUAL)

/// [JUnit] Asserts that a condition is true.

/// \see http://junit.sourceforge.net/javadoc/junit/framework/Assert.html#assertTrue(boolean)

#define assertTrue( CONDITION ) testThis( CONDITION, #CONDITION, __FILE__, __LINE__ )

/// [JUnit] Asserts that a condition is true (with message).

/// \see http://junit.sourceforge.net/javadoc/junit/framework/Assert.html#assertTrue(java.lang.String,%20boolean)

#define assertTrue_Msg( MSG, CONDITION ) testThis( CONDITION, MSG, __FILE__, __LINE__ )

/// [JUnit] Asserts that a condition is false.

/// \see http://junit.sourceforge.net/javadoc/junit/framework/Assert.html#assertFalse(boolean)

#define assertFalse( CONDITION ) testThis( !(CONDITION), "!(" #CONDITION ")", __FILE__, __LINE__ )

/// [JUnit] Asserts that a condition is false (with message).

/// \see http://junit.sourceforge.net/javadoc/junit/framework/Assert.html#assertFalse(java.lang.String,%20boolean)

#define assertFalse_Msg( MSG, CONDITION ) testThis( !(CONDITION), MSG, __FILE__, __LINE__ )

#include <math.h> // fabs()

/// [JUnit] Asserts that two doubles are equal concerning a delta.

/// \see http://junit.sourceforge.net/javadoc/junit/framework/Assert.html#assertEquals(double,%20double,%20double)

#define assertEquals_Delta(EXPECTED, ACTUAL, DELTA ) \

testThis( fabs( double(EXPECTED) - double(ACTUAL) ) < double(DELTA), \

"|" #EXPECTED "-" #ACTUAL "| < " #DELTA, __FILE__, __LINE__ )

/// [JUnit] Asserts that two doubles are equal concerning a delta (with message).

/// \see http://junit.sourceforge.net/javadoc/junit/framework/Assert.html#assertEquals(java.lang.String,%20double,%20double,%20double)

#define assertEquals_Delta_Msg( MSG, EXPECTED, ACTUAL, DELTA ) \

testThis( fabs( double(EXPECTED) - double(ACTUAL) ) < double(DELTA), \

MSG, __FILE__, __LINE__ )

/// [JUnit] Asserts that an object is null.

/// \see http://junit.sourceforge.net/javadoc/junit/framework/Assert.html#assertNull(java.lang.Object)

#define assertNull(OBJECT) testThis( 0==&(OBJECT), "assertNull(" #OBJECT ")", __FILE__, __LINE__ )

/// [JUnit] Asserts that an object isn't null.

/// \see http://junit.sourceforge.net/javadoc/junit/framework/Assert.html#assertNotNull(java.lang.Object)

#define assertNotNull(OBJECT) testThis( 0!=&(OBJECT), "assertNotNull(" #OBJECT ")", __FILE__, __LINE__ )

/// [JUnit] Asserts that two objects refer to the same object.

/// \see http://junit.sourceforge.net/javadoc/junit/framework/Assert.html#assertSame(java.lang.Object,%20java.lang.Object)

#define assertSame(THIS, THAT) testThis( &(THIS)==&(THAT), "assertSame(" #THIS ", " #THAT ")", __FILE__, __LINE__ )

/// Asserts that two objects do not refer to the same object.

/// \see http://junit.sourceforge.net/javadoc/junit/framework/Assert.html#assertNotSame(java.lang.Object,%20java.lang.Object)

#define assertNotSame(THIS, THAT) testThis( &(THIS)!=&(THAT), "assertNotSame(" #THIS ", " #THAT ")", __FILE__, __LINE__ )

/// [JUnit] Fails a test with no message.

/// \see http://junit.sourceforge.net/javadoc/junit/framework/Assert.html#fail()

#define fail( ) ADH_test_ERROR("ERROR")

/// [JUnit] Fails a test with the given message.

/// \see http://junit.sourceforge.net/javadoc/junit/framework/Assert.html#fail(java.lang.String)

#define fail_Msg( MSG ) ADH_test_ERROR(MSG)

#endif // ADH_test_h

test_Graph.cpp