COIN-OR::LEMON - Graph Library

source: lemon-0.x/test/graph_utils_test.cc @ 2391:14a343be7a5a

Last change on this file since 2391:14a343be7a5a was 2391:14a343be7a5a, checked in by Alpar Juttner, 17 years ago

Happy New Year to all source files!

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