deba@57: /* -*- C++ -*- deba@57: * deba@57: * This file is a part of LEMON, a generic C++ optimization library deba@57: * deba@57: * Copyright (C) 2003-2007 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 <lemon/graph_utils.h> 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<class Digraph> deba@57: struct PetStruct deba@57: { deba@57: ///Vector containing the outer nodes. deba@57: std::vector<typename Digraph::Node> outer; deba@57: ///Vector containing the inner nodes. deba@57: std::vector<typename Digraph::Node> inner; deba@57: ///Vector containing the edges of the inner circle. deba@57: std::vector<typename Digraph::Arc> incir; deba@57: ///Vector containing the edges of the outer circle. deba@57: std::vector<typename Digraph::Arc> outcir; deba@57: ///Vector containing the chord edges. deba@57: std::vector<typename Digraph::Arc> 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<typename Digraph> deba@57: PetStruct<Digraph> addPetersen(Digraph &G,int num = 5) deba@57: { deba@57: PetStruct<Digraph> n; deba@57: deba@57: for(int i=0;i<num;i++) { deba@57: n.outer.push_back(G.addNode()); deba@57: n.inner.push_back(G.addNode()); deba@57: } deba@57: deba@57: for(int i=0;i<num;i++) { deba@57: n.chords.push_back(G.addArc(n.outer[i],n.inner[i])); deba@57: n.outcir.push_back(G.addArc(n.outer[i],n.outer[(i+1) % num])); deba@57: n.incir.push_back(G.addArc(n.inner[i],n.inner[(i+2) % num])); deba@57: } deba@57: return n; deba@57: } deba@57: deba@57: /// \brief Adds to the digraph the reverse pair of all edges. deba@57: /// deba@57: /// Adds to the digraph the reverse pair of all edges. deba@57: /// deba@57: template<class Digraph> 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<Arc> ee; deba@57: deba@57: for(ArcIt e(G);e!=INVALID;++e) ee.push_back(e); deba@57: deba@57: for(typename std::vector<Arc>::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<class Digraph> 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<class Digraph> void checkDigraphNodeList(Digraph &G, int nn) deba@57: { deba@57: typename Digraph::NodeIt n(G); deba@57: for(int i=0;i<nn;i++) { deba@57: check(n!=INVALID,"Wrong Node list linking."); deba@57: ++n; deba@57: } deba@57: check(n==INVALID,"Wrong Node list linking."); deba@57: } deba@57: deba@57: template<class Digraph> 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<nn;i++) { deba@57: check(e!=INVALID,"Wrong Arc list linking."); deba@57: ++e; deba@57: } deba@57: check(e==INVALID,"Wrong Arc list linking."); deba@57: } deba@57: deba@57: template<class Digraph> 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<nn;i++) { deba@57: check(e!=INVALID,"Wrong OutArc list linking."); deba@57: check(n==G.source(e), "Wrong OutArc list linking."); deba@57: ++e; deba@57: } deba@57: check(e==INVALID,"Wrong OutArc list linking."); deba@57: } deba@57: deba@57: template<class Digraph> 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<nn;i++) { deba@57: check(e!=INVALID,"Wrong InArc list linking."); deba@57: check(n==G.target(e), "Wrong InArc list linking."); deba@57: ++e; deba@57: } deba@57: check(e==INVALID,"Wrong InArc list linking."); deba@57: } deba@57: deba@57: template <class Digraph> 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 <class Digraph> 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<Digraph> 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