alpar@906: /* -*- C++ -*-
alpar@906:  * src/test/graph_test.h - Part of HUGOlib, a generic C++ optimization library
alpar@906:  *
alpar@906:  * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@906:  * (Egervary Combinatorial Optimization Research Group, EGRES).
alpar@906:  *
alpar@906:  * Permission to use, modify and distribute this software is granted
alpar@906:  * provided that this copyright notice appears in all copies. For
alpar@906:  * precise terms see the accompanying LICENSE file.
alpar@906:  *
alpar@906:  * This software is provided "AS IS" with no warranty of any kind,
alpar@906:  * express or implied, and with no claim as to its suitability for any
alpar@906:  * purpose.
alpar@906:  *
alpar@906:  */
alpar@800: #ifndef HUGO_TEST_GRAPH_TEST_H
alpar@800: #define HUGO_TEST_GRAPH_TEST_H
alpar@800: 
alpar@800: 
alpar@800: #include "test_tools.h"
alpar@800: 
alpar@800: //! \ingroup misc
alpar@800: //! \file
alpar@800: //! \brief Some utility to  test graph classes.
alpar@800: namespace hugo {
alpar@800: 
deba@891:   struct DummyType {
deba@891:     int value;
deba@891:     DummyType() {}
deba@891:     DummyType(int p) : value(p) {}
deba@891:     DummyType& operator=(int p) { value = p; return *this;}
deba@891:   };
alpar@800: 
deba@891: 
deba@891:   template<class Graph> void checkCompileStaticGraph(Graph &G) 
deba@891:     {
deba@891:       typedef typename Graph::Node Node;
deba@891:       typedef typename Graph::NodeIt NodeIt;
deba@891:       typedef typename Graph::Edge Edge;
deba@891:       typedef typename Graph::EdgeIt EdgeIt;
deba@891:       typedef typename Graph::InEdgeIt InEdgeIt;
deba@891:       typedef typename Graph::OutEdgeIt OutEdgeIt;
alpar@800:   
deba@891:       {
deba@891: 	Node i; Node j(i); Node k(INVALID);
deba@891: 	i=j;
deba@891: 	bool b; b=true;
deba@891: 	b=(i==INVALID); b=(i!=INVALID);
deba@891: 	b=(i==j); b=(i!=j); b=(i<j);
deba@891:       }
deba@891:       {
deba@891: 	NodeIt i; NodeIt j(i); NodeIt k(INVALID); NodeIt l(G);
deba@891: 	i=j;
deba@891: 	j=G.first(i);
deba@891: 	j=++i;
deba@891: 	bool b; b=true;
deba@891: 	b=(i==INVALID); b=(i!=INVALID);
deba@891: 	Node n(i);
deba@891: 	n=i;
deba@891: 	b=(i==j); b=(i!=j); b=(i<j);
deba@891: 	//Node ->NodeIt conversion
deba@891: 	NodeIt ni(G,n);
deba@891:       }
deba@891:       {
deba@891: 	Edge i; Edge j(i); Edge k(INVALID);
deba@891: 	i=j;
deba@891: 	bool b; b=true;
deba@891: 	b=(i==INVALID); b=(i!=INVALID);
deba@891: 	b=(i==j); b=(i!=j); b=(i<j);
deba@891:       }
deba@891:       {
deba@891: 	EdgeIt i; EdgeIt j(i); EdgeIt k(INVALID); EdgeIt l(G);
deba@891: 	i=j;
deba@891: 	j=G.first(i);
deba@891: 	j=++i;
deba@891: 	bool b; b=true;
deba@891: 	b=(i==INVALID); b=(i!=INVALID);
deba@891: 	Edge e(i);
deba@891: 	e=i;
deba@891: 	b=(i==j); b=(i!=j); b=(i<j);
deba@891: 	//Edge ->EdgeIt conversion
deba@891: 	EdgeIt ei(G,e);
deba@891:       }
deba@891:       {
deba@891: 	Node n;
deba@891: 	InEdgeIt i; InEdgeIt j(i); InEdgeIt k(INVALID); InEdgeIt l(G,n);
deba@891: 	i=j;
deba@891: 	j=G.first(i,n);
deba@891: 	j=++i;
deba@891: 	bool b; b=true;
deba@891: 	b=(i==INVALID); b=(i!=INVALID);
deba@891: 	Edge e(i);
deba@891: 	e=i;
deba@891: 	b=(i==j); b=(i!=j); b=(i<j);
deba@891: 	//Edge ->InEdgeIt conversion
deba@891: 	InEdgeIt ei(G,e);
deba@891:       }
deba@891:       {
deba@891: 	Node n;
deba@891: 	OutEdgeIt i; OutEdgeIt j(i); OutEdgeIt k(INVALID); OutEdgeIt l(G,n);
deba@891: 	i=j;
deba@891: 	j=G.first(i,n);
deba@891: 	j=++i;
deba@891: 	bool b; b=true;
deba@891: 	b=(i==INVALID); b=(i!=INVALID);
deba@891: 	Edge e(i);
deba@891: 	e=i;
deba@891: 	b=(i==j); b=(i!=j); b=(i<j);
deba@891: 	//Edge ->OutEdgeIt conversion
deba@891: 	OutEdgeIt ei(G,e);
deba@891:       }
deba@891:       {
deba@891: 	Node n,m;
deba@891: 	n=m=INVALID;
deba@891: 	Edge e;
deba@891: 	e=INVALID;
deba@891: 	n=G.tail(e);
deba@891: 	n=G.head(e);
deba@891:       }
deba@891:       // id tests
deba@891:       { Node n; int i=G.id(n); i=i; }
deba@891:       { Edge e; int i=G.id(e); i=i; }
deba@891:       //NodeMap tests
deba@891:       {
deba@891: 	Node k;
deba@891: 	typename Graph::template NodeMap<int> m(G);
deba@891: 	//Const map
deba@891: 	typename Graph::template NodeMap<int> const &cm = m;
deba@891: 	//Inicialize with default value
deba@891: 	typename Graph::template NodeMap<int> mdef(G,12);
deba@891: 	//Copy
deba@891: 	typename Graph::template NodeMap<int> mm(cm);
deba@891: 	//Copy from another type
deba@891: 	typename Graph::template NodeMap<double> dm(cm);
deba@891: 	//Copy to more complex type
deba@891: 	typename Graph::template NodeMap<DummyType> em(cm);
deba@891: 	int v;
deba@891: 	v=m[k]; m[k]=v; m.set(k,v);
deba@891: 	v=cm[k];
alpar@800:     
deba@891: 	m=cm;  
deba@891: 	dm=cm; //Copy from another type  
deba@891: 	em=cm; //Copy to more complex type
deba@891: 	{
deba@891: 	  //Check the typedef's
deba@891: 	  typename Graph::template NodeMap<int>::ValueType val;
deba@891: 	  val=1;
deba@891: 	  typename Graph::template NodeMap<int>::KeyType key;
deba@891: 	  key = typename Graph::NodeIt(G);
deba@891: 	}
deba@891:       }  
deba@891:       { //bool NodeMap
deba@891: 	Node k;
deba@891: 	typename Graph::template NodeMap<bool> m(G);
deba@891: 	typename Graph::template NodeMap<bool> const &cm = m;  //Const map
deba@891: 	//Inicialize with default value
deba@891: 	typename Graph::template NodeMap<bool> mdef(G,12);
deba@891: 	typename Graph::template NodeMap<bool> mm(cm);   //Copy
deba@891: 	typename Graph::template NodeMap<int> dm(cm); //Copy from another type
deba@891: 	bool v;
deba@891: 	v=m[k]; m[k]=v; m.set(k,v);
deba@891: 	v=cm[k];
deba@891:     
deba@891: 	m=cm;  
deba@891: 	dm=cm; //Copy from another type
deba@891: 	m=dm; //Copy to another type
deba@891: 
deba@891: 	{
deba@891: 	  //Check the typedef's
deba@891: 	  typename Graph::template NodeMap<bool>::ValueType val;
deba@891: 	  val=true;
deba@891: 	  typename Graph::template NodeMap<bool>::KeyType key;
deba@891: 	  key= typename Graph::NodeIt(G);
deba@891: 	}
deba@891:       }
deba@891:       //EdgeMap tests
deba@891:       {
deba@891: 	Edge k;
deba@891: 	typename Graph::template EdgeMap<int> m(G);
deba@891: 	typename Graph::template EdgeMap<int> const &cm = m;  //Const map
deba@891: 	//Inicialize with default value
deba@891: 	typename Graph::template EdgeMap<int> mdef(G,12);
deba@891: 	typename Graph::template EdgeMap<int> mm(cm);   //Copy
deba@891: 	typename Graph::template EdgeMap<double> dm(cm); //Copy from another type
deba@891: 	int v;
deba@891: 	v=m[k]; m[k]=v; m.set(k,v);
deba@891: 	v=cm[k];
deba@891:     
deba@891: 	m=cm;  
deba@891: 	dm=cm; //Copy from another type
deba@891: 	{
deba@891: 	  //Check the typedef's
deba@891: 	  typename Graph::template EdgeMap<int>::ValueType val;
deba@891: 	  val=1;
deba@891: 	  typename Graph::template EdgeMap<int>::KeyType key;
deba@891: 	  key= typename Graph::EdgeIt(G);
deba@891: 	}
deba@891:       }  
deba@891:       { //bool EdgeMap
deba@891: 	Edge k;
deba@891: 	typename Graph::template EdgeMap<bool> m(G);
deba@891: 	typename Graph::template EdgeMap<bool> const &cm = m;  //Const map
deba@891: 	//Inicialize with default value
deba@891: 	typename Graph::template EdgeMap<bool> mdef(G,12);
deba@891: 	typename Graph::template EdgeMap<bool> mm(cm);   //Copy
deba@891: 	typename Graph::template EdgeMap<int> dm(cm); //Copy from another type
deba@891: 	bool v;
deba@891: 	v=m[k]; m[k]=v; m.set(k,v);
deba@891: 	v=cm[k];
deba@891:     
deba@891: 	m=cm;  
deba@891: 	dm=cm; //Copy from another type
deba@891: 	m=dm; //Copy to another type
deba@891: 	{
deba@891: 	  //Check the typedef's
deba@891: 	  typename Graph::template EdgeMap<bool>::ValueType val;
deba@891: 	  val=true;
deba@891: 	  typename Graph::template EdgeMap<bool>::KeyType key;
deba@891: 	  key= typename Graph::EdgeIt(G);
deba@891: 	}
deba@891:       }
deba@891:     }
deba@891: 
deba@891:   template<class Graph> void checkCompileGraph(Graph &G) 
alpar@800:     {
deba@891:       checkCompileStaticGraph(G);
deba@891: 
deba@891:       typedef typename Graph::Node Node;
deba@891:       typedef typename Graph::NodeIt NodeIt;
deba@891:       typedef typename Graph::Edge Edge;
deba@891:       typedef typename Graph::EdgeIt EdgeIt;
deba@891:       typedef typename Graph::InEdgeIt InEdgeIt;
deba@891:       typedef typename Graph::OutEdgeIt OutEdgeIt;
deba@891:   
deba@891:       Node n,m;
deba@891:       n=G.addNode();
deba@891:       m=G.addNode();
deba@891:       Edge e;
deba@891:       e=G.addEdge(n,m); 
deba@891:   
deba@891:       //  G.clear();
alpar@800:     }
alpar@800: 
deba@891:   template<class Graph> void checkCompileGraphEraseEdge(Graph &G) 
alpar@800:     {
deba@891:       typename Graph::Edge e;
deba@891:       G.erase(e);
alpar@800:     }
deba@891: 
deba@891:   template<class Graph> void checkCompileGraphEraseNode(Graph &G) 
alpar@800:     {
deba@891:       typename Graph::Node n;
deba@891:       G.erase(n);
alpar@800:     }
deba@891: 
deba@891:   template<class Graph> void checkCompileErasableGraph(Graph &G) 
alpar@800:     {
deba@891:       checkCompileGraph(G);
deba@891:       checkCompileGraphEraseNode(G);
deba@891:       checkCompileGraphEraseEdge(G);
alpar@800:     }
alpar@800: 
deba@891:   template<class Graph> void checkCompileGraphFindEdge(Graph &G) 
deba@891:     {
deba@891:       typedef typename Graph::NodeIt Node;
deba@891:       typedef typename Graph::NodeIt NodeIt;
alpar@800: 
deba@891:       G.findEdge(NodeIt(G),++NodeIt(G),G.findEdge(NodeIt(G),++NodeIt(G)));
deba@891:       G.findEdge(Node(),Node(),G.findEdge(Node(),Node()));  
deba@891:     }
alpar@800: 
deba@891:   template<class Graph> void checkGraphNodeList(Graph &G, int nn)
deba@891:     {
deba@891:       typename Graph::NodeIt n(G);
deba@891:       for(int i=0;i<nn;i++) {
deba@891: 	check(n!=INVALID,"Wrong Node list linking.");
deba@891: 	++n;
deba@891:       }
deba@891:       check(n==INVALID,"Wrong Node list linking.");
deba@891:     }
alpar@800: 
deba@891:   template<class Graph> void checkGraphEdgeList(Graph &G, int nn)
deba@891:     {
deba@891:       typedef typename Graph::EdgeIt EdgeIt;
alpar@800: 
deba@891:       EdgeIt e(G);
deba@891:       for(int i=0;i<nn;i++) {
deba@891: 	check(e!=INVALID,"Wrong Edge list linking.");
deba@891: 	++e;
deba@891:       }
deba@891:       check(e==INVALID,"Wrong Edge list linking.");
deba@891:     }
alpar@800: 
deba@891:   template<class Graph> void checkGraphOutEdgeList(Graph &G,
deba@891: 						   typename Graph::Node n,
deba@891: 						   int nn)
deba@891:     {
deba@891:       typename Graph::OutEdgeIt e(G,n);
deba@891:       for(int i=0;i<nn;i++) {
deba@891: 	check(e!=INVALID,"Wrong OutEdge list linking.");
deba@916: 	check(n==G.tail(e), "Wrong OutEdge list linking.");
deba@891: 	++e;
deba@891:       }
deba@891:       check(e==INVALID,"Wrong OutEdge list linking.");
deba@891:     }
alpar@800: 
deba@891:   template<class Graph> void checkGraphInEdgeList(Graph &G,
deba@891: 						  typename Graph::Node n,
deba@891: 						  int nn)
deba@891:     {
deba@891:       typename Graph::InEdgeIt e(G,n);
deba@891:       for(int i=0;i<nn;i++) {
deba@891: 	check(e!=INVALID,"Wrong InEdge list linking.");
deba@916: 	check(n==G.head(e), "Wrong InEdge list linking.");
deba@891: 	++e;
deba@891:       }
deba@891:       check(e==INVALID,"Wrong InEdge list linking.");
deba@891:     }
alpar@800: 
deba@891:   ///\file
deba@891:   ///\todo Check head(), tail() as well;
alpar@800: 
alpar@800:   
alpar@800: } //namespace hugo
alpar@800: 
alpar@800: 
alpar@800: #endif