alpar@906: /* -*- C++ -*-
alpar@906:  *
alpar@1956:  * This file is a part of LEMON, a generic C++ optimization library
alpar@1956:  *
alpar@2553:  * Copyright (C) 2003-2008
alpar@1956:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@1359:  * (Egervary Research Group on Combinatorial Optimization, 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@906: 
alpar@921: #ifndef LEMON_TEST_TEST_TOOLS_H
alpar@921: #define LEMON_TEST_TEST_TOOLS_H
alpar@574: 
klao@978: #include <iostream>
klao@978: #include <vector>
klao@978: 
deba@1728: #include <cstdlib>
deba@1728: #include <ctime>
deba@1728: 
deba@1728: #include <lemon/concept_check.h>
alpar@2260: #include <lemon/concepts/graph.h>
klao@978: 
deba@2229: #include <lemon/random.h>
deba@2229: 
klao@978: using namespace lemon;
klao@978: 
alpar@574: //! \ingroup misc
alpar@574: //! \file
alpar@1200: //! \brief Some utilities to write test programs.
alpar@574: 
alpar@574: 
alpar@679: ///If \c rc is fail, writes an error message end exit.
alpar@574: 
alpar@574: ///If \c rc is fail, writes an error message end exit.
alpar@574: ///The error message contains the file name and the line number of the
alpar@679: ///source code in a standard from, which makes it possible to go there
alpar@574: ///using good source browsers like e.g. \c emacs.
alpar@574: ///
alpar@574: ///For example
alpar@574: ///\code check(0==1,"This is obviously false.");\endcode will
alpar@574: ///print this (and then exits).
alpar@574: ///\verbatim graph_test.cc:123: error: This is obviously false. \endverbatim
alpar@774: ///
alpar@774: ///\todo It should be in \c error.h
alpar@574: #define check(rc, msg) \
alpar@574:   if(!(rc)) { \
alpar@574:     std::cerr << __FILE__ ":" << __LINE__ << ": error: " << msg << std::endl; \
deba@2198:     abort(); \
alpar@574:   } else { } \
alpar@574: 
alpar@574: ///Structure returned by \ref addPetersen().
alpar@574: 
alpar@574: ///Structure returned by \ref addPetersen().
alpar@574: ///
alpar@574: template<class Graph> struct PetStruct
alpar@574: {
alpar@825:   ///Vector containing the outer nodes.
alpar@825:   std::vector<typename Graph::Node> outer;
alpar@825:   ///Vector containing the inner nodes.
alpar@825:   std::vector<typename Graph::Node> inner;
alpar@825:   ///Vector containing the edges of the inner circle.
alpar@825:   std::vector<typename Graph::Edge> incir;
alpar@825:   ///Vector containing the edges of the outer circle.
alpar@825:   std::vector<typename Graph::Edge> outcir;
alpar@825:   ///Vector containing the chord edges.
alpar@825:   std::vector<typename Graph::Edge> chords;
alpar@574: };
alpar@574: 
alpar@721: 
alpar@721: 
alpar@574: ///Adds a Petersen graph to \c G.
alpar@574: 
alpar@574: ///Adds a Petersen graph to \c G.
deba@937: ///\return The nodes and edges of the generated graph.
alpar@721: 
alpar@721: template<typename Graph>
klao@946: PetStruct<Graph> addPetersen(Graph &G,int num = 5)
alpar@574: {
alpar@574:   PetStruct<Graph> n;
alpar@574: 
alpar@574:   for(int i=0;i<num;i++) {
alpar@574:     n.outer.push_back(G.addNode());
alpar@574:     n.inner.push_back(G.addNode());
alpar@574:   }
alpar@574: 
alpar@574:  for(int i=0;i<num;i++) {
alpar@574:    n.chords.push_back(G.addEdge(n.outer[i],n.inner[i]));
klao@946:    n.outcir.push_back(G.addEdge(n.outer[i],n.outer[(i+1) % num]));
klao@946:    n.incir.push_back(G.addEdge(n.inner[i],n.inner[(i+2) % num]));
alpar@574:   }
alpar@574:  return n;
alpar@574: }
alpar@574: 
alpar@1200: /// \brief Adds to the graph the reverse pair of all edges.
klao@946: ///
alpar@1200: /// Adds to the graph the reverse pair of all edges.
klao@946: ///
klao@946: template<class Graph> void bidirGraph(Graph &G)
klao@946: {
klao@946:   typedef typename Graph::Edge Edge;
klao@946:   typedef typename Graph::EdgeIt EdgeIt;
klao@946:   
klao@946:   std::vector<Edge> ee;
klao@946:   
klao@946:   for(EdgeIt e(G);e!=INVALID;++e) ee.push_back(e);
klao@946: 
klao@946:   for(typename std::vector<Edge>::iterator p=ee.begin();p!=ee.end();p++)
alpar@986:     G.addEdge(G.target(*p),G.source(*p));
klao@946: }
klao@946: 
klao@946: 
klao@946: /// \brief Checks the bidirectioned Petersen graph.
klao@946: ///
klao@946: ///  Checks the bidirectioned Petersen graph.
klao@946: ///
klao@946: template<class Graph> void checkBidirPetersen(Graph &G, int num = 5)
klao@946: {
klao@946:   typedef typename Graph::Node Node;
klao@946: 
klao@946:   typedef typename Graph::EdgeIt EdgeIt;
klao@946:   typedef typename Graph::NodeIt NodeIt;
klao@946: 
klao@946:   checkGraphNodeList(G, 2 * num);
klao@946:   checkGraphEdgeList(G, 6 * num);
klao@946: 
klao@946:   for(NodeIt n(G);n!=INVALID;++n) {
klao@946:     checkGraphInEdgeList(G, n, 3);
klao@946:     checkGraphOutEdgeList(G, n, 3);
klao@946:   }  
klao@946: }
klao@946: 
klao@1909: ///Structure returned by \ref addUPetersen().
alpar@574: 
klao@1909: ///Structure returned by \ref addUPetersen().
deba@937: ///
klao@1909: template<class Graph> struct UPetStruct
deba@937: {
deba@937:   ///Vector containing the outer nodes.
deba@937:   std::vector<typename Graph::Node> outer;
deba@937:   ///Vector containing the inner nodes.
deba@937:   std::vector<typename Graph::Node> inner;
deba@937:   ///Vector containing the edges of the inner circle.
klao@1909:   std::vector<typename Graph::UEdge> incir;
deba@937:   ///Vector containing the edges of the outer circle.
klao@1909:   std::vector<typename Graph::UEdge> outcir;
deba@937:   ///Vector containing the chord edges.
klao@1909:   std::vector<typename Graph::UEdge> chords;
deba@937: };
deba@937: 
alpar@1716: ///Adds a Petersen graph to the undirected \c G.
deba@937: 
alpar@1716: ///Adds a Petersen graph to the undirected \c G.
deba@937: ///\return The nodes and edges of the generated graph.
deba@937: 
deba@937: template<typename Graph>
klao@1909: UPetStruct<Graph> addUPetersen(Graph &G,int num=5)
deba@937: {
klao@1909:   UPetStruct<Graph> n;
deba@937: 
deba@937:   for(int i=0;i<num;i++) {
deba@937:     n.outer.push_back(G.addNode());
deba@937:     n.inner.push_back(G.addNode());
deba@937:   }
deba@937: 
deba@937:  for(int i=0;i<num;i++) {
deba@937:    n.chords.push_back(G.addEdge(n.outer[i],n.inner[i]));
deba@937:    n.outcir.push_back(G.addEdge(n.outer[i],n.outer[(i+1)%5]));
deba@937:    n.incir.push_back(G.addEdge(n.inner[i],n.inner[(i+2)%5]));
deba@2242:  }
deba@937:  return n;
deba@937: }
alpar@574: 
alpar@574: #endif