alpar@4: /* -*- C++ -*-
alpar@4:  *
alpar@4:  * This file is a part of LEMON, a generic C++ optimization library
alpar@4:  *
alpar@39:  * Copyright (C) 2003-2008
alpar@4:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@4:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@4:  *
alpar@4:  * Permission to use, modify and distribute this software is granted
alpar@4:  * provided that this copyright notice appears in all copies. For
alpar@4:  * precise terms see the accompanying LICENSE file.
alpar@4:  *
alpar@4:  * This software is provided "AS IS" with no warranty of any kind,
alpar@4:  * express or implied, and with no claim as to its suitability for any
alpar@4:  * purpose.
alpar@4:  *
alpar@4:  */
alpar@4: 
alpar@4: #ifndef LEMON_TEST_TEST_TOOLS_H
alpar@4: #define LEMON_TEST_TEST_TOOLS_H
alpar@4: 
alpar@4: #include <iostream>
alpar@100: #include <vector>
alpar@100: 
alpar@100: #include <cstdlib>
alpar@100: #include <ctime>
alpar@100: 
alpar@100: #include <lemon/concept_check.h>
alpar@100: #include <lemon/concepts/digraph.h>
alpar@100: 
alpar@100: #include <lemon/random.h>
alpar@100: 
alpar@100: using namespace lemon;
alpar@4: 
alpar@4: //! \ingroup misc
alpar@4: //! \file
alpar@4: //! \brief Some utilities to write test programs.
alpar@4: 
alpar@4: 
alpar@4: ///If \c rc is fail, writes an error message end exit.
alpar@4: 
alpar@4: ///If \c rc is fail, writes an error message end exit.
alpar@4: ///The error message contains the file name and the line number of the
alpar@4: ///source code in a standard from, which makes it possible to go there
alpar@4: ///using good source browsers like e.g. \c emacs.
alpar@4: ///
alpar@4: ///For example
alpar@4: ///\code check(0==1,"This is obviously false.");\endcode will
alpar@4: ///print this (and then exits).
alpar@100: ///\verbatim digraph_test.cc:123: error: This is obviously false. \endverbatim
alpar@4: ///
alpar@4: ///\todo It should be in \c error.h
alpar@4: #define check(rc, msg) \
alpar@4:   if(!(rc)) { \
alpar@4:     std::cerr << __FILE__ ":" << __LINE__ << ": error: " << msg << std::endl; \
alpar@4:     abort(); \
alpar@4:   } else { } \
alpar@4: 
alpar@100: ///Structure returned by \ref addPetersen().
alpar@100: 
alpar@100: ///Structure returned by \ref addPetersen().
alpar@100: ///
alpar@100: template<class Digraph> struct PetStruct
alpar@100: {
alpar@100:   ///Vector containing the outer nodes.
alpar@100:   std::vector<typename Digraph::Node> outer;
alpar@100:   ///Vector containing the inner nodes.
alpar@100:   std::vector<typename Digraph::Node> inner;
alpar@100:   ///Vector containing the arcs of the inner circle.
alpar@100:   std::vector<typename Digraph::Arc> incir;
alpar@100:   ///Vector containing the arcs of the outer circle.
alpar@100:   std::vector<typename Digraph::Arc> outcir;
alpar@100:   ///Vector containing the chord arcs.
alpar@100:   std::vector<typename Digraph::Arc> chords;
alpar@100: };
alpar@100: 
alpar@100: 
alpar@100: 
alpar@100: ///Adds a Petersen digraph to \c G.
alpar@100: 
alpar@100: ///Adds a Petersen digraph to \c G.
alpar@100: ///\return The nodes and arcs of the generated digraph.
alpar@100: 
alpar@100: template<typename Digraph>
alpar@100: PetStruct<Digraph> addPetersen(Digraph &G,int num = 5)
alpar@100: {
alpar@100:   PetStruct<Digraph> n;
alpar@100: 
alpar@100:   for(int i=0;i<num;i++) {
alpar@100:     n.outer.push_back(G.addNode());
alpar@100:     n.inner.push_back(G.addNode());
alpar@100:   }
alpar@100: 
alpar@100:  for(int i=0;i<num;i++) {
alpar@100:    n.chords.push_back(G.addArc(n.outer[i],n.inner[i]));
alpar@100:    n.outcir.push_back(G.addArc(n.outer[i],n.outer[(i+1) % num]));
alpar@100:    n.incir.push_back(G.addArc(n.inner[i],n.inner[(i+2) % num]));
alpar@100:   }
alpar@100:  return n;
alpar@100: }
alpar@100: 
alpar@100: /// \brief Adds to the digraph the reverse pair of all arcs.
alpar@100: ///
alpar@100: /// Adds to the digraph the reverse pair of all arcs.
alpar@100: ///
alpar@100: template<class Digraph> void bidirDigraph(Digraph &G)
alpar@100: {
alpar@100:   typedef typename Digraph::Arc Arc;
alpar@100:   typedef typename Digraph::ArcIt ArcIt;
alpar@100:   
alpar@100:   std::vector<Arc> ee;
alpar@100:   
alpar@100:   for(ArcIt e(G);e!=INVALID;++e) ee.push_back(e);
alpar@100: 
alpar@100:   for(typename std::vector<Arc>::iterator p=ee.begin();p!=ee.end();p++)
alpar@100:     G.addArc(G.target(*p),G.source(*p));
alpar@100: }
alpar@100: 
alpar@100: 
alpar@100: /// \brief Checks the bidirectioned Petersen digraph.
alpar@100: ///
alpar@100: ///  Checks the bidirectioned Petersen digraph.
alpar@100: ///
alpar@100: template<class Digraph> void checkBidirPetersen(Digraph &G, int num = 5)
alpar@100: {
alpar@100:   typedef typename Digraph::Node Node;
alpar@100: 
alpar@100:   typedef typename Digraph::ArcIt ArcIt;
alpar@100:   typedef typename Digraph::NodeIt NodeIt;
alpar@100: 
alpar@100:   checkDigraphNodeList(G, 2 * num);
alpar@100:   checkDigraphArcList(G, 6 * num);
alpar@100: 
alpar@100:   for(NodeIt n(G);n!=INVALID;++n) {
alpar@100:     checkDigraphInArcList(G, n, 3);
alpar@100:     checkDigraphOutArcList(G, n, 3);
alpar@100:   }  
alpar@100: }
alpar@100: 
alpar@100: ///Structure returned by \ref addUPetersen().
alpar@100: 
alpar@100: ///Structure returned by \ref addUPetersen().
alpar@100: ///
alpar@100: template<class Digraph> struct UPetStruct
alpar@100: {
alpar@100:   ///Vector containing the outer nodes.
alpar@100:   std::vector<typename Digraph::Node> outer;
alpar@100:   ///Vector containing the inner nodes.
alpar@100:   std::vector<typename Digraph::Node> inner;
alpar@100:   ///Vector containing the arcs of the inner circle.
alpar@100:   std::vector<typename Digraph::Edge> incir;
alpar@100:   ///Vector containing the arcs of the outer circle.
alpar@100:   std::vector<typename Digraph::Edge> outcir;
alpar@100:   ///Vector containing the chord arcs.
alpar@100:   std::vector<typename Digraph::Edge> chords;
alpar@100: };
alpar@100: 
alpar@100: ///Adds a Petersen digraph to the undirected \c G.
alpar@100: 
alpar@100: ///Adds a Petersen digraph to the undirected \c G.
alpar@100: ///\return The nodes and arcs of the generated digraph.
alpar@100: 
alpar@100: template<typename Digraph>
alpar@100: UPetStruct<Digraph> addUPetersen(Digraph &G,int num=5)
alpar@100: {
alpar@100:   UPetStruct<Digraph> n;
alpar@100: 
alpar@100:   for(int i=0;i<num;i++) {
alpar@100:     n.outer.push_back(G.addNode());
alpar@100:     n.inner.push_back(G.addNode());
alpar@100:   }
alpar@100: 
alpar@100:  for(int i=0;i<num;i++) {
alpar@100:    n.chords.push_back(G.addArc(n.outer[i],n.inner[i]));
alpar@100:    n.outcir.push_back(G.addArc(n.outer[i],n.outer[(i+1)%5]));
alpar@100:    n.incir.push_back(G.addArc(n.inner[i],n.inner[(i+2)%5]));
alpar@100:  }
alpar@100:  return n;
alpar@100: }
alpar@100: 
alpar@4: #endif