COIN-OR::LEMON - Graph Library

Changeset 1194:7bce0ef61d6b in lemon-0.x


Ignore:
Timestamp:
03/04/05 18:20:11 (15 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1606
Message:

Change test to be up to date.
Deprecated test, it should be used rather the heap_test.cc and heap_test.h.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/test/dijkstra_heap_test.cc

    r1164 r1194  
    3232
    3333#include <lemon/smart_graph.h>
     34
     35#include <lemon/graph_writer.h>
     36#include <lemon/map_utils.h>
     37
     38
    3439#include <lemon/dimacs.h>
    3540#include <lemon/dijkstra.h>
    3641#include <lemon/time_measure.h>
     42#include <lemon/graph_utils.h>
     43
    3744#include <lemon/bin_heap.h>
    3845#include <lemon/fib_heap.h>
     46#include <lemon/radix_heap.h>
    3947
    4048using namespace lemon;
    4149
    42 int main(int, char **) {
    43  
    44   typedef SmartGraph Graph;
    45 
    46   typedef Graph::Edge Edge;
    47   typedef Graph::Node Node;
    48   typedef Graph::EdgeIt EdgeIt;
    49   typedef Graph::NodeIt NodeIt;
    50   typedef Graph::template EdgeMap<int> LengthMap;
    51 
    52   Graph G;
     50typedef ListGraph Graph;
     51
     52typedef Graph::Edge Edge;
     53typedef Graph::Node Node;
     54typedef Graph::EdgeIt EdgeIt;
     55typedef Graph::NodeIt NodeIt;
     56typedef Graph::EdgeMap<int> LengthMap;
     57
     58
     59struct FibTraits : public DijkstraDefaultTraits<Graph, LengthMap> {
     60  typedef FibHeap<Graph::Node, LengthMap::Value, Graph::NodeMap<int> > Heap;
     61};
     62
     63struct RadixTraits : public DijkstraDefaultTraits<Graph, LengthMap> {
     64  typedef RadixHeap<Graph::Node, Graph::NodeMap<int> > Heap;
     65};
     66
     67
     68int main(int argc, const char* argv[]) {
     69 
     70
     71  Graph graph;
    5372  Node s, t;
    54   LengthMap cap(G);
    55   readDimacsMaxFlow(std::cin, G, s, t, cap);
     73  LengthMap cap(graph);
     74  readDimacs(std::cin, graph, cap, s, t);
    5675  Timer ts;
     76
     77  GraphWriter<Graph> writer(std::cout, graph);
     78
     79  IdMap<Graph, Node> nodeIdMap(graph);
     80  writer.addNodeMap("id", nodeIdMap);
     81
     82  IdMap<Graph, Edge> edgeIdMap(graph);
     83  writer.addEdgeMap("id", edgeIdMap);
     84
     85  writer.addEdgeMap("cap", cap);
     86
     87  writer.run();
    5788   
    5889  std::cout <<
     
    6091            <<std::endl;
    6192  std::cout<<"  on a graph with " <<
    62     G.nodeNum() << " nodes and " << G.edgeNum() << " edges..."
     93    countNodes(graph) << " nodes and " << countEdges(graph) << " edges..."
    6394           << std::endl<<std::endl;
    64  
     95
     96
    6597  Dijkstra<Graph, LengthMap>
    66     dijkstra_test(G, cap);
     98    dijkstra_test(graph, cap);
    6799  ts.reset();
    68   dijkstra_test.run(s);
     100   dijkstra_test.run(s);
    69101  std::cout << "elapsed time: " << ts << std::endl;
    70  
     102
    71103  int error1=0;
    72104  int error2=0;
    73105
    74   for(EdgeIt e(G); e!=INVALID; ++e) {
    75     Node u=G.source(e);
    76     Node v=G.target(e);
     106  for(EdgeIt e(graph); e!=INVALID; ++e) {
     107    Node u=graph.source(e);
     108    Node v=graph.target(e);
    77109    if ( dijkstra_test.dist(v) - dijkstra_test.dist(u) > cap[e] )
    78110      if ( dijkstra_test.reached(u) ) {
     
    85117
    86118  NodeIt v;
    87   for(NodeIt v(G); v!=INVALID; ++v) {
     119  for(NodeIt v(graph); v!=INVALID; ++v) {
    88120    if ( dijkstra_test.reached(v) ) {
    89121      Edge e=dijkstra_test.pred(v);
    90       Node u=G.source(e);
     122      Node u=graph.source(e);
    91123      if ( dijkstra_test.dist(v) - dijkstra_test.dist(u) != cap[e] ) {
    92124        std::cout<<"Error in a shortest path tree edge! Difference: "
     
    109141            <<std::endl;
    110142  std::cout<<"  on a graph with " <<
    111     G.nodeNum() << " nodes and " << G.edgeNum() << " edges..."
     143    countNodes(graph) << " nodes and " << countEdges(graph) << " edges..."
    112144           << std::endl<<std::endl;
    113145 
    114   Dijkstra<Graph, LengthMap, FibHeap>
    115     dijkstra_test2(G, cap);
     146
     147  Dijkstra<Graph, LengthMap, FibTraits>
     148    dijkstra_test2(graph, cap);
    116149  ts.reset();
    117150  dijkstra_test2.run(s);
     
    121154  error2=0;
    122155
    123   for(EdgeIt e(G); e!=INVALID; ++e) {
    124     Node u=G.source(e);
    125     Node v=G.target(e);
     156  for(EdgeIt e(graph); e!=INVALID; ++e) {
     157    Node u=graph.source(e);
     158    Node v=graph.target(e);
    126159    if ( dijkstra_test2.dist(v) - dijkstra_test2.dist(u) > cap[e] )
    127160      if ( dijkstra_test2.reached(u) ) {
     
    133166  }
    134167
    135   for(NodeIt n(G); v!=INVALID; ++v) {
     168  for(NodeIt n(graph); v!=INVALID; ++v) {
    136169    if ( dijkstra_test2.reached(v) ) {
    137170      Edge e=dijkstra_test2.pred(v);
    138       Node u=G.source(e);
     171      Node u=graph.source(e);
    139172      if ( dijkstra_test2.dist(v) - dijkstra_test2.dist(u) != cap[e] ) {
    140173        std::cout<<"Error in a shortest path tree edge! Difference: "
     
    150183            << " shortest path tree edge is erroneous."<<std::endl;
    151184
     185  std::cout <<
     186    "\n\n  Testing dijkstra.h with Radix heap implementation radix_heap.h,"
     187            <<std::endl;
     188  std::cout<<"  on a graph with " <<
     189    countNodes(graph) << " nodes and " << countEdges(graph) << " edges..."
     190           << std::endl<<std::endl;
     191
     192
     193  Dijkstra<Graph, LengthMap, RadixTraits>
     194    dijkstra_test3(graph, cap);
     195  ts.reset();
     196  dijkstra_test3.run(s);
     197  std::cout << "elapsed time: " << ts << std::endl;
     198 
     199
     200  error1=0;
     201  error2=0;
     202
     203  for(EdgeIt e(graph); e!=INVALID; ++e) {
     204    Node u=graph.source(e);
     205    Node v=graph.target(e);
     206    if ( dijkstra_test3.dist(v) - dijkstra_test3.dist(u) > cap[e] )
     207      if ( dijkstra_test3.reached(u) ) {
     208        std::cout<<"Error! dist(target)-dist(source)- edge_length= "
     209                 <<dijkstra_test3.dist(v) - dijkstra_test3.dist(u)
     210          - cap[e]<<std::endl;
     211        ++error1;
     212      }
     213  }
     214
     215  for(NodeIt n(graph); v!=INVALID; ++v) {
     216    if ( dijkstra_test3.reached(v) ) {
     217      Edge e=dijkstra_test3.pred(v);
     218      Node u=graph.source(e);
     219      if ( dijkstra_test3.dist(v) - dijkstra_test3.dist(u) != cap[e] ) {
     220        std::cout<<"Error in a shortest path tree edge! Difference: "
     221                 <<std::abs(dijkstra_test3.dist(v) - dijkstra_test3.dist(u)
     222                            - cap[e])<<std::endl;
     223        ++error2;
     224      }
     225    }
     226  }
     227
     228
     229  std::cout << error1 << " non-tree and " << error2
     230            << " shortest path tree edge is erroneous."<<std::endl;
    152231
    153232  return 0;
Note: See TracChangeset for help on using the changeset viewer.