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