COIN-OR::LEMON - Graph Library

source: lemon/test/graph_test.cc @ 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: 5.1 KB
RevLine 
[57]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#include <lemon/concepts/graph.h>
20#include <lemon/list_graph.h>
21// #include <lemon/smart_graph.h>
22// #include <lemon/full_graph.h>
23// #include <lemon/grid_graph.h>
24
25//#include <lemon/graph_utils.h>
26
27#include "test_tools.h"
28
29
30using namespace lemon;
31using namespace lemon::concepts;
32
33void check_concepts() {
34
35  { // checking digraph components
36    checkConcept<BaseGraphComponent, BaseGraphComponent >();
37
38    checkConcept<IDableGraphComponent<>,
39      IDableGraphComponent<> >();
40
41    checkConcept<IterableGraphComponent<>,
42      IterableGraphComponent<> >();
43
44    checkConcept<MappableGraphComponent<>,
45      MappableGraphComponent<> >();
46
47  }
48  {
49    checkConcept<Graph, ListGraph>();   
50//     checkConcept<Graph, SmartGraph>();   
51//     checkConcept<Graph, FullGraph>();   
52//     checkConcept<Graph, Graph>();   
53//     checkConcept<Graph, GridGraph>();
54  }
55}
56
57template <typename Graph>
58void check_item_counts(Graph &g, int n, int e) {
59  int nn = 0;
60  for (typename Graph::NodeIt it(g); it != INVALID; ++it) {
61    ++nn;
62  }
63
64  check(nn == n, "Wrong node number.");
65  //  check(countNodes(g) == n, "Wrong node number.");
66
67  int ee = 0;
68  for (typename Graph::ArcIt it(g); it != INVALID; ++it) {
69    ++ee;
70  }
71
72  check(ee == 2*e, "Wrong arc number.");
73  //  check(countArcs(g) == 2*e, "Wrong arc number.");
74
75  int uee = 0;
76  for (typename Graph::EdgeIt it(g); it != INVALID; ++it) {
77    ++uee;
78  }
79
80  check(uee == e, "Wrong edge number.");
81  //  check(countEdges(g) == e, "Wrong edge number.");
82}
83
84template <typename Graph>
85void print_items(Graph &g) {
86
87  typedef typename Graph::NodeIt NodeIt;
88  typedef typename Graph::EdgeIt EdgeIt;
89  typedef typename Graph::ArcIt ArcIt;
90
91  std::cout << "Nodes" << std::endl;
92  int i=0;
93  for(NodeIt it(g); it!=INVALID; ++it, ++i) {
94    std::cout << "  " << i << ": " << g.id(it) << std::endl;
95  }
96
97  std::cout << "Edge" << std::endl;
98  i=0;
99  for(EdgeIt it(g); it!=INVALID; ++it, ++i) {
100    std::cout << "  " << i << ": " << g.id(it)
101         << " (" << g.id(g.source(it)) << ", " << g.id(g.target(it))
102         << ")" << std::endl;
103  }
104
105  std::cout << "Arc" << std::endl;
106  i=0;
107  for(ArcIt it(g); it!=INVALID; ++it, ++i) {
108    std::cout << "  " << i << ": " << g.id(it)
109         << " (" << g.id(g.source(it)) << ", " << g.id(g.target(it))
110         << ")" << std::endl;
111  }
112
113}
114
115template <typename Graph>
116void check_graph() {
117
118  typedef typename Graph::Node Node;
119  typedef typename Graph::Edge Edge;
120  typedef typename Graph::Arc Arc;
121  typedef typename Graph::NodeIt NodeIt;
122  typedef typename Graph::EdgeIt EdgeIt;
123  typedef typename Graph::ArcIt ArcIt;
124
125  Graph g;
126
127  check_item_counts(g,0,0);
128
129  Node
130    n1 = g.addNode(),
131    n2 = g.addNode(),
132    n3 = g.addNode();
133
134  Edge
135    e1 = g.addEdge(n1, n2),
136    e2 = g.addEdge(n2, n3);
137
138  // print_items(g);
139
140  check_item_counts(g,3,2);
141}
142
143// void checkGridGraph(const GridGraph& g, int w, int h) {
144//   check(g.width() == w, "Wrong width");
145//   check(g.height() == h, "Wrong height");
146
147//   for (int i = 0; i < w; ++i) {
148//     for (int j = 0; j < h; ++j) {
149//       check(g.col(g(i, j)) == i, "Wrong col");
150//       check(g.row(g(i, j)) == j, "Wrong row");
151//     }
152//   }
153 
154//   for (int i = 0; i < w; ++i) {
155//     for (int j = 0; j < h - 1; ++j) {
156//       check(g.source(g.down(g(i, j))) == g(i, j), "Wrong down");
157//       check(g.target(g.down(g(i, j))) == g(i, j + 1), "Wrong down");
158//     }
159//     check(g.down(g(i, h - 1)) == INVALID, "Wrong down");
160//   }
161
162//   for (int i = 0; i < w; ++i) {
163//     for (int j = 1; j < h; ++j) {
164//       check(g.source(g.up(g(i, j))) == g(i, j), "Wrong up");
165//       check(g.target(g.up(g(i, j))) == g(i, j - 1), "Wrong up");
166//     }
167//     check(g.up(g(i, 0)) == INVALID, "Wrong up");
168//   }
169
170//   for (int j = 0; j < h; ++j) {
171//     for (int i = 0; i < w - 1; ++i) {
172//       check(g.source(g.right(g(i, j))) == g(i, j), "Wrong right");
173//       check(g.target(g.right(g(i, j))) == g(i + 1, j), "Wrong right");     
174//     }
175//     check(g.right(g(w - 1, j)) == INVALID, "Wrong right");   
176//   }
177
178//   for (int j = 0; j < h; ++j) {
179//     for (int i = 1; i < w; ++i) {
180//       check(g.source(g.left(g(i, j))) == g(i, j), "Wrong left");
181//       check(g.target(g.left(g(i, j))) == g(i - 1, j), "Wrong left");     
182//     }
183//     check(g.left(g(0, j)) == INVALID, "Wrong left");   
184//   }
185// }
186
187int main() {
188  check_concepts();
189
190  check_graph<ListGraph>();
191//  check_graph<SmartGraph>();
192
193//   {
194//     FullGraph g(5);
195//     check_item_counts(g, 5, 10);
196//   }
197
198//   {
199//     GridGraph g(5, 6);
200//     check_item_counts(g, 30, 49);
201//     checkGridGraph(g, 5, 6);
202//   }
203
204  std::cout << __FILE__ ": All tests passed.\n";
205
206  return 0;
207}
Note: See TracBrowser for help on using the repository browser.