/* -*- C++ -*- * * This file is a part of LEMON, a generic C++ optimization library * * Copyright (C) 2003-2008 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * * Permission to use, modify and distribute this software is granted * provided that this copyright notice appears in all copies. For * precise terms see the accompanying LICENSE file. * * This software is provided "AS IS" with no warranty of any kind, * express or implied, and with no claim as to its suitability for any * purpose. * */ #ifndef LEMON_TEST_GRAPH_TEST_H #define LEMON_TEST_GRAPH_TEST_H //#include #include "test_tools.h" //! \ingroup misc //! \file //! \brief Some utility and test cases to test digraph classes. namespace lemon { ///Structure returned by \ref addPetersen(). ///Structure returned by \ref addPetersen(). /// template struct PetStruct { ///Vector containing the outer nodes. std::vector outer; ///Vector containing the inner nodes. std::vector inner; ///Vector containing the edges of the inner circle. std::vector incir; ///Vector containing the edges of the outer circle. std::vector outcir; ///Vector containing the chord edges. std::vector chords; }; ///Adds a Petersen graph to \c G. ///Adds a Petersen graph to \c G. ///\return The nodes and edges of the generated graph. template PetStruct addPetersen(Digraph &G,int num = 5) { PetStruct n; for(int i=0;i void bidirDigraph(Digraph &G) { typedef typename Digraph::Arc Arc; typedef typename Digraph::ArcIt ArcIt; std::vector ee; for(ArcIt e(G);e!=INVALID;++e) ee.push_back(e); for(typename std::vector::iterator p=ee.begin();p!=ee.end();p++) G.addArc(G.target(*p),G.source(*p)); } /// \brief Checks the bidirectioned Petersen graph. /// /// Checks the bidirectioned Petersen graph. /// template void checkBidirPetersen(Digraph &G, int num = 5) { typedef typename Digraph::Node Node; typedef typename Digraph::ArcIt ArcIt; typedef typename Digraph::NodeIt NodeIt; checkDigraphNodeList(G, 2 * num); checkDigraphArcList(G, 6 * num); for(NodeIt n(G);n!=INVALID;++n) { checkDigraphInArcList(G, n, 3); checkDigraphOutArcList(G, n, 3); } } template void checkDigraphNodeList(Digraph &G, int nn) { typename Digraph::NodeIt n(G); for(int i=0;i void checkDigraphArcList(Digraph &G, int nn) { typedef typename Digraph::ArcIt ArcIt; ArcIt e(G); for(int i=0;i void checkDigraphOutArcList(Digraph &G, typename Digraph::Node n, int nn) { typename Digraph::OutArcIt e(G,n); for(int i=0;i void checkDigraphInArcList(Digraph &G, typename Digraph::Node n, int nn) { typename Digraph::InArcIt e(G,n); for(int i=0;i void checkDigraph() { const int num = 5; Digraph G; addPetersen(G, num); bidirDigraph(G); checkBidirPetersen(G, num); } template void checkDigraphIterators(const Digraph& digraph) { typedef typename Digraph::Node Node; typedef typename Digraph::NodeIt NodeIt; typedef typename Digraph::Arc Arc; typedef typename Digraph::ArcIt ArcIt; typedef typename Digraph::InArcIt InArcIt; typedef typename Digraph::OutArcIt OutArcIt; // typedef ConArcIt ConArcIt; } ///\file ///\todo Check target(), source() as well; } //namespace lemon #endif