COIN-OR::LEMON - Graph Library

Changeset 286:da414906fe21 in lemon-1.2 for test


Ignore:
Timestamp:
09/26/08 12:40:11 (16 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Improvements related to BFS/DFS/Dijkstra (ticket #96)

  • Add run(s,t) function to BfsVisit?.
  • Modify run(s,t) functions in the class interfaces to return bool value.
  • Bug fix in Dijkstra::start(t) function.
  • Improve Dijkstra::currentDist().
  • Extend test files to check named class template parameters.
  • Doc improvements.
Location:
test
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • test/bfs_test.cc

    r278 r286  
    5555  typedef concepts::Digraph Digraph;
    5656  typedef Bfs<Digraph> BType;
     57  typedef Digraph::Node Node;
     58  typedef Digraph::Arc Arc;
    5759
    5860  Digraph G;
    59   Digraph::Node n;
    60   Digraph::Arc e;
     61  Node s, t;
     62  Arc e;
    6163  int l;
    6264  bool b;
    6365  BType::DistMap d(G);
    6466  BType::PredMap p(G);
     67  Path<Digraph> pp;
    6568
    66   BType bfs_test(G);
     69  {
     70    BType bfs_test(G);
    6771
    68   bfs_test.run(n);
     72    bfs_test.run(s);
     73    bfs_test.run(s,t);
     74    bfs_test.run();
    6975
    70   l  = bfs_test.dist(n);
    71   e  = bfs_test.predArc(n);
    72   n  = bfs_test.predNode(n);
    73   d  = bfs_test.distMap();
    74   p  = bfs_test.predMap();
    75   b  = bfs_test.reached(n);
     76    l  = bfs_test.dist(t);
     77    e  = bfs_test.predArc(t);
     78    s  = bfs_test.predNode(t);
     79    b  = bfs_test.reached(t);
     80    d  = bfs_test.distMap();
     81    p  = bfs_test.predMap();
     82    pp = bfs_test.path(t);
     83  }
     84  {
     85    BType
     86      ::SetPredMap<concepts::ReadWriteMap<Node,Arc> >
     87      ::SetDistMap<concepts::ReadWriteMap<Node,int> >
     88      ::SetReachedMap<concepts::ReadWriteMap<Node,bool> >
     89      ::SetProcessedMap<concepts::WriteMap<Node,bool> >
     90      ::SetStandardProcessedMap
     91      ::Create bfs_test(G);
    7692
    77   Path<Digraph> pp = bfs_test.path(n);
     93    bfs_test.run(s);
     94    bfs_test.run(s,t);
     95    bfs_test.run();
     96
     97    l  = bfs_test.dist(t);
     98    e  = bfs_test.predArc(t);
     99    s  = bfs_test.predNode(t);
     100    b  = bfs_test.reached(t);
     101    pp = bfs_test.path(t);
     102  }
    78103}
    79104
  • test/dfs_test.cc

    r278 r286  
    5757  typedef concepts::Digraph Digraph;
    5858  typedef Dfs<Digraph> DType;
     59  typedef Digraph::Node Node;
     60  typedef Digraph::Arc Arc;
    5961
    6062  Digraph G;
    61   Digraph::Node n;
    62   Digraph::Arc e;
     63  Node s, t;
     64  Arc e;
    6365  int l;
    6466  bool b;
    6567  DType::DistMap d(G);
    6668  DType::PredMap p(G);
     69  Path<Digraph> pp;
    6770
    68   DType dfs_test(G);
     71  {
     72    DType dfs_test(G);
    6973
    70   dfs_test.run(n);
     74    dfs_test.run(s);
     75    dfs_test.run(s,t);
     76    dfs_test.run();
    7177
    72   l  = dfs_test.dist(n);
    73   e  = dfs_test.predArc(n);
    74   n  = dfs_test.predNode(n);
    75   d  = dfs_test.distMap();
    76   p  = dfs_test.predMap();
    77   b  = dfs_test.reached(n);
     78    l  = dfs_test.dist(t);
     79    e  = dfs_test.predArc(t);
     80    s  = dfs_test.predNode(t);
     81    b  = dfs_test.reached(t);
     82    d  = dfs_test.distMap();
     83    p  = dfs_test.predMap();
     84    pp = dfs_test.path(t);
     85  }
     86  {
     87    DType
     88      ::SetPredMap<concepts::ReadWriteMap<Node,Arc> >
     89      ::SetDistMap<concepts::ReadWriteMap<Node,int> >
     90      ::SetReachedMap<concepts::ReadWriteMap<Node,bool> >
     91      ::SetProcessedMap<concepts::WriteMap<Node,bool> >
     92      ::SetStandardProcessedMap
     93      ::Create dfs_test(G);
    7894
    79   Path<Digraph> pp = dfs_test.path(n);
     95    dfs_test.run(s);
     96    dfs_test.run(s,t);
     97    dfs_test.run();
     98
     99    l  = dfs_test.dist(t);
     100    e  = dfs_test.predArc(t);
     101    s  = dfs_test.predNode(t);
     102    b  = dfs_test.reached(t);
     103    pp = dfs_test.path(t);
     104  }
    80105}
    81106
  • test/dijkstra_test.cc

    r278 r286  
    2323#include <lemon/dijkstra.h>
    2424#include <lemon/path.h>
     25#include <lemon/bin_heap.h>
    2526
    2627#include "graph_test.h"
     
    5657  typedef concepts::ReadMap<Digraph::Arc,VType> LengthMap;
    5758  typedef Dijkstra<Digraph, LengthMap> DType;
     59  typedef Digraph::Node Node;
     60  typedef Digraph::Arc Arc;
    5861
    5962  Digraph G;
    60   Digraph::Node n;
    61   Digraph::Arc e;
     63  Node s, t;
     64  Arc e;
    6265  VType l;
    6366  bool b;
     
    6568  DType::PredMap p(G);
    6669  LengthMap length;
     70  Path<Digraph> pp;
    6771
    68   DType dijkstra_test(G,length);
     72  {
     73    DType dijkstra_test(G,length);
    6974
    70   dijkstra_test.run(n);
     75    dijkstra_test.run(s);
     76    dijkstra_test.run(s,t);
    7177
    72   l  = dijkstra_test.dist(n);
    73   e  = dijkstra_test.predArc(n);
    74   n  = dijkstra_test.predNode(n);
    75   d  = dijkstra_test.distMap();
    76   p  = dijkstra_test.predMap();
    77   b  = dijkstra_test.reached(n);
     78    l  = dijkstra_test.dist(t);
     79    e  = dijkstra_test.predArc(t);
     80    s  = dijkstra_test.predNode(t);
     81    b  = dijkstra_test.reached(t);
     82    d  = dijkstra_test.distMap();
     83    p  = dijkstra_test.predMap();
     84    pp = dijkstra_test.path(t);
     85  }
     86  {
     87    DType
     88      ::SetPredMap<concepts::ReadWriteMap<Node,Arc> >
     89      ::SetDistMap<concepts::ReadWriteMap<Node,VType> >
     90      ::SetProcessedMap<concepts::WriteMap<Node,bool> >
     91      ::SetStandardProcessedMap
     92      ::SetOperationTraits<DijkstraWidestPathOperationTraits<VType> >
     93      ::SetHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > >
     94      ::SetStandardHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > >
     95      ::Create dijkstra_test(G,length);
    7896
    79   Path<Digraph> pp = dijkstra_test.path(n);
     97    dijkstra_test.run(s);
     98    dijkstra_test.run(s,t);
     99
     100    l  = dijkstra_test.dist(t);
     101    e  = dijkstra_test.predArc(t);
     102    s  = dijkstra_test.predNode(t);
     103    b  = dijkstra_test.reached(t);
     104    pp = dijkstra_test.path(t);
     105  }
     106
    80107}
    81108
Note: See TracChangeset for help on using the changeset viewer.