alpar@503: #include<iostream>
ladanyi@542: #include<hugo/smart_graph.h>
alpar@564: #include<hugo/skeletons/graph.h>
alpar@578: #include<hugo/list_graph.h>
alpar@592: #include<hugo/full_graph.h>
alpar@578: 
alpar@567: #include"test_tools.h"
alpar@567: 
alpar@774: /**
alpar@774: \file
alpar@503: This test makes consistency checks of list graph structures.
alpar@503: 
alpar@774: G.addNode(), G.addEdge(), G.tail(), G.head()
alpar@503: 
alpar@592: \todo Checks for empty graphs and isolated points.
alpar@774: \todo Checks for Node->NodeIt, Edge->{EdgeIt,InEdgeIt,OutEdgeIt}
alpar@774: conversion.
alpar@503: */
alpar@503: 
alpar@503: using namespace hugo;
alpar@503: 
alpar@592: template<class Graph> void checkCompileStaticGraph(Graph &G) 
alpar@503: {
alpar@503:   typedef typename Graph::Node Node;
alpar@503:   typedef typename Graph::NodeIt NodeIt;
alpar@503:   typedef typename Graph::Edge Edge;
alpar@503:   typedef typename Graph::EdgeIt EdgeIt;
alpar@503:   typedef typename Graph::InEdgeIt InEdgeIt;
alpar@503:   typedef typename Graph::OutEdgeIt OutEdgeIt;
alpar@503:   
alpar@503:   {
alpar@503:     Node i; Node j(i); Node k(INVALID);
alpar@503:     i=j;
alpar@774:     //    bool b=G.valid(i); b=b;
alpar@774:     bool b; b=b;
alpar@774:     b=(i==INVALID); b=(i!=INVALID);
alpar@503:     b=(i==j); b=(i!=j); b=(i<j);
alpar@503:   }
alpar@503:   {
alpar@503:     NodeIt i; NodeIt j(i); NodeIt k(INVALID); NodeIt l(G);
alpar@503:     i=j;
alpar@503:     j=G.first(i);
alpar@774:     j=++i;
alpar@774:     //    bool b=G.valid(i); b=b;
alpar@774:     bool b; b=b;
alpar@774:     b=(i==INVALID); b=(i!=INVALID);
alpar@503:     Node n(i);
alpar@503:     n=i;
alpar@503:     b=(i==j); b=(i!=j); b=(i<j);
alpar@774:     //Node ->NodeIt conversion
alpar@774:     NodeIt ni(G,n);
alpar@503:   }
alpar@503:   {
alpar@503:     Edge i; Edge j(i); Edge k(INVALID);
alpar@503:     i=j;
alpar@774:     //    bool b=G.valid(i); b=b;
alpar@774:     bool b; b=b;
alpar@774:     b=(i==INVALID); b=(i!=INVALID);
alpar@503:     b=(i==j); b=(i!=j); b=(i<j);
alpar@503:   }
alpar@503:   {
alpar@503:     EdgeIt i; EdgeIt j(i); EdgeIt k(INVALID); EdgeIt l(G);
alpar@503:     i=j;
alpar@503:     j=G.first(i);
alpar@774:     j=++i;
alpar@774:     //    bool b=G.valid(i); b=b;
alpar@774:     bool b; b=b;
alpar@774:     b=(i==INVALID); b=(i!=INVALID);
alpar@503:     Edge e(i);
alpar@503:     e=i;
alpar@503:     b=(i==j); b=(i!=j); b=(i<j);
alpar@774:     //Edge ->EdgeIt conversion
alpar@774:     EdgeIt ei(G,e);
alpar@503:   }
alpar@503:   {
alpar@503:     Node n;
alpar@503:     InEdgeIt i; InEdgeIt j(i); InEdgeIt k(INVALID); InEdgeIt l(G,n);
alpar@503:     i=j;
alpar@503:     j=G.first(i,n);
alpar@774:     j=++i;
alpar@774:     //    bool b=G.valid(i); b=b;
alpar@774:     bool b; b=b;
alpar@774:     b=(i==INVALID); b=(i!=INVALID);
alpar@503:     Edge e(i);
alpar@503:     e=i;
alpar@503:     b=(i==j); b=(i!=j); b=(i<j);
alpar@774:     //Edge ->InEdgeIt conversion
alpar@774:     InEdgeIt ei(G,e);
alpar@503:   }
alpar@503:   {
alpar@503:     Node n;
alpar@503:     OutEdgeIt i; OutEdgeIt j(i); OutEdgeIt k(INVALID); OutEdgeIt l(G,n);
alpar@503:     i=j;
alpar@503:     j=G.first(i,n);
alpar@774:     j=++i;
alpar@774:     //    bool b=G.valid(i); b=b;
alpar@774:     bool b; b=b;
alpar@774:     b=(i==INVALID); b=(i!=INVALID);
alpar@503:     Edge e(i);
alpar@503:     e=i;
alpar@503:     b=(i==j); b=(i!=j); b=(i<j);
alpar@774:     //Edge ->OutEdgeIt conversion
alpar@774:     OutEdgeIt ei(G,e);
alpar@503:   }
alpar@774:   {
alpar@774:     Node n,m;
alpar@774:     n=m=INVALID;
alpar@774:     Edge e;
alpar@774:     e=INVALID;
alpar@774:     n=G.tail(e);
alpar@774:     n=G.head(e);
alpar@774:   }
alpar@503:   // id tests
alpar@774:   { Node n; int i=G.id(n); i=i; }
alpar@774:   { Edge e; int i=G.id(e); i=i; }
alpar@503:   //NodeMap tests
alpar@503:   {
alpar@503:     Node k;
alpar@515:     typename Graph::template NodeMap<int> m(G);
alpar@774:     //Const map
alpar@774:     typename Graph::template NodeMap<int> const &cm = m;
alpar@515:     //Inicialize with default value
alpar@515:     typename Graph::template NodeMap<int> mdef(G,12);
alpar@774:     //Copy
alpar@774:     typename Graph::template NodeMap<int> mm(cm);
alpar@774:     //Copy from another type
alpar@774:     typename Graph::template NodeMap<double> dm(cm);
alpar@503:     int v;
alpar@503:     v=m[k]; m[k]=v; m.set(k,v);
alpar@503:     v=cm[k];
alpar@503:     
alpar@503:     m=cm;  
alpar@503:     dm=cm; //Copy from another type
alpar@787:     {
alpar@787:       //Check the typedef's
alpar@787:       typename Graph::template NodeMap<int>::ValueType val;
alpar@787:       val=1;
alpar@787:       typename Graph::template NodeMap<int>::KeyType key;
alpar@787:       key = typename Graph::NodeIt(G);
alpar@787:     }
alpar@503:   }  
alpar@503:   { //bool NodeMap
alpar@503:     Node k;
alpar@515:     typename Graph::template NodeMap<bool> m(G);
alpar@515:     typename Graph::template NodeMap<bool> const &cm = m;  //Const map
alpar@515:     //Inicialize with default value
alpar@515:     typename Graph::template NodeMap<bool> mdef(G,12);
alpar@515:     typename Graph::template NodeMap<bool> mm(cm);   //Copy
alpar@515:     typename Graph::template NodeMap<int> dm(cm); //Copy from another type
alpar@503:     bool v;
alpar@503:     v=m[k]; m[k]=v; m.set(k,v);
alpar@503:     v=cm[k];
alpar@503:     
alpar@503:     m=cm;  
alpar@503:     dm=cm; //Copy from another type
alpar@504:     m=dm; //Copy to another type
alpar@787: 
alpar@787:     {
alpar@787:       //Check the typedef's
alpar@787:       typename Graph::template NodeMap<bool>::ValueType val;
alpar@787:       val=true;
alpar@787:       typename Graph::template NodeMap<bool>::KeyType key;
alpar@787:       key= typename Graph::NodeIt(G);
alpar@787:     }
alpar@503:   }
alpar@503:   //EdgeMap tests
alpar@503:   {
alpar@503:     Edge k;
alpar@515:     typename Graph::template EdgeMap<int> m(G);
alpar@515:     typename Graph::template EdgeMap<int> const &cm = m;  //Const map
alpar@515:     //Inicialize with default value
alpar@515:     typename Graph::template EdgeMap<int> mdef(G,12);
alpar@515:     typename Graph::template EdgeMap<int> mm(cm);   //Copy
alpar@515:     typename Graph::template EdgeMap<double> dm(cm); //Copy from another type
alpar@503:     int v;
alpar@503:     v=m[k]; m[k]=v; m.set(k,v);
alpar@503:     v=cm[k];
alpar@503:     
alpar@503:     m=cm;  
alpar@503:     dm=cm; //Copy from another type
alpar@787:     {
alpar@787:       //Check the typedef's
alpar@787:       typename Graph::template EdgeMap<int>::ValueType val;
alpar@787:       val=1;
alpar@787:       typename Graph::template EdgeMap<int>::KeyType key;
alpar@787:       key= typename Graph::EdgeIt(G);
alpar@787:     }
alpar@503:   }  
alpar@503:   { //bool EdgeMap
alpar@503:     Edge k;
alpar@515:     typename Graph::template EdgeMap<bool> m(G);
alpar@515:     typename Graph::template EdgeMap<bool> const &cm = m;  //Const map
alpar@515:     //Inicialize with default value
alpar@515:     typename Graph::template EdgeMap<bool> mdef(G,12);
alpar@515:     typename Graph::template EdgeMap<bool> mm(cm);   //Copy
alpar@515:     typename Graph::template EdgeMap<int> dm(cm); //Copy from another type
alpar@503:     bool v;
alpar@503:     v=m[k]; m[k]=v; m.set(k,v);
alpar@503:     v=cm[k];
alpar@503:     
alpar@503:     m=cm;  
alpar@503:     dm=cm; //Copy from another type
alpar@504:     m=dm; //Copy to another type
alpar@787:     {
alpar@787:       //Check the typedef's
alpar@787:       typename Graph::template EdgeMap<bool>::ValueType val;
alpar@787:       val=true;
alpar@787:       typename Graph::template EdgeMap<bool>::KeyType key;
alpar@787:       key= typename Graph::EdgeIt(G);
alpar@787:     }
alpar@503:   }
alpar@503: }
alpar@503: 
alpar@592: template<class Graph> void checkCompile(Graph &G) 
alpar@592: {
alpar@592:   checkCompileStaticGraph(G);
alpar@592: 
alpar@592:   typedef typename Graph::Node Node;
alpar@592:   typedef typename Graph::NodeIt NodeIt;
alpar@592:   typedef typename Graph::Edge Edge;
alpar@592:   typedef typename Graph::EdgeIt EdgeIt;
alpar@592:   typedef typename Graph::InEdgeIt InEdgeIt;
alpar@592:   typedef typename Graph::OutEdgeIt OutEdgeIt;
alpar@592:   
alpar@592:   Node n,m;
alpar@592:   n=G.addNode();
alpar@592:   m=G.addNode();
alpar@774:   Edge e;
alpar@774:   e=G.addEdge(n,m); 
alpar@592:   
alpar@774:   //  G.clear();
alpar@774: }
alpar@774: 
alpar@774: template<class Graph> void checkCompileErase(Graph &G) 
alpar@774: {
alpar@774:   typedef typename Graph::Node Node;
alpar@774:   typedef typename Graph::Edge Edge;
alpar@774:   Node n;
alpar@774:   Edge e;
alpar@774:   G.erase(n);
alpar@774:   G.erase(e);
alpar@774: }
alpar@774: 
alpar@774: template<class Graph> void checkCompileEraseEdge(Graph &G) 
alpar@774: {
alpar@774:   typedef typename Graph::Edge Edge;
alpar@774:   Edge e;
alpar@774:   G.erase(e);
alpar@774: }
alpar@774: 
alpar@774: template<class Graph> void checkCompileFindEdge(Graph &G) 
alpar@774: {
alpar@774:   typedef typename Graph::NodeIt Node;
alpar@774:   typedef typename Graph::NodeIt NodeIt;
alpar@774: 
alpar@774:   G.findEdge(NodeIt(G),++NodeIt(G),G.findEdge(NodeIt(G),++NodeIt(G)));
alpar@774:   G.findEdge(Node(),Node(),G.findEdge(Node(),Node()));  
alpar@592: }
alpar@592: 
alpar@592: 
alpar@503: template<class Graph> void checkNodeList(Graph &G, int nn)
alpar@503: {
alpar@503:   typename Graph::NodeIt n(G);
alpar@503:   for(int i=0;i<nn;i++) {
alpar@774:     check(n!=INVALID,"Wrong Node list linking.");
alpar@774:     ++n;
alpar@503:   }
alpar@774:   check(n==INVALID,"Wrong Node list linking.");
alpar@503: }
alpar@503: 
alpar@503: template<class Graph> void checkEdgeList(Graph &G, int nn)
alpar@503: {
alpar@503:   typedef typename Graph::EdgeIt EdgeIt;
alpar@503: 
alpar@503:   EdgeIt e(G);
alpar@503:   for(int i=0;i<nn;i++) {
alpar@774:     check(e!=INVALID,"Wrong Edge list linking.");
alpar@774:     ++e;
alpar@503:   }
alpar@774:   check(e==INVALID,"Wrong Edge list linking.");
alpar@503: }
alpar@503: 
alpar@503: template<class Graph> void checkOutEdgeList(Graph &G,
alpar@503: 					    typename Graph::Node n,
alpar@503: 					    int nn)
alpar@503: {
alpar@503:   typename Graph::OutEdgeIt e(G,n);
alpar@503:   for(int i=0;i<nn;i++) {
alpar@774:     check(e!=INVALID,"Wrong OutEdge list linking.");
alpar@774:     ++e;
alpar@503:   }
alpar@774:   check(e==INVALID,"Wrong OutEdge list linking.");
alpar@503: }
alpar@503: 
alpar@503: template<class Graph> void checkInEdgeList(Graph &G,
alpar@774: 					   typename Graph::Node n,
alpar@774: 					   int nn)
alpar@503: {
alpar@503:   typename Graph::InEdgeIt e(G,n);
alpar@503:   for(int i=0;i<nn;i++) {
alpar@774:     check(e!=INVALID,"Wrong InEdge list linking.");
alpar@774:     ++e;
alpar@503:   }
alpar@774:   check(e==INVALID,"Wrong InEdge list linking.");
alpar@503: }
alpar@503: 
alpar@774: ///\file
alpar@774: ///\todo Checks head(), tail() as well;
alpar@774: 
alpar@503: template<class Graph> void bidirPetersen(Graph &G)
alpar@503: {
alpar@503:   typedef typename Graph::Edge Edge;
alpar@503:   typedef typename Graph::EdgeIt EdgeIt;
alpar@503:   
alpar@503:   checkEdgeList(G,15);
alpar@503:   
alpar@503:   std::vector<Edge> ee;
alpar@503:   
alpar@774:   for(EdgeIt e(G);e!=INVALID;++e) ee.push_back(e);
alpar@503: 
alpar@503:   for(typename std::vector<Edge>::iterator p=ee.begin();p!=ee.end();p++)
alpar@503:     G.addEdge(G.head(*p),G.tail(*p));
alpar@503: }
alpar@503: 
alpar@503: template<class Graph> void checkPetersen(Graph &G)
alpar@503: {
alpar@503:   typedef typename Graph::Node Node;
alpar@503: 
alpar@503:   typedef typename Graph::EdgeIt EdgeIt;
alpar@503:   typedef typename Graph::NodeIt NodeIt;
alpar@503: 
alpar@503:   checkNodeList(G,10);
alpar@503:   checkEdgeList(G,30);
alpar@503: 
alpar@774:   for(NodeIt n(G);n!=INVALID;++n) {
alpar@503:     checkInEdgeList(G,n,3);
alpar@503:     checkOutEdgeList(G,n,3);
alpar@774:     ++n;
alpar@503:   }  
alpar@503: }
alpar@503: 
alpar@774: //Compile GraphSkeleton
alpar@793: template void checkCompileStaticGraph<skeleton::StaticGraphSkeleton>
alpar@793: (skeleton::StaticGraphSkeleton &);
alpar@793: 
alpar@793: template void checkCompile<skeleton::GraphSkeleton>(skeleton::GraphSkeleton &);
alpar@793: 
alpar@793: template void checkCompileErase<skeleton::EraseableGraphSkeleton>
alpar@793: (skeleton::EraseableGraphSkeleton &);
alpar@733: 
alpar@774: //Compile SmartGraph
alpar@503: template void checkCompile<SmartGraph>(SmartGraph &);
deba@783: 
alpar@774: //Compile SymSmartGraph
alpar@503: template void checkCompile<SymSmartGraph>(SymSmartGraph &);
alpar@774: 
alpar@774: //Compile ListGraph
alpar@578: template void checkCompile<ListGraph>(ListGraph &);
alpar@774: template void checkCompileErase<ListGraph>(ListGraph &);
alpar@774: template void checkCompileFindEdge<ListGraph>(ListGraph &);
alpar@774: 
deba@783: 
alpar@774: //Compile SymListGraph
alpar@578: template void checkCompile<SymListGraph>(SymListGraph &);
alpar@774: template void checkCompileErase<SymListGraph>(SymListGraph &);
alpar@774: template void checkCompileFindEdge<SymListGraph>(SymListGraph &);
alpar@774: 
alpar@774: //Compile FullGraph
alpar@592: template void checkCompileStaticGraph<FullGraph>(FullGraph &);
alpar@774: template void checkCompileFindEdge<FullGraph>(FullGraph &);
alpar@550: 
alpar@774: //Compile EdgeSet <ListGraph>
alpar@579: template void checkCompile<EdgeSet <ListGraph> >(EdgeSet <ListGraph> &);
alpar@774: template
alpar@774: void checkCompileEraseEdge<EdgeSet <ListGraph> >(EdgeSet <ListGraph> &);
alpar@774: template
alpar@774: void checkCompileFindEdge<EdgeSet <ListGraph> >(EdgeSet <ListGraph> &);
alpar@774: 
alpar@774: //Compile EdgeSet <NodeSet>
alpar@717: template void checkCompile<EdgeSet <NodeSet> >(EdgeSet <NodeSet> &);
alpar@774: template
alpar@774: void checkCompileEraseEdge<EdgeSet <NodeSet> >(EdgeSet <NodeSet> &);
alpar@774: template void checkCompileFindEdge<EdgeSet <NodeSet> >(EdgeSet <NodeSet> &);
alpar@774: 
alpar@503: 
alpar@503: int main() 
alpar@503: {
alpar@503:   {
alpar@503:     SmartGraph G;
alpar@503:     addPetersen(G);
alpar@503:     bidirPetersen(G);
alpar@503:     checkPetersen(G);
alpar@503:   }
alpar@578:   {
alpar@578:     ListGraph G;
alpar@578:     addPetersen(G);
alpar@578:     bidirPetersen(G);
alpar@578:     checkPetersen(G);
alpar@578:   }
alpar@503:   {
alpar@503:     SymSmartGraph G;
alpar@503:     addPetersen(G);
alpar@503:     checkPetersen(G);
alpar@503:   }
alpar@578:   {
alpar@578:     SymListGraph G;
alpar@578:     addPetersen(G);
alpar@578:     checkPetersen(G);
alpar@578:   }
alpar@503: 
alpar@774:   ///\file
alpar@774:   ///\todo map tests.
alpar@774:   ///\todo copy constr tests.
alpar@503: 
alpar@503:   std::cout << __FILE__ ": All tests passed.\n";
alpar@503: 
alpar@579:   return 0;
alpar@503: }