source: lemon-0.x/src/test/graph_test.cc @ 774:4297098d9677

#include<iostream>
#include<hugo/smart_graph.h>
#include<hugo/skeletons/graph.h>
#include<hugo/list_graph.h>
#include<hugo/full_graph.h>

#include"test_tools.h"

/**
\file
This test makes consistency checks of list graph structures.

G.addNode(), G.addEdge(), G.tail(), G.head()

\todo Checks for empty graphs and isolated points.
\todo Checks for Node->NodeIt, Edge->{EdgeIt,InEdgeIt,OutEdgeIt}
conversion.
*/

using namespace hugo;
using namespace hugo::skeleton;

template<class Graph> void checkCompileStaticGraph(Graph &G) 
{
  typedef typename Graph::Node Node;
  typedef typename Graph::NodeIt NodeIt;
  typedef typename Graph::Edge Edge;
  typedef typename Graph::EdgeIt EdgeIt;
  typedef typename Graph::InEdgeIt InEdgeIt;
  typedef typename Graph::OutEdgeIt OutEdgeIt;
  
  {
    Node i; Node j(i); Node k(INVALID);
    i=j;
    //    bool b=G.valid(i); b=b;
    bool b; b=b;
    b=(i==INVALID); b=(i!=INVALID);
    b=(i==j); b=(i!=j); b=(i<j);
  }
  {
    NodeIt i; NodeIt j(i); NodeIt k(INVALID); NodeIt l(G);
    i=j;
    j=G.first(i);
    j=++i;
    //    bool b=G.valid(i); b=b;
    bool b; b=b;
    b=(i==INVALID); b=(i!=INVALID);
    Node n(i);
    n=i;
    b=(i==j); b=(i!=j); b=(i<j);
    //Node ->NodeIt conversion
    NodeIt ni(G,n);
  }
  {
    Edge i; Edge j(i); Edge k(INVALID);
    i=j;
    //    bool b=G.valid(i); b=b;
    bool b; b=b;
    b=(i==INVALID); b=(i!=INVALID);
    b=(i==j); b=(i!=j); b=(i<j);
  }
  {
    EdgeIt i; EdgeIt j(i); EdgeIt k(INVALID); EdgeIt l(G);
    i=j;
    j=G.first(i);
    j=++i;
    //    bool b=G.valid(i); b=b;
    bool b; b=b;
    b=(i==INVALID); b=(i!=INVALID);
    Edge e(i);
    e=i;
    b=(i==j); b=(i!=j); b=(i<j);
    //Edge ->EdgeIt conversion
    EdgeIt ei(G,e);
  }
  {
    Node n;
    InEdgeIt i; InEdgeIt j(i); InEdgeIt k(INVALID); InEdgeIt l(G,n);
    i=j;
    j=G.first(i,n);
    j=++i;
    //    bool b=G.valid(i); b=b;
    bool b; b=b;
    b=(i==INVALID); b=(i!=INVALID);
    Edge e(i);
    e=i;
    b=(i==j); b=(i!=j); b=(i<j);
    //Edge ->InEdgeIt conversion
    InEdgeIt ei(G,e);
  }
  {
    Node n;
    OutEdgeIt i; OutEdgeIt j(i); OutEdgeIt k(INVALID); OutEdgeIt l(G,n);
    i=j;
    j=G.first(i,n);
    j=++i;
    //    bool b=G.valid(i); b=b;
    bool b; b=b;
    b=(i==INVALID); b=(i!=INVALID);
    Edge e(i);
    e=i;
    b=(i==j); b=(i!=j); b=(i<j);
    //Edge ->OutEdgeIt conversion
    OutEdgeIt ei(G,e);
  }
  {
    Node n,m;
    n=m=INVALID;
    Edge e;
    e=INVALID;
    n=G.tail(e);
    n=G.head(e);
  }
  // id tests
  { Node n; int i=G.id(n); i=i; }
  { Edge e; int i=G.id(e); i=i; }
  //NodeMap tests
  {
    Node k;
    typename Graph::template NodeMap<int> m(G);
    //Const map
    typename Graph::template NodeMap<int> const &cm = m;
    //Inicialize with default value
    typename Graph::template NodeMap<int> mdef(G,12);
    //Copy
    typename Graph::template NodeMap<int> mm(cm);
    //Copy from another type
    typename Graph::template NodeMap<double> dm(cm);
    int v;
    v=m[k]; m[k]=v; m.set(k,v);
    v=cm[k];
    
    m=cm;  
    dm=cm; //Copy from another type
  }  
  { //bool NodeMap
    Node k;
    typename Graph::template NodeMap<bool> m(G);
    typename Graph::template NodeMap<bool> const &cm = m;  //Const map
    //Inicialize with default value
    typename Graph::template NodeMap<bool> mdef(G,12);
    typename Graph::template NodeMap<bool> mm(cm);   //Copy
    typename Graph::template NodeMap<int> dm(cm); //Copy from another type
    bool v;
    v=m[k]; m[k]=v; m.set(k,v);
    v=cm[k];
    
    m=cm;  
    dm=cm; //Copy from another type
    m=dm; //Copy to another type
  }
  //EdgeMap tests
  {
    Edge k;
    typename Graph::template EdgeMap<int> m(G);
    typename Graph::template EdgeMap<int> const &cm = m;  //Const map
    //Inicialize with default value
    typename Graph::template EdgeMap<int> mdef(G,12);
    typename Graph::template EdgeMap<int> mm(cm);   //Copy
    typename Graph::template EdgeMap<double> dm(cm); //Copy from another type
    int v;
    v=m[k]; m[k]=v; m.set(k,v);
    v=cm[k];
    
    m=cm;  
    dm=cm; //Copy from another type
  }  
  { //bool EdgeMap
    Edge k;
    typename Graph::template EdgeMap<bool> m(G);
    typename Graph::template EdgeMap<bool> const &cm = m;  //Const map
    //Inicialize with default value
    typename Graph::template EdgeMap<bool> mdef(G,12);
    typename Graph::template EdgeMap<bool> mm(cm);   //Copy
    typename Graph::template EdgeMap<int> dm(cm); //Copy from another type
    bool v;
    v=m[k]; m[k]=v; m.set(k,v);
    v=cm[k];
    
    m=cm;  
    dm=cm; //Copy from another type
    m=dm; //Copy to another type
  }
}

template<class Graph> void checkCompile(Graph &G) 
{
  checkCompileStaticGraph(G);

  typedef typename Graph::Node Node;
  typedef typename Graph::NodeIt NodeIt;
  typedef typename Graph::Edge Edge;
  typedef typename Graph::EdgeIt EdgeIt;
  typedef typename Graph::InEdgeIt InEdgeIt;
  typedef typename Graph::OutEdgeIt OutEdgeIt;
  
  Node n,m;
  n=G.addNode();
  m=G.addNode();
  Edge e;
  e=G.addEdge(n,m); 
  
  //  G.clear();
}

template<class Graph> void checkCompileErase(Graph &G) 
{
  typedef typename Graph::Node Node;
  typedef typename Graph::Edge Edge;
  Node n;
  Edge e;
  G.erase(n);
  G.erase(e);
}

template<class Graph> void checkCompileEraseEdge(Graph &G) 
{
  typedef typename Graph::Edge Edge;
  Edge e;
  G.erase(e);
}

template<class Graph> void checkCompileFindEdge(Graph &G) 
{
  typedef typename Graph::NodeIt Node;
  typedef typename Graph::NodeIt NodeIt;

  G.findEdge(NodeIt(G),++NodeIt(G),G.findEdge(NodeIt(G),++NodeIt(G)));
  G.findEdge(Node(),Node(),G.findEdge(Node(),Node()));  
}


template<class Graph> void checkNodeList(Graph &G, int nn)
{
  typename Graph::NodeIt n(G);
  for(int i=0;i<nn;i++) {
    check(n!=INVALID,"Wrong Node list linking.");
    ++n;
  }
  check(n==INVALID,"Wrong Node list linking.");
}

template<class Graph> void checkEdgeList(Graph &G, int nn)
{
  typedef typename Graph::EdgeIt EdgeIt;

  EdgeIt e(G);
  for(int i=0;i<nn;i++) {
    check(e!=INVALID,"Wrong Edge list linking.");
    ++e;
  }
  check(e==INVALID,"Wrong Edge list linking.");
}

template<class Graph> void checkOutEdgeList(Graph &G,
                                            typename Graph::Node n,
                                            int nn)
{
  typename Graph::OutEdgeIt e(G,n);
  for(int i=0;i<nn;i++) {
    check(e!=INVALID,"Wrong OutEdge list linking.");
    ++e;
  }
  check(e==INVALID,"Wrong OutEdge list linking.");
}

template<class Graph> void checkInEdgeList(Graph &G,
                                           typename Graph::Node n,
                                           int nn)
{
  typename Graph::InEdgeIt e(G,n);
  for(int i=0;i<nn;i++) {
    check(e!=INVALID,"Wrong InEdge list linking.");
    ++e;
  }
  check(e==INVALID,"Wrong InEdge list linking.");
}

///\file
///\todo Checks head(), tail() as well;

template<class Graph> void bidirPetersen(Graph &G)
{
  typedef typename Graph::Edge Edge;
  typedef typename Graph::EdgeIt EdgeIt;
  
  checkEdgeList(G,15);
  
  std::vector<Edge> ee;
  
  for(EdgeIt e(G);e!=INVALID;++e) ee.push_back(e);

  for(typename std::vector<Edge>::iterator p=ee.begin();p!=ee.end();p++)
    G.addEdge(G.head(*p),G.tail(*p));
}

template<class Graph> void checkPetersen(Graph &G)
{
  typedef typename Graph::Node Node;

  typedef typename Graph::EdgeIt EdgeIt;
  typedef typename Graph::NodeIt NodeIt;

  checkNodeList(G,10);
  checkEdgeList(G,30);

  for(NodeIt n(G);n!=INVALID;++n) {
    checkInEdgeList(G,n,3);
    checkOutEdgeList(G,n,3);
    ++n;
  }  
}

//Compile GraphSkeleton
template 
void checkCompileStaticGraph<StaticGraphSkeleton>(StaticGraphSkeleton &);
template void checkCompile<GraphSkeleton>(GraphSkeleton &);
template
void checkCompileErase<EraseableGraphSkeleton>(EraseableGraphSkeleton &);

//Compile SmartGraph
template void checkCompile<SmartGraph>(SmartGraph &);
//Compile SymSmartGraph
template void checkCompile<SymSmartGraph>(SymSmartGraph &);

//Compile ListGraph
template void checkCompile<ListGraph>(ListGraph &);
template void checkCompileErase<ListGraph>(ListGraph &);
template void checkCompileFindEdge<ListGraph>(ListGraph &);

//Compile SymListGraph
template void checkCompile<SymListGraph>(SymListGraph &);
template void checkCompileErase<SymListGraph>(SymListGraph &);
template void checkCompileFindEdge<SymListGraph>(SymListGraph &);

//Compile FullGraph
template void checkCompileStaticGraph<FullGraph>(FullGraph &);
template void checkCompileFindEdge<FullGraph>(FullGraph &);

//Compile EdgeSet <ListGraph>
template void checkCompile<EdgeSet <ListGraph> >(EdgeSet <ListGraph> &);
template
void checkCompileEraseEdge<EdgeSet <ListGraph> >(EdgeSet <ListGraph> &);
template
void checkCompileFindEdge<EdgeSet <ListGraph> >(EdgeSet <ListGraph> &);

//Compile EdgeSet <NodeSet>
template void checkCompile<EdgeSet <NodeSet> >(EdgeSet <NodeSet> &);
template
void checkCompileEraseEdge<EdgeSet <NodeSet> >(EdgeSet <NodeSet> &);
template void checkCompileFindEdge<EdgeSet <NodeSet> >(EdgeSet <NodeSet> &);


int main() 
{
  {
    SmartGraph G;
    addPetersen(G);
    bidirPetersen(G);
    checkPetersen(G);
  }
  {
    ListGraph G;
    addPetersen(G);
    bidirPetersen(G);
    checkPetersen(G);
  }
  {
    SymSmartGraph G;
    addPetersen(G);
    checkPetersen(G);
  }
  {
    SymListGraph G;
    addPetersen(G);
    checkPetersen(G);
  }

  ///\file
  ///\todo map tests.
  ///\todo copy constr tests.

  std::cout << __FILE__ ": All tests passed.\n";

  return 0;
}