COIN-OR::LEMON - Graph Library

source: lemon/test/digraph_test.h @ 82:bce6c8f93d10

Last change on this file since 82:bce6c8f93d10 was 57:c1acf0018c0a, checked in by Balazs Dezso <deba@…>, 17 years ago

Port ListDigraph? and ListGraph? from svn -r 3433
Details:

  • port Digraph and Graph concepts
  • port ListDigraph? and ListGraph?
  • port Basic graph constructing tools
  • port Digraph and Graph tests
File size: 4.9 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2007
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_TEST_GRAPH_TEST_H
20#define LEMON_TEST_GRAPH_TEST_H
21
22//#include <lemon/graph_utils.h>
23#include "test_tools.h"
24
25//! \ingroup misc
26//! \file
27//! \brief Some utility and test cases to test digraph classes.
28namespace lemon {
29
30  ///Structure returned by \ref addPetersen().
31
32  ///Structure returned by \ref addPetersen().
33  ///
34  template<class Digraph>
35  struct PetStruct
36  {
37    ///Vector containing the outer nodes.
38    std::vector<typename Digraph::Node> outer;
39    ///Vector containing the inner nodes.
40    std::vector<typename Digraph::Node> inner;
41    ///Vector containing the edges of the inner circle.
42    std::vector<typename Digraph::Arc> incir;
43    ///Vector containing the edges of the outer circle.
44    std::vector<typename Digraph::Arc> outcir;
45    ///Vector containing the chord edges.
46    std::vector<typename Digraph::Arc> chords;
47  };
48
49
50
51  ///Adds a Petersen graph to \c G.
52
53  ///Adds a Petersen graph to \c G.
54  ///\return The nodes and edges of the generated graph.
55
56  template<typename Digraph>
57  PetStruct<Digraph> addPetersen(Digraph &G,int num = 5)
58  {
59    PetStruct<Digraph> n;
60
61    for(int i=0;i<num;i++) {
62      n.outer.push_back(G.addNode());
63      n.inner.push_back(G.addNode());
64    }
65
66    for(int i=0;i<num;i++) {
67      n.chords.push_back(G.addArc(n.outer[i],n.inner[i]));
68      n.outcir.push_back(G.addArc(n.outer[i],n.outer[(i+1) % num]));
69      n.incir.push_back(G.addArc(n.inner[i],n.inner[(i+2) % num]));
70    }
71    return n;
72  }
73
74  /// \brief Adds to the digraph the reverse pair of all edges.
75  ///
76  /// Adds to the digraph the reverse pair of all edges.
77  ///
78  template<class Digraph>
79  void bidirDigraph(Digraph &G)
80  {
81    typedef typename Digraph::Arc Arc;
82    typedef typename Digraph::ArcIt ArcIt;
83 
84    std::vector<Arc> ee;
85 
86    for(ArcIt e(G);e!=INVALID;++e) ee.push_back(e);
87
88    for(typename std::vector<Arc>::iterator p=ee.begin();p!=ee.end();p++)
89      G.addArc(G.target(*p),G.source(*p));
90  }
91
92
93  /// \brief Checks the bidirectioned Petersen graph.
94  ///
95  ///  Checks the bidirectioned Petersen graph.
96  ///
97  template<class Digraph>
98  void checkBidirPetersen(Digraph &G, int num = 5)
99  {
100    typedef typename Digraph::Node Node;
101
102    typedef typename Digraph::ArcIt ArcIt;
103    typedef typename Digraph::NodeIt NodeIt;
104
105    checkDigraphNodeList(G, 2 * num);
106    checkDigraphArcList(G, 6 * num);
107
108    for(NodeIt n(G);n!=INVALID;++n) {
109      checkDigraphInArcList(G, n, 3);
110      checkDigraphOutArcList(G, n, 3);
111    } 
112  }
113
114  template<class Digraph> void checkDigraphNodeList(Digraph &G, int nn)
115  {
116    typename Digraph::NodeIt n(G);
117    for(int i=0;i<nn;i++) {
118      check(n!=INVALID,"Wrong Node list linking.");
119      ++n;
120    }
121    check(n==INVALID,"Wrong Node list linking.");
122  }
123
124  template<class Digraph>
125  void checkDigraphArcList(Digraph &G, int nn)
126  {
127    typedef typename Digraph::ArcIt ArcIt;
128
129    ArcIt e(G);
130    for(int i=0;i<nn;i++) {
131      check(e!=INVALID,"Wrong Arc list linking.");
132      ++e;
133    }
134    check(e==INVALID,"Wrong Arc list linking.");
135  }
136
137  template<class Digraph>
138  void checkDigraphOutArcList(Digraph &G, typename Digraph::Node n, int nn)
139  {
140    typename Digraph::OutArcIt e(G,n);
141    for(int i=0;i<nn;i++) {
142      check(e!=INVALID,"Wrong OutArc list linking.");
143      check(n==G.source(e), "Wrong OutArc list linking.");
144      ++e;
145    }
146    check(e==INVALID,"Wrong OutArc list linking.");
147  }
148
149  template<class Digraph> void
150  checkDigraphInArcList(Digraph &G, typename Digraph::Node n, int nn)
151  {
152    typename Digraph::InArcIt e(G,n);
153    for(int i=0;i<nn;i++) {
154      check(e!=INVALID,"Wrong InArc list linking.");
155      check(n==G.target(e), "Wrong InArc list linking.");
156      ++e;
157    }
158    check(e==INVALID,"Wrong InArc list linking.");
159  }
160
161  template <class Digraph>
162  void checkDigraph() {
163    const int num = 5;
164    Digraph G;
165    addPetersen(G, num);
166    bidirDigraph(G);
167    checkBidirPetersen(G, num);
168  }
169
170  template <class Digraph>
171  void checkDigraphIterators(const Digraph& digraph) {
172    typedef typename Digraph::Node Node;
173    typedef typename Digraph::NodeIt NodeIt;
174    typedef typename Digraph::Arc Arc;
175    typedef typename Digraph::ArcIt ArcIt;
176    typedef typename Digraph::InArcIt InArcIt;
177    typedef typename Digraph::OutArcIt OutArcIt;
178    //    typedef ConArcIt<Digraph> ConArcIt;
179  }
180
181  ///\file
182  ///\todo Check target(), source() as well;
183
184 
185} //namespace lemon
186
187
188#endif
Note: See TracBrowser for help on using the repository browser.