COIN-OR::LEMON - Graph Library

source: lemon-main/test/graph_test.h @ 227:33f8d69e642a

Last change on this file since 227:33f8d69e642a was 220:a5d8c039f218, checked in by Balazs Dezso <deba@…>, 16 years ago

Reorganize header files (Ticket #97)

In addition on some places the DefaultMap?<G, K, V> is replaced with
ItemSetTraits?<G, K>::template Map<V>::Type, to decrease the dependencies
of different tools. It is obviously better solution.

File size: 7.2 KB
Line 
1/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library.
4 *
5 * Copyright (C) 2003-2008
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/core.h>
23#include "test_tools.h"
24
25namespace lemon {
26
27  template<class Graph>
28  void checkGraphNodeList(const Graph &G, int cnt)
29  {
30    typename Graph::NodeIt n(G);
31    for(int i=0;i<cnt;i++) {
32      check(n!=INVALID,"Wrong Node list linking.");
33      ++n;
34    }
35    check(n==INVALID,"Wrong Node list linking.");
36    check(countNodes(G)==cnt,"Wrong Node number.");
37  }
38
39  template<class Graph>
40  void checkGraphArcList(const Graph &G, int cnt)
41  {
42    typename Graph::ArcIt e(G);
43    for(int i=0;i<cnt;i++) {
44      check(e!=INVALID,"Wrong Arc list linking.");
45      ++e;
46    }
47    check(e==INVALID,"Wrong Arc list linking.");
48    check(countArcs(G)==cnt,"Wrong Arc number.");
49  }
50
51  template<class Graph>
52  void checkGraphOutArcList(const Graph &G, typename Graph::Node n, int cnt)
53  {
54    typename Graph::OutArcIt e(G,n);
55    for(int i=0;i<cnt;i++) {
56      check(e!=INVALID,"Wrong OutArc list linking.");
57      check(n==G.source(e),"Wrong OutArc list linking.");
58      ++e;
59    }
60    check(e==INVALID,"Wrong OutArc list linking.");
61    check(countOutArcs(G,n)==cnt,"Wrong OutArc number.");
62  }
63
64  template<class Graph>
65  void checkGraphInArcList(const Graph &G, typename Graph::Node n, int cnt)
66  {
67    typename Graph::InArcIt e(G,n);
68    for(int i=0;i<cnt;i++) {
69      check(e!=INVALID,"Wrong InArc list linking.");
70      check(n==G.target(e),"Wrong InArc list linking.");
71      ++e;
72    }
73    check(e==INVALID,"Wrong InArc list linking.");
74    check(countInArcs(G,n)==cnt,"Wrong InArc number.");
75  }
76
77  template<class Graph>
78  void checkGraphEdgeList(const Graph &G, int cnt)
79  {
80    typename Graph::EdgeIt e(G);
81    for(int i=0;i<cnt;i++) {
82      check(e!=INVALID,"Wrong Edge list linking.");
83      ++e;
84    }
85    check(e==INVALID,"Wrong Edge list linking.");
86    check(countEdges(G)==cnt,"Wrong Edge number.");
87  }
88
89  template<class Graph>
90  void checkGraphIncEdgeList(const Graph &G, typename Graph::Node n, int cnt)
91  {
92    typename Graph::IncEdgeIt e(G,n);
93    for(int i=0;i<cnt;i++) {
94      check(e!=INVALID,"Wrong IncEdge list linking.");
95      check(n==G.u(e) || n==G.v(e),"Wrong IncEdge list linking.");
96      ++e;
97    }
98    check(e==INVALID,"Wrong IncEdge list linking.");
99    check(countIncEdges(G,n)==cnt,"Wrong IncEdge number.");
100  }
101
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
112  template <class Graph>
113  void checkGraphIterators() {
114    checkDigraphIterators<Graph>();
115    typedef typename Graph::Edge Edge;
116    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  }
259
260} //namespace lemon
261
262#endif
Note: See TracBrowser for help on using the repository browser.