COIN-OR::LEMON - Graph Library

source: lemon-1.0/test/graph_utils_test.cc @ 145:95d905b6e33d

Last change on this file since 145:95d905b6e33d was 139:701c529ba737, checked in by Balazs Dezso <deba@…>, 11 years ago

Renamings in the graph_utils.h + graph_utils_test added

File size: 3.8 KB
Line 
1/* -*- C++ -*-
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#include <iostream>
20#include <vector>
21
22#include <lemon/graph_utils.h>
23
24#include <lemon/list_graph.h>
25#include <lemon/smart_graph.h>
26
27#include "test_tools.h"
28#include "graph_utils_test.h"
29
30
31using namespace lemon;
32
33template <class Graph>
34void checkSnapDeg()
35{
36  Graph g;
37  typename Graph::Node n1=g.addNode();
38  typename Graph::Node n2=g.addNode();
39   
40  InDegMap<Graph> ind(g);
41 
42  g.addArc(n1,n2);
43 
44  typename Graph::Snapshot snap(g);
45 
46  OutDegMap<Graph> outd(g);
47 
48  check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value.");
49  check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value.");
50
51  g.addArc(n1,n2);
52  g.addArc(n2,n1);
53 
54  check(ind[n1]==1 && ind[n2]==2, "Wrong InDegMap value.");
55  check(outd[n1]==2 && outd[n2]==1, "Wrong OutDegMap value.");
56
57  snap.restore();
58
59  check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value.");
60  check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value.");
61 
62}
63
64int main() {
65  ///\file
66  { // checking list graph
67    checkDigraphCounters<ListDigraph>();
68    checkFindArc<ListDigraph>();
69  }
70  { // checking smart graph
71    checkDigraphCounters<SmartDigraph>();
72    checkFindArc<SmartDigraph>();
73  }
74  {
75    int num = 5;
76    SmartDigraph fg;
77    std::vector<SmartDigraph::Node> nodes;
78    for (int i = 0; i < num; ++i) {
79      nodes.push_back(fg.addNode());
80    }
81    for (int i = 0; i < num * num; ++i) {
82      fg.addArc(nodes[i / num], nodes[i % num]);
83    }
84    check(countNodes(fg) == num, "FullGraph: wrong node number.");
85    check(countArcs(fg) == num*num, "FullGraph: wrong arc number.");
86    for (SmartDigraph::NodeIt src(fg); src != INVALID; ++src) {
87      for (SmartDigraph::NodeIt trg(fg); trg != INVALID; ++trg) {
88        ConArcIt<SmartDigraph> con(fg, src, trg);
89        check(con != INVALID, "There is no connecting arc.");
90        check(fg.source(con) == src, "Wrong source.");
91        check(fg.target(con) == trg, "Wrong target.");
92        check(++con == INVALID, "There is more connecting arc.");
93      }
94    }
95    AllArcLookUp<SmartDigraph> el(fg);
96    for (SmartDigraph::NodeIt src(fg); src != INVALID; ++src) {
97      for (SmartDigraph::NodeIt trg(fg); trg != INVALID; ++trg) {
98        SmartDigraph::Arc con = el(src, trg);
99        check(con != INVALID, "There is no connecting arc.");
100        check(fg.source(con) == src, "Wrong source.");
101        check(fg.target(con) == trg, "Wrong target.");
102        check(el(src,trg,con) == INVALID, "There is more connecting arc.");
103      }
104    }
105  }
106
107  //check In/OutDegMap (and Snapshot feature)
108
109  checkSnapDeg<ListDigraph>();
110  checkSnapDeg<SmartDigraph>();
111 
112  {
113    const int nodeNum = 10;
114    const int arcNum = 100;
115    ListDigraph digraph;
116    InDegMap<ListDigraph> inDeg(digraph);
117    OutDegMap<ListDigraph> outDeg(digraph);
118    std::vector<ListDigraph::Node> nodes(nodeNum);
119    for (int i = 0; i < nodeNum; ++i) {
120      nodes[i] = digraph.addNode();
121    }
122    std::vector<ListDigraph::Arc> arcs(arcNum);
123    for (int i = 0; i < arcNum; ++i) {
124      arcs[i] =
125        digraph.addArc(nodes[rnd[nodeNum]], nodes[rnd[nodeNum]]);
126    }
127    for (int i = 0; i < nodeNum; ++i) {
128      check(inDeg[nodes[i]] == countInArcs(digraph, nodes[i]),
129            "Wrong in degree map");
130    }
131    for (int i = 0; i < nodeNum; ++i) {
132      check(outDeg[nodes[i]] == countOutArcs(digraph, nodes[i]),
133            "Wrong in degree map");
134    }
135  }
136
137  ///Everything is OK
138  std::cout << __FILE__ ": All tests passed.\n";
139
140  return 0;
141}
Note: See TracBrowser for help on using the repository browser.