COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 228:b6732e0d38c5 in lemon for test/graph_test.h


Ignore:
Timestamp:
07/21/08 16:30:28 (16 years ago)
Author:
Balazs Dezso <deba@…>
Branch:
default
Children:
229:aebc0161f6e5, 230:af4e8ba94294
Phase:
public
Message:

Reworking graph testing

  • The graph tests check more graph functionality.
  • The petersen graph is too regular, therefore special graphs are used.
  • The graph_test.h contains just general tools to test graphs.
File:
1 edited

Legend:

Unmodified
Added
Removed

  • test/graph_test.h

    r220 r228  
    2020#define LEMON_TEST_GRAPH_TEST_H
    2121
     22#include <set>
     23
    2224#include <lemon/core.h>
     25#include <lemon/maps.h>
     26
    2327#include "test_tools.h"
    2428
    … …  
    4347    for(int i=0;i<cnt;i++) {
    4448      check(e!=INVALID,"Wrong Arc list linking.");
     49      check(G.oppositeNode(G.source(e), e) == G.target(e),
     50            "Wrong opposite node");
     51      check(G.oppositeNode(G.target(e), e) == G.source(e),
     52            "Wrong opposite node");
    4553      ++e;
    4654    }
    … …  
    5664      check(e!=INVALID,"Wrong OutArc list linking.");
    5765      check(n==G.source(e),"Wrong OutArc list linking.");
     66      check(n==G.baseNode(e),"Wrong OutArc list linking.");
     67      check(G.target(e)==G.runningNode(e),"Wrong OutArc list linking.");
    5868      ++e;
    5969    }
    … …  
    6979      check(e!=INVALID,"Wrong InArc list linking.");
    7080      check(n==G.target(e),"Wrong InArc list linking.");
     81      check(n==G.baseNode(e),"Wrong OutArc list linking.");
     82      check(G.source(e)==G.runningNode(e),"Wrong OutArc list linking.");
    7183      ++e;
    7284    }
    … …  
    8193    for(int i=0;i<cnt;i++) {
    8294      check(e!=INVALID,"Wrong Edge list linking.");
     95      check(G.oppositeNode(G.u(e), e) == G.v(e), "Wrong opposite node");
     96      check(G.oppositeNode(G.v(e), e) == G.u(e), "Wrong opposite node");
    8397      ++e;
    8498    }
    … …  
    94108      check(e!=INVALID,"Wrong IncEdge list linking.");
    95109      check(n==G.u(e) || n==G.v(e),"Wrong IncEdge list linking.");
     110      check(n==G.baseNode(e),"Wrong OutArc list linking.");
     111      check(G.u(e)==G.runningNode(e) || G.v(e)==G.runningNode(e),
     112            "Wrong OutArc list linking.");
    96113      ++e;
    97114    }
    … …  
    100117  }
    101118
    102   template <class Digraph>
    103   void checkDigraphIterators() {
    104     typedef typename Digraph::Node Node;
    105     typedef typename Digraph::NodeIt NodeIt;
    106     typedef typename Digraph::Arc Arc;
    107     typedef typename Digraph::ArcIt ArcIt;
    108     typedef typename Digraph::InArcIt InArcIt;
    109     typedef typename Digraph::OutArcIt OutArcIt;
    110   }
    111 
    112119  template <class Graph>
    113   void checkGraphIterators() {
    114     checkDigraphIterators<Graph>();
     120  void checkGraphConArcList(const Graph &G, int cnt) {
     121    int i = 0;
     122    for (typename Graph::NodeIt u(G); u != INVALID; ++u) {
     123      for (typename Graph::NodeIt v(G); v != INVALID; ++v) {
     124        for (ConArcIt<Graph> a(G, u, v); a != INVALID; ++a) {
     125          check(G.source(a) == u, "Wrong iterator.");
     126          check(G.target(a) == v, "Wrong iterator.");
     127          ++i;
     128        }
     129      }
     130    }
     131    check(cnt == i, "Wrong iterator.");
     132  }
     133
     134  template <class Graph>
     135  void checkGraphConEdgeList(const Graph &G, int cnt) {
     136    int i = 0;
     137    for (typename Graph::NodeIt u(G); u != INVALID; ++u) {
     138      for (typename Graph::NodeIt v(G); v != INVALID; ++v) {
     139        for (ConEdgeIt<Graph> e(G, u, v); e != INVALID; ++e) {
     140          check((G.u(e) == u && G.v(e) == v) ||
     141                (G.u(e) == v && G.v(e) == u), "Wrong iterator.");
     142          i += u == v ? 2 : 1;
     143        }
     144      }
     145    }
     146    check(2 * cnt == i, "Wrong iterator.");
     147  }
     148
     149  template <typename Graph>
     150  void checkArcDirections(const Graph& G) {
     151    for (typename Graph::ArcIt a(G); a != INVALID; ++a) {
     152      check(G.source(a) == G.target(G.oppositeArc(a)), "Wrong direction");
     153      check(G.target(a) == G.source(G.oppositeArc(a)), "Wrong direction");
     154      check(G.direct(a, G.direction(a)) == a, "Wrong direction");
     155    }
     156  }
     157
     158  template <typename Graph>
     159  void checkNodeIds(const Graph& G) {
     160    std::set<int> values;
     161    for (typename Graph::NodeIt n(G); n != INVALID; ++n) {
     162      check(G.nodeFromId(G.id(n)) == n, "Wrong id");
     163      check(values.find(G.id(n)) == values.end(), "Wrong id");
     164      check(G.id(n) <= G.maxNodeId(), "Wrong maximum id");
     165      values.insert(G.id(n));
     166    }
     167  }
     168
     169  template <typename Graph>
     170  void checkArcIds(const Graph& G) {
     171    std::set<int> values;
     172    for (typename Graph::ArcIt a(G); a != INVALID; ++a) {
     173      check(G.arcFromId(G.id(a)) == a, "Wrong id");
     174      check(values.find(G.id(a)) == values.end(), "Wrong id");
     175      check(G.id(a) <= G.maxArcId(), "Wrong maximum id");
     176      values.insert(G.id(a));
     177    }
     178  }
     179
     180  template <typename Graph>
     181  void checkEdgeIds(const Graph& G) {
     182    std::set<int> values;
     183    for (typename Graph::EdgeIt e(G); e != INVALID; ++e) {
     184      check(G.edgeFromId(G.id(e)) == e, "Wrong id");
     185      check(values.find(G.id(e)) == values.end(), "Wrong id");
     186      check(G.id(e) <= G.maxEdgeId(), "Wrong maximum id");
     187      values.insert(G.id(e));
     188    }
     189  }
     190
     191  template <typename Graph>
     192  void checkGraphNodeMap(const Graph& G) {
     193    typedef typename Graph::Node Node;
     194    typedef typename Graph::NodeIt NodeIt;
     195
     196    typedef typename Graph::template NodeMap<int> IntNodeMap;
     197    IntNodeMap map(G, 42);
     198    for (NodeIt it(G); it != INVALID; ++it) {
     199      check(map[it] == 42, "Wrong map constructor.");
     200    }
     201    int s = 0;
     202    for (NodeIt it(G); it != INVALID; ++it) {
     203      map[it] = 0;
     204      check(map[it] == 0, "Wrong operator[].");
     205      map.set(it, s);
     206      check(map[it] == s, "Wrong set.");
     207      ++s;
     208    }
     209    s = s * (s - 1) / 2;
     210    for (NodeIt it(G); it != INVALID; ++it) {
     211      s -= map[it];
     212    }
     213    check(s == 0, "Wrong sum.");
     214
     215    map = constMap<Node>(12);
     216    for (NodeIt it(G); it != INVALID; ++it) {
     217      check(map[it] == 12, "Wrong operator[].");
     218    }
     219  }
     220
     221  template <typename Graph>
     222  void checkGraphArcMap(const Graph& G) {
     223    typedef typename Graph::Arc Arc;
     224    typedef typename Graph::ArcIt ArcIt;
     225
     226    typedef typename Graph::template ArcMap<int> IntArcMap;
     227    IntArcMap map(G, 42);
     228    for (ArcIt it(G); it != INVALID; ++it) {
     229      check(map[it] == 42, "Wrong map constructor.");
     230    }
     231    int s = 0;
     232    for (ArcIt it(G); it != INVALID; ++it) {
     233      map[it] = 0;
     234      check(map[it] == 0, "Wrong operator[].");
     235      map.set(it, s);
     236      check(map[it] == s, "Wrong set.");
     237      ++s;
     238    }
     239    s = s * (s - 1) / 2;
     240    for (ArcIt it(G); it != INVALID; ++it) {
     241      s -= map[it];
     242    }
     243    check(s == 0, "Wrong sum.");
     244
     245    map = constMap<Arc>(12);
     246    for (ArcIt it(G); it != INVALID; ++it) {
     247      check(map[it] == 12, "Wrong operator[].");
     248    }
     249  }
     250
     251  template <typename Graph>
     252  void checkGraphEdgeMap(const Graph& G) {
    115253    typedef typename Graph::Edge Edge;
    116254    typedef typename Graph::EdgeIt EdgeIt;
    117     typedef typename Graph::IncEdgeIt IncEdgeIt;
    118   }
    119 
    120   // Structure returned by addPetersen()
    121   template<class Digraph>
    122   struct PetStruct
    123   {
    124     // Vector containing the outer nodes
    125     std::vector<typename Digraph::Node> outer;
    126     // Vector containing the inner nodes
    127     std::vector<typename Digraph::Node> inner;
    128     // Vector containing the arcs of the inner circle
    129     std::vector<typename Digraph::Arc> incir;
    130     // Vector containing the arcs of the outer circle
    131     std::vector<typename Digraph::Arc> outcir;
    132     // Vector containing the chord arcs
    133     std::vector<typename Digraph::Arc> chords;
    134   };
    135 
    136   // Adds the reverse pair of all arcs to a digraph
    137   template<class Digraph>
    138   void bidirDigraph(Digraph &G)
    139   {
    140     typedef typename Digraph::Arc Arc;
    141     typedef typename Digraph::ArcIt ArcIt;
    142 
    143     std::vector<Arc> ee;
    144 
    145     for(ArcIt e(G);e!=INVALID;++e) ee.push_back(e);
    146 
    147     for(int i=0;i<int(ee.size());++i)
    148       G.addArc(G.target(ee[i]),G.source(ee[i]));
    149   }
    150 
    151   // Adds a Petersen digraph to G.
    152   // Returns the nodes and arcs of the generated digraph.
    153   template<typename Digraph>
    154   PetStruct<Digraph> addPetersen(Digraph &G,int num = 5)
    155   {
    156     PetStruct<Digraph> n;
    157 
    158     for(int i=0;i<num;i++) {
    159       n.outer.push_back(G.addNode());
    160       n.inner.push_back(G.addNode());
    161     }
    162 
    163     for(int i=0;i<num;i++) {
    164       n.chords.push_back(G.addArc(n.outer[i],n.inner[i]));
    165       n.outcir.push_back(G.addArc(n.outer[i],n.outer[(i+1) % num]));
    166       n.incir.push_back(G.addArc(n.inner[i],n.inner[(i+2) % num]));
    167     }
    168 
    169     return n;
    170   }
    171 
    172   // Checks the bidirectioned Petersen digraph
    173   template<class Digraph>
    174   void checkBidirPetersen(const Digraph &G, int num = 5)
    175   {
    176     typedef typename Digraph::NodeIt NodeIt;
    177 
    178     checkGraphNodeList(G, 2 * num);
    179     checkGraphArcList(G, 6 * num);
    180 
    181     for(NodeIt n(G);n!=INVALID;++n) {
    182       checkGraphInArcList(G, n, 3);
    183       checkGraphOutArcList(G, n, 3);
    184     }
    185   }
    186 
    187   // Structure returned by addUPetersen()
    188   template<class Graph>
    189   struct UPetStruct
    190   {
    191     // Vector containing the outer nodes
    192     std::vector<typename Graph::Node> outer;
    193     // Vector containing the inner nodes
    194     std::vector<typename Graph::Node> inner;
    195     // Vector containing the edges of the inner circle
    196     std::vector<typename Graph::Edge> incir;
    197     // Vector containing the edges of the outer circle
    198     std::vector<typename Graph::Edge> outcir;
    199     // Vector containing the chord edges
    200     std::vector<typename Graph::Edge> chords;
    201   };
    202 
    203   // Adds a Petersen graph to \c G.
    204   // Returns the nodes and edges of the generated graph.
    205   template<typename Graph>
    206   UPetStruct<Graph> addUPetersen(Graph &G,int num=5)
    207   {
    208     UPetStruct<Graph> n;
    209 
    210     for(int i=0;i<num;i++) {
    211       n.outer.push_back(G.addNode());
    212       n.inner.push_back(G.addNode());
    213     }
    214 
    215     for(int i=0;i<num;i++) {
    216       n.chords.push_back(G.addEdge(n.outer[i],n.inner[i]));
    217       n.outcir.push_back(G.addEdge(n.outer[i],n.outer[(i+1)%num]));
    218       n.incir.push_back(G.addEdge(n.inner[i],n.inner[(i+2)%num]));
    219     }
    220 
    221     return n;
    222   }
    223 
    224   // Checks the undirected Petersen graph
    225   template<class Graph>
    226   void checkUndirPetersen(const Graph &G, int num = 5)
    227   {
    228     typedef typename Graph::NodeIt NodeIt;
    229 
    230     checkGraphNodeList(G, 2 * num);
    231     checkGraphEdgeList(G, 3 * num);
    232     checkGraphArcList(G, 6 * num);
    233 
    234     for(NodeIt n(G);n!=INVALID;++n) {
    235       checkGraphIncEdgeList(G, n, 3);
    236     }
    237   }
    238 
    239   template <class Digraph>
    240   void checkDigraph() {
    241     const int num = 5;
    242     Digraph G;
    243     checkGraphNodeList(G, 0);
    244     checkGraphArcList(G, 0);
    245     addPetersen(G, num);
    246     bidirDigraph(G);
    247     checkBidirPetersen(G, num);
    248   }
    249 
    250   template <class Graph>
    251   void checkGraph() {
    252     const int num = 5;
    253     Graph G;
    254     checkGraphNodeList(G, 0);
    255     checkGraphEdgeList(G, 0);
    256     addUPetersen(G, num);
    257     checkUndirPetersen(G, num);
    258   }
     255
     256    typedef typename Graph::template EdgeMap<int> IntEdgeMap;
     257    IntEdgeMap map(G, 42);
     258    for (EdgeIt it(G); it != INVALID; ++it) {
     259      check(map[it] == 42, "Wrong map constructor.");
     260    }
     261    int s = 0;
     262    for (EdgeIt it(G); it != INVALID; ++it) {
     263      map[it] = 0;
     264      check(map[it] == 0, "Wrong operator[].");
     265      map.set(it, s);
     266      check(map[it] == s, "Wrong set.");
     267      ++s;
     268    }
     269    s = s * (s - 1) / 2;
     270    for (EdgeIt it(G); it != INVALID; ++it) {
     271      s -= map[it];
     272    }
     273    check(s == 0, "Wrong sum.");
     274
     275    map = constMap<Edge>(12);
     276    for (EdgeIt it(G); it != INVALID; ++it) {
     277      check(map[it] == 12, "Wrong operator[].");
     278    }
     279  }
     280
    259281
    260282} //namespace lemon
Note: See TracChangeset for help on using the changeset viewer.