test/graph_utils_test.cc
author deba
Fri, 03 Nov 2006 16:29:32 +0000
changeset 2293 1ee6e8788cc7
parent 2236 9f329faa4aee
child 2391 14a343be7a5a
permissions -rw-r--r--
First implementation of the static graph class
It could be improved to get better running times on benchmarks
alpar@1956
     1
/* -*- C++ -*-
alpar@1956
     2
 *
alpar@1956
     3
 * This file is a part of LEMON, a generic C++ optimization library
alpar@1956
     4
 *
alpar@1956
     5
 * Copyright (C) 2003-2006
alpar@1956
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@1956
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@1956
     8
 *
alpar@1956
     9
 * Permission to use, modify and distribute this software is granted
alpar@1956
    10
 * provided that this copyright notice appears in all copies. For
alpar@1956
    11
 * precise terms see the accompanying LICENSE file.
alpar@1956
    12
 *
alpar@1956
    13
 * This software is provided "AS IS" with no warranty of any kind,
alpar@1956
    14
 * express or implied, and with no claim as to its suitability for any
alpar@1956
    15
 * purpose.
alpar@1956
    16
 *
alpar@1956
    17
 */
klao@946
    18
klao@946
    19
#include <iostream>
klao@946
    20
#include <vector>
klao@946
    21
klao@977
    22
#include <lemon/graph_utils.h>
klao@977
    23
klao@946
    24
#include <lemon/list_graph.h>
klao@946
    25
#include <lemon/smart_graph.h>
klao@946
    26
#include <lemon/full_graph.h>
klao@946
    27
klao@946
    28
#include "test_tools.h"
klao@946
    29
#include "graph_utils_test.h"
klao@946
    30
klao@946
    31
klao@946
    32
using namespace lemon;
klao@946
    33
alpar@1459
    34
template<class Graph>
alpar@1459
    35
void checkSnapDeg() 
alpar@1459
    36
{
alpar@1459
    37
  Graph g;
alpar@1459
    38
  typename Graph::Node n1=g.addNode();
alpar@1459
    39
  typename Graph::Node n2=g.addNode();
alpar@1459
    40
   
alpar@1459
    41
  InDegMap<Graph> ind(g);
alpar@1459
    42
 
alpar@1459
    43
  g.addEdge(n1,n2);
alpar@1459
    44
  
alpar@1772
    45
  typename Graph::Snapshot snap(g);
alpar@1459
    46
  
alpar@1459
    47
  OutDegMap<Graph> outd(g);
alpar@1459
    48
  
alpar@1459
    49
  check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value.");
alpar@1459
    50
  check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value.");
alpar@1459
    51
alpar@1459
    52
  g.addEdge(n1,n2);
alpar@1459
    53
  g.addEdge(n2,n1);
alpar@1459
    54
 
alpar@1459
    55
  check(ind[n1]==1 && ind[n2]==2, "Wrong InDegMap value.");
alpar@1459
    56
  check(outd[n1]==2 && outd[n2]==1, "Wrong OutDegMap value.");
alpar@1459
    57
alpar@1459
    58
  snap.restore();
alpar@1459
    59
alpar@1459
    60
  check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value.");
alpar@1459
    61
  check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value.");
alpar@1459
    62
  
alpar@1459
    63
}
klao@946
    64
klao@946
    65
int main() {
klao@946
    66
  ///\file
klao@946
    67
  { // checking list graph
klao@946
    68
    checkGraphCounters<ListGraph>();
deba@1568
    69
    checkFindEdge<ListGraph>();
klao@946
    70
  }
klao@946
    71
  { // checking smart graph
klao@946
    72
    checkGraphCounters<SmartGraph>();
deba@1568
    73
    checkFindEdge<SmartGraph>();
klao@946
    74
  }
klao@977
    75
  {
klao@977
    76
    int num = 5;
klao@977
    77
    FullGraph fg(num);
klao@977
    78
    check(countNodes(fg) == num, "FullGraph: wrong node number.");
deba@1568
    79
    check(countEdges(fg) == num*num, "FullGraph: wrong edge number.");
deba@1568
    80
    for (FullGraph::NodeIt src(fg); src != INVALID; ++src) {
deba@1568
    81
      for (FullGraph::NodeIt trg(fg); trg != INVALID; ++trg) {
deba@1568
    82
	ConEdgeIt<FullGraph> con(fg, src, trg);
deba@1568
    83
	check(con != INVALID, "There is no connecting edge.");
deba@1568
    84
	check(fg.source(con) == src, "Wrong source.");
deba@1568
    85
	check(fg.target(con) == trg, "Wrong target.");
deba@1568
    86
	check(++con == INVALID, "There is more connecting edge.");
deba@1568
    87
      }
deba@1568
    88
    }
alpar@2236
    89
    AllEdgeLookUp<FullGraph> el(fg);
alpar@2236
    90
    for (FullGraph::NodeIt src(fg); src != INVALID; ++src) {
alpar@2236
    91
      for (FullGraph::NodeIt trg(fg); trg != INVALID; ++trg) {
alpar@2236
    92
	FullGraph::Edge con = el(src, trg);
alpar@2236
    93
	check(con != INVALID, "There is no connecting edge.");
alpar@2236
    94
	check(fg.source(con) == src, "Wrong source.");
alpar@2236
    95
	check(fg.target(con) == trg, "Wrong target.");
alpar@2236
    96
	check(el(src,trg,con) == INVALID, "There is more connecting edge.");
alpar@2236
    97
      }
alpar@2236
    98
    }
klao@977
    99
  }
klao@946
   100
alpar@1772
   101
  //check In/OutDegMap (and Snapshot feature)
alpar@1459
   102
alpar@1459
   103
  checkSnapDeg<ListGraph>();
alpar@1459
   104
  checkSnapDeg<SmartGraph>();
alpar@1459
   105
  
deba@1728
   106
  {
deba@1728
   107
    const int nodeNum = 10;
deba@1728
   108
    const int edgeNum = 100;
deba@1728
   109
    ListGraph graph;
deba@1728
   110
    InDegMap<ListGraph> inDeg(graph);
deba@1729
   111
    OutDegMap<ListGraph> outDeg(graph);
deba@1728
   112
    std::vector<ListGraph::Node> nodes(nodeNum);
deba@1728
   113
    for (int i = 0; i < nodeNum; ++i) {
deba@1728
   114
      nodes[i] = graph.addNode();
deba@1728
   115
    }
deba@1728
   116
    std::vector<ListGraph::Edge> edges(edgeNum);
deba@1728
   117
    for (int i = 0; i < edgeNum; ++i) {
deba@1728
   118
      edges[i] = 
deba@2242
   119
	graph.addEdge(nodes[rnd[nodeNum]], nodes[rnd[nodeNum]]);
deba@1728
   120
    }
deba@1728
   121
    for (int i = 0; i < nodeNum; ++i) {
deba@1728
   122
      check(inDeg[nodes[i]] == countInEdges(graph, nodes[i]), 
deba@1728
   123
	    "Wrong in degree map");
deba@1728
   124
    }
deba@1728
   125
    for (int i = 0; i < nodeNum; ++i) {
deba@1729
   126
      check(outDeg[nodes[i]] == countOutEdges(graph, nodes[i]), 
deba@1728
   127
	    "Wrong in degree map");
deba@1728
   128
    }
deba@1728
   129
  }
alpar@1459
   130
alpar@1459
   131
  ///Everything is OK
klao@946
   132
  std::cout << __FILE__ ": All tests passed.\n";
klao@946
   133
klao@946
   134
  return 0;
klao@946
   135
}