COIN-OR::LEMON - Graph Library

Changeset 1728:eb8bb91ba9e2 in lemon-0.x


Ignore:
Timestamp:
10/14/05 13:03:40 (19 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2255
Message:

Updating tests

Location:
test
Files:
1 added
6 edited

Legend:

Unmodified
Added
Removed
  • test/Makefile.am

    r1711 r1728  
    2323        max_matching_test \
    2424        maps_test \
     25        matrix_maps_test \
    2526        min_cost_flow_test \
    2627        suurballe_test \
     
    5556kruskal_test_SOURCES = kruskal_test.cc
    5657maps_test_SOURCES = maps_test.cc
     58matrix_maps_test_SOURCES = matrix_maps_test.cc
    5759min_cost_flow_test_SOURCES = min_cost_flow_test.cc
    5860max_matching_test_SOURCES = max_matching_test.cc
  • test/graph_test.h

    r1435 r1728  
    1717#define LEMON_TEST_GRAPH_TEST_H
    1818
    19 
     19#include <lemon/graph_utils.h>
    2020#include "test_tools.h"
    2121
     
    8181  }
    8282
     83  template <class Graph>
     84  void checkGraphIterators(const Graph& graph) {
     85    typedef typename Graph::Node Node;
     86    typedef typename Graph::NodeIt NodeIt;
     87    typedef typename Graph::Edge Edge;
     88    typedef typename Graph::EdgeIt EdgeIt;
     89    typedef typename Graph::InEdgeIt InEdgeIt;
     90    typedef typename Graph::OutEdgeIt OutEdgeIt;
     91    typedef ConEdgeIt<Graph> ConEdgeIt;
     92   
     93    for (NodeIt it(graph); it != INVALID; ++it) {}
     94  }
     95
    8396  ///\file
    8497  ///\todo Check target(), source() as well;
  • test/graph_utils_test.cc

    r1568 r1728  
    7878  checkSnapDeg<SmartGraph>();
    7979 
     80  {
     81    const int nodeNum = 10;
     82    const int edgeNum = 100;
     83    ListGraph graph;
     84    InDegMap<ListGraph> inDeg(graph);
     85    std::vector<ListGraph::Node> nodes(nodeNum);
     86    for (int i = 0; i < nodeNum; ++i) {
     87      nodes[i] = graph.addNode();
     88    }
     89    std::vector<ListGraph::Edge> edges(edgeNum);
     90    for (int i = 0; i < edgeNum; ++i) {
     91      edges[i] =
     92        graph.addEdge(nodes[urandom(nodeNum)], nodes[urandom(nodeNum)]);
     93    }
     94    for (int i = 0; i < nodeNum; ++i) {
     95      check(inDeg[nodes[i]] == countInEdges(graph, nodes[i]),
     96            "Wrong in degree map");
     97    }
     98    for (int i = 0; i < edgeNum; ++i) {
     99      graph.changeTarget(edges[i], nodes[urandom(nodeNum)]);
     100    }
     101    for (int i = 0; i < nodeNum; ++i) {
     102      check(inDeg[nodes[i]] == countInEdges(graph, nodes[i]),
     103            "Wrong in degree map");
     104    }
     105    for (int i = 0; i < edgeNum; ++i) {
     106      graph.changeSource(edges[i], nodes[urandom(nodeNum)]);
     107    }
     108    for (int i = 0; i < nodeNum; ++i) {
     109      check(inDeg[nodes[i]] == countInEdges(graph, nodes[i]),
     110            "Wrong in degree map");
     111    }
     112    for (int i = 0; i < edgeNum; ++i) {
     113      graph.reverseEdge(edges[i]);
     114    }
     115    for (int i = 0; i < nodeNum; ++i) {
     116      check(inDeg[nodes[i]] == countInEdges(graph, nodes[i]),
     117            "Wrong in degree map");
     118    }
     119  }
    80120
    81121  ///Everything is OK
  • test/heap_test.cc

    r1435 r1728  
    1616#include <lemon/fib_heap.h>
    1717#include <lemon/radix_heap.h>
     18#include <lemon/linear_heap.h>
    1819
    1920#include "test_tools.h"
     
    2122#include "heap_test.h"
    2223
     24#include <lemon/time_measure.h>
    2325
    2426using namespace lemon;
     
    6668    typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap;
    6769    checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
     70    Timer timer;
    6871    dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
     72    std::cout << timer << std::endl;
    6973  }
    7074  {
     
    7882    typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap;
    7983    checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
     84    Timer timer;
    8085    dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
     86    std::cout << timer << std::endl;
    8187  }
    8288  {
     
    9096    typedef RadixHeap<Node, Graph::NodeMap<int> > NodeHeap;
    9197    checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
     98    Timer timer;
    9299    dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
     100    std::cout << timer << std::endl;
     101  }
     102
     103  {
     104    std::cerr << "Checking Linear Heap" << std::endl;
     105
     106    typedef LinearHeap<Item, ItemIntMap> IntHeap;
     107    checkConcept<Heap<Item, Prio, ItemIntMap>, IntHeap>();
     108    heapSortTest<IntHeap>(100);
     109    heapIncreaseTest<IntHeap>(100);
     110
     111    typedef LinearHeap<Node, Graph::NodeMap<int> > NodeHeap;
     112    checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
     113    Timer timer;
     114    dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
     115    std::cout << timer << std::endl;
    93116  }
    94117
  • test/heap_test.h

    r1435 r1728  
    1 // -+- c++ -+-
     1// -*- c++ -*-
    22
    33#include <vector>
     
    6666
    6767
    68 template <typename _Traits, typename _Heap>
    69 struct DefHeapTraits : public _Traits {
    70   typedef _Heap Heap;
    71 };
    72 
    7368template <typename _Graph, typename _LengthMap, typename _Heap>
    7469void dijkstraHeapTest(_Graph& graph, _LengthMap& length,
     
    8479  typedef typename Graph::EdgeIt EdgeIt;
    8580
    86   Dijkstra<Graph, LengthMap,
    87     DefHeapTraits<DijkstraDefaultTraits<Graph, LengthMap>, Heap> >
    88     dijkstra(graph, length);
     81  typename Dijkstra<Graph, LengthMap>::template DefHeap<Heap>::
     82    Create dijkstra(graph, length);
    8983
    9084  dijkstra.run(start);
     
    9589    if (dijkstra.reached(u)) {
    9690      check( dijkstra.dist(v) - dijkstra.dist(u) <= length[e],
    97              "Error in a shortest path tree edge!");
     91             "Error in a shortest path tree edge!");
    9892    }
    9993  }
  • test/test_tools.h

    r1716 r1728  
    2121#include <vector>
    2222
     23#include <cstdlib>
     24#include <ctime>
     25
    2326#include <lemon/invalid.h>
     27#include <lemon/concept_check.h>
    2428
    2529using namespace lemon;
     
    171175}
    172176
     177int _urandom_init() {
     178  int seed = time(0);
     179  srand(seed);
     180  return seed;
     181}
     182
     183int urandom(int n) {
     184  static int seed = _urandom_init();
     185  ignore_unused_variable_warning(seed);
     186  return (int)(rand() / (1.0 + RAND_MAX) * n);
     187}
     188
    173189#endif
Note: See TracChangeset for help on using the changeset viewer.