COIN-OR::LEMON - Graph Library

source: lemon-main/test/graph_utils_test.cc @ 572:be6646ac5d89

Last change on this file since 572:be6646ac5d89 was 572:be6646ac5d89, checked in by Alpar Juttner <alpar@…>, 15 years ago

DescriptorMap?->RangeIdMap?, InvertableMap?->CrossRefMap? (#160)

File size: 6.5 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-2009
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 <cstdlib>
20#include <ctime>
21
22#include <lemon/random.h>
23#include <lemon/list_graph.h>
24#include <lemon/smart_graph.h>
25#include <lemon/maps.h>
26
27#include "graph_test.h"
28#include "test_tools.h"
29
30using namespace lemon;
31
32template <typename Digraph>
33void checkFindArcs() {
34  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
35
36  {
37    Digraph digraph;
38    for (int i = 0; i < 10; ++i) {
39      digraph.addNode();
40    }
41    RangeIdMap<Digraph, Node> nodes(digraph);
42    typename RangeIdMap<Digraph, Node>::InverseMap invNodes(nodes);
43    for (int i = 0; i < 100; ++i) {
44      int src = rnd[invNodes.size()];
45      int trg = rnd[invNodes.size()];
46      digraph.addArc(invNodes[src], invNodes[trg]);
47    }
48    typename Digraph::template ArcMap<bool> found(digraph, false);
49    RangeIdMap<Digraph, Arc> arcs(digraph);
50    for (NodeIt src(digraph); src != INVALID; ++src) {
51      for (NodeIt trg(digraph); trg != INVALID; ++trg) {
52        for (ConArcIt<Digraph> con(digraph, src, trg); con != INVALID; ++con) {
53          check(digraph.source(con) == src, "Wrong source.");
54          check(digraph.target(con) == trg, "Wrong target.");
55          check(found[con] == false, "The arc found already.");
56          found[con] = true;
57        }
58      }
59    }
60    for (ArcIt it(digraph); it != INVALID; ++it) {
61      check(found[it] == true, "The arc is not found.");
62    }
63  }
64
65  {
66    int num = 5;
67    Digraph fg;
68    std::vector<Node> nodes;
69    for (int i = 0; i < num; ++i) {
70      nodes.push_back(fg.addNode());
71    }
72    for (int i = 0; i < num * num; ++i) {
73      fg.addArc(nodes[i / num], nodes[i % num]);
74    }
75    check(countNodes(fg) == num, "Wrong node number.");
76    check(countArcs(fg) == num*num, "Wrong arc number.");
77    for (NodeIt src(fg); src != INVALID; ++src) {
78      for (NodeIt trg(fg); trg != INVALID; ++trg) {
79        ConArcIt<Digraph> con(fg, src, trg);
80        check(con != INVALID, "There is no connecting arc.");
81        check(fg.source(con) == src, "Wrong source.");
82        check(fg.target(con) == trg, "Wrong target.");
83        check(++con == INVALID, "There is more connecting arc.");
84      }
85    }
86    ArcLookUp<Digraph> al1(fg);
87    DynArcLookUp<Digraph> al2(fg);
88    AllArcLookUp<Digraph> al3(fg);
89    for (NodeIt src(fg); src != INVALID; ++src) {
90      for (NodeIt trg(fg); trg != INVALID; ++trg) {
91        Arc con1 = al1(src, trg);
92        Arc con2 = al2(src, trg);
93        Arc con3 = al3(src, trg);
94        Arc con4 = findArc(fg, src, trg);
95        check(con1 == con2 && con2 == con3 && con3 == con4,
96              "Different results.")
97        check(con1 != INVALID, "There is no connecting arc.");
98        check(fg.source(con1) == src, "Wrong source.");
99        check(fg.target(con1) == trg, "Wrong target.");
100        check(al3(src, trg, con3) == INVALID,
101              "There is more connecting arc.");
102        check(findArc(fg, src, trg, con4) == INVALID,
103              "There is more connecting arc.");
104      }
105    }
106  }
107}
108
109template <typename Graph>
110void checkFindEdges() {
111  TEMPLATE_GRAPH_TYPEDEFS(Graph);
112  Graph graph;
113  for (int i = 0; i < 10; ++i) {
114    graph.addNode();
115  }
116  RangeIdMap<Graph, Node> nodes(graph);
117  typename RangeIdMap<Graph, Node>::InverseMap invNodes(nodes);
118  for (int i = 0; i < 100; ++i) {
119    int src = rnd[invNodes.size()];
120    int trg = rnd[invNodes.size()];
121    graph.addEdge(invNodes[src], invNodes[trg]);
122  }
123  typename Graph::template EdgeMap<int> found(graph, 0);
124  RangeIdMap<Graph, Edge> edges(graph);
125  for (NodeIt src(graph); src != INVALID; ++src) {
126    for (NodeIt trg(graph); trg != INVALID; ++trg) {
127      for (ConEdgeIt<Graph> con(graph, src, trg); con != INVALID; ++con) {
128        check( (graph.u(con) == src && graph.v(con) == trg) ||
129               (graph.v(con) == src && graph.u(con) == trg),
130               "Wrong end nodes.");
131        ++found[con];
132        check(found[con] <= 2, "The edge found more than twice.");
133      }
134    }
135  }
136  for (EdgeIt it(graph); it != INVALID; ++it) {
137    check( (graph.u(it) != graph.v(it) && found[it] == 2) ||
138           (graph.u(it) == graph.v(it) && found[it] == 1),
139           "The edge is not found correctly.");
140  }
141}
142
143template <class Digraph>
144void checkDeg()
145{
146  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
147
148  const int nodeNum = 10;
149  const int arcNum = 100;
150  Digraph digraph;
151  InDegMap<Digraph> inDeg(digraph);
152  OutDegMap<Digraph> outDeg(digraph);
153  std::vector<Node> nodes(nodeNum);
154  for (int i = 0; i < nodeNum; ++i) {
155    nodes[i] = digraph.addNode();
156  }
157  std::vector<Arc> arcs(arcNum);
158  for (int i = 0; i < arcNum; ++i) {
159    arcs[i] = digraph.addArc(nodes[rnd[nodeNum]], nodes[rnd[nodeNum]]);
160  }
161  for (int i = 0; i < nodeNum; ++i) {
162    check(inDeg[nodes[i]] == countInArcs(digraph, nodes[i]),
163          "Wrong in degree map");
164  }
165  for (int i = 0; i < nodeNum; ++i) {
166    check(outDeg[nodes[i]] == countOutArcs(digraph, nodes[i]),
167          "Wrong out degree map");
168  }
169}
170
171template <class Digraph>
172void checkSnapDeg()
173{
174  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
175
176  Digraph g;
177  Node n1=g.addNode();
178  Node n2=g.addNode();
179
180  InDegMap<Digraph> ind(g);
181
182  g.addArc(n1,n2);
183
184  typename Digraph::Snapshot snap(g);
185
186  OutDegMap<Digraph> outd(g);
187
188  check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value.");
189  check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value.");
190
191  g.addArc(n1,n2);
192  g.addArc(n2,n1);
193
194  check(ind[n1]==1 && ind[n2]==2, "Wrong InDegMap value.");
195  check(outd[n1]==2 && outd[n2]==1, "Wrong OutDegMap value.");
196
197  snap.restore();
198
199  check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value.");
200  check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value.");
201}
202
203int main() {
204  // Checking ConArcIt, ConEdgeIt, ArcLookUp, AllArcLookUp, and DynArcLookUp
205  checkFindArcs<ListDigraph>();
206  checkFindArcs<SmartDigraph>();
207  checkFindEdges<ListGraph>();
208  checkFindEdges<SmartGraph>();
209
210  // Checking In/OutDegMap (and Snapshot feature)
211  checkDeg<ListDigraph>();
212  checkDeg<SmartDigraph>();
213  checkSnapDeg<ListDigraph>();
214  checkSnapDeg<SmartDigraph>();
215
216  return 0;
217}
Note: See TracBrowser for help on using the repository browser.