COIN-OR::LEMON - Graph Library

Changeset 944:4f064aff855e in lemon-0.x


Ignore:
Timestamp:
10/16/04 02:20:13 (15 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1293
Message:

It's time to design an iterable generic bfs

Location:
src/work/marci
Files:
3 edited
2 copied

Legend:

Unmodified
Added
Removed
  • src/work/marci/augmenting_flow.h

    r921 r944  
    77
    88#include <lemon/graph_wrapper.h>
    9 #include <bfs_dfs.h>
     9//#include <bfs_dfs.h>
     10#include <bfs_mm.h>
    1011#include <lemon/invalid.h>
    1112#include <lemon/maps.h>
    12 #include <lemon/tight_edge_filter_map.h>
     13#include <demo/tight_edge_filter_map.h>
    1314
    1415/// \file
     
    1718
    1819namespace lemon {
     20  using lemon::marci::BfsIterator;
     21  using lemon::marci::DfsIterator;
    1922
    2023  /// \addtogroup galgs
     
    110113      int* number_of_augmentations;
    111114    public:
     115      typedef Node KeyType;
     116      typedef bool ValueType;
    112117      TrickyReachedMap(IntMap& _map, int& _number_of_augmentations) :
    113118        map(&_map), number_of_augmentations(&_number_of_augmentations) { }
  • src/work/marci/bfs_mm.h

    r921 r944  
    1818
    1919namespace lemon {
     20  namespace marci {
    2021
    2122  /// Bfs searches for the nodes wich are not marked in
    2223  /// \c reached_map
    23   /// Reached have to be a read-write bool node-map.
     24  /// RM have to be a read-write bool node-map.
    2425  /// \ingroup galgs
    2526  template <typename Graph, /*typename OutEdgeIt,*/
    26             typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
     27            typename RM/*=typename Graph::NodeMap<bool>*/ >
    2728  class BfsIterator {
     29  public:
     30    typedef RM ReachedMap;
    2831  protected:
    2932    typedef typename Graph::Node Node;
     
    3235    const Graph* graph;
    3336    std::queue<Node> bfs_queue;
    34     ReachedMap& reached;
     37    ReachedMap* reached_map;
    3538    bool b_node_newly_reached;
     39    //OutEdgeIt actual_edge;
    3640    Edge actual_edge;
    37     bool own_reached_map;
     41    /// \e
     42    BfsIterator(const Graph& _graph) : graph(&_graph), reached_map(0) { }
     43    /// RM have to be set before any bfs operation.
     44    BfsIterator<Graph, RM>& setReached(RM& _reached_map) {
     45      reached_map=&_reached_map;
     46    }
    3847  public:
    39     /// In that constructor \c _reached have to be a reference
     48    /// In that constructor \c _reached_map have to be a reference
    4049    /// for a bool bode-map. The algorithm will search for the
    4150    /// initially \c false nodes
    4251    /// in a bfs order.
    43     BfsIterator(const Graph& _graph, ReachedMap& _reached) :
    44       graph(&_graph), reached(_reached),
    45       own_reached_map(false) { }
     52    BfsIterator(const Graph& _graph, ReachedMap& _reached_map) :
     53      graph(&_graph), reached_map(&_reached_map) { }
    4654    /// The same as above, but the map storing the reached nodes
    4755    /// is constructed dynamically to everywhere false.
    4856    /// \deprecated
    49     BfsIterator(const Graph& _graph) :
    50       graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))),
    51       own_reached_map(true) { }
    52     /// The map storing the reached nodes have to be destroyed if
    53     /// it was constructed dynamically
    54     ~BfsIterator() { if (own_reached_map) delete &reached; }
     57//     BfsIterator(const Graph& _graph) :
     58//       graph(&_graph), reached_map(new ReachedMap(*graph /*, false*/)),
     59//       own_reached_map(true) { }
     60//     /// The map storing the reached nodes have to be destroyed if
     61//     /// it was constructed dynamically
     62//     ~BfsIterator() { if (own_reached_map) delete reached_map; }
    5563    /// This method markes \c s reached.
    5664    /// If the queue is empty, then \c s is pushed in the bfs queue
     
    5866    /// If the queue is not empty, then \c s is simply pushed.
    5967    BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& pushAndSetReached(Node s) {
    60       reached.set(s, true);
     68      reached_map->set(s, true);
    6169      if (bfs_queue.empty()) {
    6270        bfs_queue.push(s);
     
    6573        if (actual_edge!=INVALID) {
    6674          Node w=graph->head(actual_edge);
    67           if (!reached[w]) {
     75          if (!(*reached_map)[w]) {
    6876            bfs_queue.push(w);
    69             reached.set(w, true);
     77            reached_map->set(w, true);
    7078            b_node_newly_reached=true;
    7179          } else {
     
    8795        if (actual_edge!=INVALID) {
    8896          Node w=graph->head(actual_edge);
    89           if (!reached[w]) {
     97          if (!(*reached_map)[w]) {
    9098            bfs_queue.push(w);
    91             reached.set(w, true);
     99            reached_map->set(w, true);
    92100            b_node_newly_reached=true;
    93101          } else {
     
    102110          if (actual_edge!=INVALID) {
    103111            Node w=graph->head(actual_edge);
    104             if (!reached[w]) {
     112            if (!(*reached_map)[w]) {
    105113              bfs_queue.push(w);
    106               reached.set(w, true);
     114              reached_map->set(w, true);
    107115              b_node_newly_reached=true;
    108116            } else {
     
    130138    /// Guess what?
    131139    /// \deprecated
    132     const ReachedMap& getReachedMap() const { return reached; }
     140    const ReachedMap& reachedMap() const { return *reached_map; }
     141    /// Guess what?
     142    /// \deprecated
     143    typename ReachedMap::ValueType reached(const Node& n) const {
     144      return (*reached_map)[n];
     145    }
    133146    /// Guess what?
    134147    /// \deprecated
     
    138151  /// Bfs searches for the nodes wich are not marked in
    139152  /// \c reached_map
    140   /// Reached have to work as a read-write bool Node-map,
    141   /// Pred is a write edge node-map and
    142   /// Dist is a read-write node-map of integral value, have to be.
     153  /// RM have to work as a read-write bool Node-map,
     154  /// PM is a write edge node-map and
     155  /// PNM is a write node node-map and
     156  /// DM is a read-write node-map of integral value, have to be.
    143157  /// \ingroup galgs
    144158  template <typename Graph,
    145             typename ReachedMap=typename Graph::template NodeMap<bool>,
    146             typename PredMap
     159            typename RM=typename Graph::template NodeMap<bool>,
     160            typename PM
    147161            =typename Graph::template NodeMap<typename Graph::Edge>,
    148             typename DistMap=typename Graph::template NodeMap<int> >
    149   class Bfs : public BfsIterator<Graph, ReachedMap> {
    150     typedef BfsIterator<Graph, ReachedMap> Parent;
     162            typename PNM
     163            =typename Graph::template NodeMap<typename Graph::Node>,
     164            typename DM=typename Graph::template NodeMap<int> >
     165  class Bfs : public BfsIterator<Graph, RM> {
     166    typedef BfsIterator<Graph, RM> Parent;
     167  public:
     168    typedef RM ReachedMap;
     169    typedef PM PredMap;
     170    typedef PNM PredNodeMap;
     171    typedef DM DistMap;
    151172  protected:
    152173    typedef typename Parent::Node Node;
    153     PredMap& pred;
    154     DistMap& dist;
     174    PredMap* pred_map;
     175    PredNodeMap* pred_node_map;
     176    DistMap* dist_map;
     177    /// \e
     178    Bfs<Graph, RM, PM, PNM, DM>
     179    (const Graph& _graph) : BfsIterator<Graph, RM>(_graph) { }
     180    /// PM have to be set before any bfs operation.
     181    Bfs<Graph, RM, PM, PNM, DM>&
     182    setPredMap(PredMap& _pred_map) {
     183      pred_map=&_pred_map;
     184    }
     185    /// PredNodeMap have to be set before any bfs operation.
     186    Bfs<Graph, RM, PM, PNM, DM>&
     187    setPredNodeMap(PredNodeMap& _pred_node_map) {
     188      pred_node_map=&_pred_node_map;
     189    }
     190    /// DistMap have to be set before any bfs operation.
     191    Bfs<Graph, RM, PM, PNM, DM>&
     192    setDistMap(DistMap& _dist_map) {
     193      dist_map=&_dist_map;
     194    }
    155195  public:
    156196    /// The algorithm will search in a bfs order for
    157197    /// the nodes which are \c false initially.
    158198    /// The constructor makes no initial changes on the maps.
    159     Bfs<Graph, ReachedMap, PredMap, DistMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred, DistMap& _dist) :
    160       BfsIterator<Graph, ReachedMap>(_graph, _reached),
    161       pred(_pred), dist(_dist) { }
     199    Bfs<Graph, RM, PM, PNM, DM>
     200    (const Graph& _graph, ReachedMap& _reached_map,
     201     PredMap& _pred_map, PredNodeMap& _pred_node_map,
     202     DistMap& _dist_map) : BfsIterator<Graph, RM>(_graph, _reached_map),
     203      pred_map(&_pred_map), pred_node_map(&_pred_node_map),
     204                           dist_map(&_dist_map) { }
    162205    /// \c s is marked to be reached and pushed in the bfs queue.
    163206    /// If the queue is empty, then the first out-edge is processed.
    164207    /// If \c s was not marked previously, then
    165     /// in addition its pred is set to be \c INVALID, and dist to \c 0.
     208    /// in addition its pred_map is set to be \c INVALID,
     209    /// and dist_map to \c 0.
    166210    /// if \c s was marked previuosly, then it is simply pushed.
    167     Bfs<Graph, ReachedMap, PredMap, DistMap>& push(Node s) {
    168       if (this->reached[s]) {
     211    Bfs<Graph, RM, PM, PNM, DM>& push(Node s) {
     212      if ((*(this->reached_map))[s]) {
    169213        Parent::pushAndSetReached(s);
    170214      } else {
    171215        Parent::pushAndSetReached(s);
    172         pred.set(s, INVALID);
    173         dist.set(s, 0);
     216        pred_map->set(s, INVALID);
     217        pred_node_map->set(s, INVALID);
     218        dist_map->set(s, 0);
    174219      }
    175220      return *this;
    176221    }
    177222    /// A bfs is processed from \c s.
    178     Bfs<Graph, ReachedMap, PredMap, DistMap>& run(Node s) {
     223    Bfs<Graph, RM, PM, PNM, DM>& run(Node s) {
    179224      push(s);
    180225      while (!this->finished()) this->operator++();
    181226      return *this;
    182227    }
    183     /// Beside the bfs iteration, \c pred and \dist are saved in a
     228    /// Beside the bfs iteration, \c pred_map and \dist_map are saved in a
    184229    /// newly reached node.
    185     Bfs<Graph, ReachedMap, PredMap, DistMap>& operator++() {
     230    Bfs<Graph, RM, PM, PNM, DM>& operator++() {
    186231      Parent::operator++();
    187       if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached)
     232      if ((this->actual_edge)!=INVALID && this->b_node_newly_reached)
    188233      {
    189         pred.set(this->head(), this->actual_edge);
    190         dist.set(this->head(), dist[this->tail()]);
    191       }
    192       return *this;
    193     }
    194     /// Guess what?
    195     /// \deprecated
    196     const PredMap& getPredMap() const { return pred; }
     234        pred_map->set(this->head(), this->actual_edge);
     235        pred_node_map->set(this->head(), this->tail());
     236        dist_map->set(this->head(), (*dist_map)[this->tail()]);
     237      }
     238      return *this;
     239    }
     240    /// Guess what?
     241    /// \deprecated
     242    const PredMap& predMap() const { return *pred_map; }
     243    /// Guess what?
     244    /// \deprecated
     245    typename PredMap::ValueType pred(const Node& n) const {
     246      return (*pred_map)[n];
     247    }
     248    /// Guess what?
     249    /// \deprecated
     250    const PredNodeMap& predNodeMap() const { return *pred_node_map; }
     251    /// Guess what?
     252    /// \deprecated
     253    typename PredNodeMap::ValueType predNode(const Node& n) const {
     254      return (*pred_node_map)[n];
     255    }
    197256    /// Guess what?
    198257    /// \deprecated
    199     const DistMap& getDistMap() const { return dist; }
     258    const DistMap& distMap() const { return *dist_map; }
     259    /// Guess what?
     260    /// \deprecated
     261    typename DistMap::ValueType dist(const Node& n) const {
     262      return (*dist_map)[n];
     263    }
    200264  };
     265
     266//   template <typename Graph,
     267//          typename RM=typename Graph::template NodeMap<bool>,
     268//          typename PM
     269//          =typename Graph::template NodeMap<typename Graph::Edge>,
     270//          typename PredNodeMap
     271//          =typename Graph::template NodeMap<typename Graph::Node>,
     272//          typename DistMap=typename Graph::template NodeMap<int> >
     273//     class BfsWizard : public Bfs<Graph> {
     274//     public:
     275//       typedef Bfs<Graph, PM, PredNodeMap, DistMap> Parent;
     276//     protected:
     277//       typedef typename Parent::Node Node;
     278//       bool own_reached_map;
     279//       bool own_pred_map;
     280//       bool own_pred_node_map;
     281//       bool own_dist_map;
     282
     283//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
     284//       makeRreached() {
     285//      own_reached_map=true;
     286//      reached=new ReachedMap(*graph, false);
     287//       }
     288//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
     289//       deleteReachedMap() {
     290//      own_reached_map=false;
     291//      delete reached;
     292//       }
     293
     294//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
     295//       makePM() {
     296//      own_pred_map=true;
     297//      pred_map=new PM(*graph, INVALID);
     298//       }
     299//       BfsWizard<Graph, ReachedMap, PM, PredNodeMap, DistMap>&
     300//       deletePM() {
     301//      own_pred_map=false;
     302//      delete pred_map;
     303//       }
     304
     305//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
     306//       makePredNodeMap() {
     307//      own_pred_node_map=true;
     308//      pred_node_map=new PredNodeMap(*graph, INVALID);
     309//       }
     310//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
     311//       deletePredNodeMap() {
     312//      own_pred_node_map=false;
     313//      delete pred_node_map;
     314//       }
     315
     316//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
     317//       makeDistMap() {
     318//      own_dist_map=true;
     319//      dist_map=new DistMap(*graph, 0);
     320//       }
     321//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
     322//       deleteDistMap() {
     323//      own_dist_map=false;
     324//      delete dist_map;
     325//       }
     326
     327//     public:
     328//       /// User friendly Bfs class.
     329//       /// The maps which are not explicitly given by the user are
     330//       /// constructed with false, INVALID, INVALID and 0 values.
     331//       /// For the user defined maps, the values are not modified, and
     332//       /// the bfs is processed without any preset on maps. Therefore,
     333//       /// the bfs will search only the nodes which are set false previously
     334//       /// in reached, and in the nodes wich are not newly reached by the
     335//       /// search, the map values are not modified.
     336//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>
     337//       (const Graph& _graph) :
     338//      own_reached_map(false),
     339//      own_pred_map(false),
     340//      own_pred_node_map(false),
     341//      own_dist_map(false) {
     342//       }
     343
     344//       /// \e
     345//       ~BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>() {
     346//      if (own_reached_map) deleteReachedMap();
     347//      if (own_pred_map) deletePM();
     348//      if (own_pred_node_map) deletePredNodeMap();
     349//      if (own_dist_map) deleteDistMap();
     350//       }
     351
     352//       /// \e
     353//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
     354//       setReachedMap(ReachedMap& _reached) {
     355//      if (own_reached_map) deleteReachedMap();
     356//      Parent::setReachedMap(_reached);
     357//       }
     358//       /// \e
     359//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
     360//       setPM(PM& _pred) {
     361//      if (own_pred_map) deletePM();
     362//      Parent::setPM(_pred);
     363//       }
     364//       /// \e
     365//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
     366//       setPredNodeMap(PredNodeMap& _pred_node) {
     367//      if (own_pred_node_map) deletePredNodeMap();
     368//      Parent::setPredNodeMap(_pred_node);
     369//       }
     370//       /// \e
     371//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
     372//       setDistMap(DistMap& _dist) {
     373//      if (own_dist_map) deleteDistMap();
     374//      Parent::setDistMap(_dist);
     375//       }
     376
     377//       /// \e
     378//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
     379//       push(Node s) {
     380//      if (!reached) makeReachedMap();
     381//      if (!pred_map) makePMMap();
     382//      if (!pred_node_map) makePredNodeMap();
     383//      if (!dist_map) makeDistMap();
     384//      push(s);
     385//      return *this;
     386//       }
     387
     388//       /// \e
     389//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
     390//       operator++() {
     391//      if (!reached) makeRM();
     392//      if (!pred_map) makePMMap();
     393//      if (!pred_node_map) makePredNodeMap();
     394//      if (!dist_map) makeDistMap();
     395//      ++(*this);
     396//      return *this;
     397//       }
     398
     399//       /// \e
     400//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
     401//       run(Node s) {
     402//      if (!reached) makeRM();
     403//      if (!pred_map) makePMMap();
     404//      if (!pred_node_map) makePredNodeMap();
     405//      if (!dist_map) makeDistMap();
     406//      run(s);
     407//      return *this;
     408//       }
     409     
     410//     };
     411
    201412
    202413  /// Dfs searches for the nodes wich are not marked in
     
    343554  };
    344555
    345 
     556  } // namespace marci
    346557} // namespace lemon
    347558
  • src/work/marci/bfs_mm_test.cc

    r921 r944  
    1515 */
    1616
    17 #include "test_tools.h"
     17#include <test/test_tools.h>
    1818#include <lemon/smart_graph.h>
    19 #include <lemon/bfs.h>
    20 #include<lemon/skeletons/graph.h>
     19#include <bfs_mm.h>
     20#include <lemon/skeletons/graph.h>
    2121
    2222using namespace lemon;
     
    3434  typedef Graph::NodeIt NodeIt;
    3535 
    36   typedef Bfs<Graph> BType;
     36  typedef marci::Bfs<Graph> BType;
    3737 
    3838  Graph G;
     
    4444  BType::PredMap p(G);
    4545  BType::PredNodeMap pn(G);
    46  
    47   BType bfs_test(G);
     46
     47   Graph::NodeMap<bool> reached(G);
     48   Graph::NodeMap<Edge> pred(G);
     49   Graph::NodeMap<Node> pred_node(G);
     50   Graph::NodeMap<int> dist(G); 
     51   BType bfs_test(G, reached, pred, pred_node, dist);
    4852 
    4953  bfs_test.run(n);
     
    7781  t=ps.inner[0];
    7882 
    79   Bfs<Graph> bfs_test(G);
     83   Graph::NodeMap<bool> reached(G);
     84   Graph::NodeMap<Edge> pred(G);
     85   Graph::NodeMap<Node> pred_node(G);
     86   Graph::NodeMap<int> dist(G);
     87   marci::Bfs<Graph> bfs_test(G, reached, pred, pred_node, dist);
    8088  bfs_test.run(s);
    8189 
    82   check(bfs_test.dist(t)==3,"Bfs found a wrong path. " << bfs_test.dist(t));
     90//   check(bfs_test.dist(t)==3,"Bfs found a wrong path. " << bfs_test.dist(t));
    8391
    8492
    85   for(EdgeIt e(G); e==INVALID; ++e) {
    86     Node u=G.tail(e);
    87     Node v=G.head(e);
    88     check( !bfs_test.reached(u) ||
    89            (bfs_test.dist(v) > bfs_test.dist(u)+1),
    90            "Wrong output.");
    91   }
     93//   for(EdgeIt e(G); e==INVALID; ++e) {
     94//     Node u=G.tail(e);
     95//     Node v=G.head(e);
     96//     check( !bfs_test.reached(u) ||
     97//         (bfs_test.dist(v) > bfs_test.dist(u)+1),
     98//         "Wrong output.");
     99//   }
    92100
    93   for(NodeIt v(G); v==INVALID; ++v) {
    94     check(bfs_test.reached(v),"Each node should be reached.");
    95     if ( bfs_test.pred(v)!=INVALID ) {
    96       Edge e=bfs_test.pred(v);
    97       Node u=G.tail(e);
    98       check(u==bfs_test.predNode(v),"Wrong tree.");
    99       check(bfs_test.dist(v) - bfs_test.dist(u) == 1,
    100             "Wrong distance. Difference: "
    101             << std::abs(bfs_test.dist(v) - bfs_test.dist(u)
    102                         - 1));
    103     }
    104   }
     101//   for(NodeIt v(G); v==INVALID; ++v) {
     102//     check(bfs_test.reached(v),"Each node should be reached.");
     103//     if ( bfs_test.pred(v)!=INVALID ) {
     104//       Edge e=bfs_test.pred(v);
     105//       Node u=G.tail(e);
     106//       check(u==bfs_test.predNode(v),"Wrong tree.");
     107//       check(bfs_test.dist(v) - bfs_test.dist(u) == 1,
     108//          "Wrong distance. Difference: "
     109//          << std::abs(bfs_test.dist(v) - bfs_test.dist(u)
     110//                      - 1));
     111//     }
     112//   }
    105113}
    106114
  • src/work/marci/bfsit_vs_byhand.cc

    r921 r944  
    33#include <fstream>
    44
    5 #include <sage_graph.h>
     5//#include <sage_graph.h>
    66#include <lemon/smart_graph.h>
     7#include <lemon/list_graph.h>
    78#include <lemon/dimacs.h>
    89#include <lemon/time_measure.h>
    910//#include <lemon/for_each_macros.h>
    10 #include <bfs_dfs.h>
     11#include <bfs_mm.h>
     12#include <lemon/bfs.h>
    1113
    1214using namespace lemon;
     
    1618
    1719int main() {
    18   typedef SageGraph Graph;
     20  //  typedef SageGraph Graph;
     21  typedef SmartGraph Graph ;
     22  //typedef ListGraph Graph;
    1923  typedef Graph::Node Node;
    2024  typedef Graph::NodeIt NodeIt;
     
    2428
    2529  Graph g;
    26   //Node s;
    27   //Graph::EdgeMap<int> cap(g);
    28   //readDimacsMaxFlow(std::cin, g, s, t, cap);
    2930  readDimacs(std::cin, g);
    30   NodeIt s;
    31   g.first(s);
     31  NodeIt s(g);
    3232
    3333  cout << g.nodeNum() << endl;
     
    3737  cout << "iteration time of bfs written by hand..." << endl;
    3838  Timer ts;
     39  ts.reset();
     40  for (int i=0; i<100; ++i)
    3941  {
    40     ts.reset();
    4142    Graph::NodeMap<bool> reached(g);
    4243    reached.set(s, true);
     
    4748      Node v=bfs_queue.front();
    4849      bfs_queue.pop();
    49       OutEdgeIt e;
    50       for(g.first(e,v); g.valid(e); g.next(e)) {
     50      for(OutEdgeIt e(g,v); e!=INVALID; ++e) {
    5151        Node w=g.head(e);
    5252        if (!reached[w]) {
     
    5757      }
    5858    }
    59 
    60     std::cout << ts << std::endl;
    6159  }
     60  std::cout << ts << std::endl;
    6261
    6362  cout << "iteration time with bfs iterator..." << endl;
     63  ts.reset();     
     64  for (int i=0; i<100; ++i)
    6465  {
    65     ts.reset();     
    66     BfsIterator< Graph, Graph::NodeMap<bool> > bfs(g);
     66    Graph::NodeMap<bool> reached(g);
     67    marci::BfsIterator< Graph, Graph::NodeMap<bool> > bfs(g, reached);
    6768    bfs.pushAndSetReached(s);
    6869    pred.set(s, INVALID);
    6970    while (!bfs.finished()) {
    7071      ++bfs;
    71       if (g.valid(bfs) && bfs.isBNodeNewlyReached())
     72      if (Graph::Edge(bfs)!=INVALID && bfs.isBNodeNewlyReached())
    7273        pred.set(bfs.head(), Graph::Edge(bfs));
    7374    }
    74     std::cout << ts << std::endl;
    7575  }
     76  std::cout << ts << std::endl;
     77
     78  cout << "iteration time with bfs aplar..." << endl;
     79  ts.reset();     
     80  for (int i=0; i<100; ++i)
     81  {
     82    Bfs<Graph> bfs(g);
     83    bfs.setPredMap(pred);
     84    bfs.run(s);
     85  }
     86  std::cout << ts << std::endl;
     87
    7688
    7789  return 0;
  • src/work/marci/makefile

    r915 r944  
    55
    66LEDABINARIES = leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo
    7 BINARIES = merge_node_graph_wrapper_test#sub_graph_wrapper_demo.cc graph_wrapper_time max_flow_demo iterator_bfs_demo macro_test lg_vs_sg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test bipartite_matching_demo top_sort_test max_flow_1 proba7 proba10
     7BINARIES = bfsit_vs_byhand max_flow_demo bfs_mm_test#merge_node_graph_wrapper_test sub_graph_wrapper_demo.cc graph_wrapper_time iterator_bfs_demo macro_test lg_vs_sg_vs_sg bipartite_graph_wrapper_test bipartite_matching_demo top_sort_test max_flow_1 proba7 proba10
    88#BINARIES = preflow_bug
    99#gw_vs_not preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos edmonds_karp_demo_alpar preflow_demo_leda
Note: See TracChangeset for help on using the changeset viewer.