COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bfs.h @ 1694:6d81e6f7a88d

Last change on this file since 1694:6d81e6f7a88d was 1694:6d81e6f7a88d, checked in by Balazs Dezso, 14 years ago

Fixing naming conventions
Temporarly bugfix with named-parameters
Removing dead codes

File size: 35.4 KB
Line 
1/* -*- C++ -*-
2 * lemon/bfs.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
6 *
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
10 *
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
13 * purpose.
14 *
15 */
16
17#ifndef LEMON_BFS_H
18#define LEMON_BFS_H
19
20///\ingroup flowalgs
21///\file
22///\brief Bfs algorithm.
23
24#include <lemon/list_graph.h>
25#include <lemon/graph_utils.h>
26#include <lemon/invalid.h>
27#include <lemon/error.h>
28#include <lemon/maps.h>
29
30namespace lemon {
31
32
33 
34  ///Default traits class of Bfs class.
35
36  ///Default traits class of Bfs class.
37  ///\param GR Graph type.
38  template<class GR>
39  struct BfsDefaultTraits
40  {
41    ///The graph type the algorithm runs on.
42    typedef GR Graph;
43    ///\brief The type of the map that stores the last
44    ///edges of the shortest paths.
45    ///
46    ///The type of the map that stores the last
47    ///edges of the shortest paths.
48    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
49    ///
50    typedef typename Graph::template NodeMap<typename GR::Edge> PredMap;
51    ///Instantiates a PredMap.
52 
53    ///This function instantiates a \ref PredMap.
54    ///\param G is the graph, to which we would like to define the PredMap.
55    ///\todo The graph alone may be insufficient to initialize
56    static PredMap *createPredMap(const GR &G)
57    {
58      return new PredMap(G);
59    }
60//     ///\brief The type of the map that stores the last but one
61//     ///nodes of the shortest paths.
62//     ///
63//     ///The type of the map that stores the last but one
64//     ///nodes of the shortest paths.
65//     ///It must meet the \ref concept::WriteMap "WriteMap" concept.
66//     ///
67//     typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
68//     ///Instantiates a PredNodeMap.
69   
70//     ///This function instantiates a \ref PredNodeMap.
71//     ///\param G is the graph, to which
72//     ///we would like to define the \ref PredNodeMap
73//     static PredNodeMap *createPredNodeMap(const GR &G)
74//     {
75//       return new PredNodeMap();
76//     }
77
78    ///The type of the map that indicates which nodes are processed.
79 
80    ///The type of the map that indicates which nodes are processed.
81    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
82    ///\todo named parameter to set this type, function to read and write.
83    typedef NullMap<typename Graph::Node,bool> ProcessedMap;
84    ///Instantiates a ProcessedMap.
85 
86    ///This function instantiates a \ref ProcessedMap.
87    ///\param g is the graph, to which
88    ///we would like to define the \ref ProcessedMap
89#ifdef DOXYGEN
90    static ProcessedMap *createProcessedMap(const GR &g)
91#else
92    static ProcessedMap *createProcessedMap(const GR &)
93#endif
94    {
95      return new ProcessedMap();
96    }
97    ///The type of the map that indicates which nodes are reached.
98 
99    ///The type of the map that indicates which nodes are reached.
100    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
101    ///\todo named parameter to set this type, function to read and write.
102    typedef typename Graph::template NodeMap<bool> ReachedMap;
103    ///Instantiates a ReachedMap.
104 
105    ///This function instantiates a \ref ReachedMap.
106    ///\param G is the graph, to which
107    ///we would like to define the \ref ReachedMap.
108    static ReachedMap *createReachedMap(const GR &G)
109    {
110      return new ReachedMap(G);
111    }
112    ///The type of the map that stores the dists of the nodes.
113 
114    ///The type of the map that stores the dists of the nodes.
115    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
116    ///
117    typedef typename Graph::template NodeMap<int> DistMap;
118    ///Instantiates a DistMap.
119 
120    ///This function instantiates a \ref DistMap.
121    ///\param G is the graph, to which we would like to define the \ref DistMap
122    static DistMap *createDistMap(const GR &G)
123    {
124      return new DistMap(G);
125    }
126  };
127 
128  ///%BFS algorithm class.
129 
130  ///\ingroup flowalgs
131  ///This class provides an efficient implementation of the %BFS algorithm.
132  ///
133  ///\param GR The graph type the algorithm runs on. The default value is
134  ///\ref ListGraph. The value of GR is not used directly by Bfs, it
135  ///is only passed to \ref BfsDefaultTraits.
136  ///\param TR Traits class to set various data types used by the algorithm.
137  ///The default traits class is
138  ///\ref BfsDefaultTraits "BfsDefaultTraits<GR>".
139  ///See \ref BfsDefaultTraits for the documentation of
140  ///a Bfs traits class.
141  ///
142  ///\author Alpar Juttner
143  ///\todo A compare object would be nice.
144
145#ifdef DOXYGEN
146  template <typename GR,
147            typename TR>
148#else
149  template <typename GR=ListGraph,
150            typename TR=BfsDefaultTraits<GR> >
151#endif
152  class Bfs {
153  public:
154    /**
155     * \brief \ref Exception for uninitialized parameters.
156     *
157     * This error represents problems in the initialization
158     * of the parameters of the algorithms.
159     */
160    class UninitializedParameter : public lemon::UninitializedParameter {
161    public:
162      virtual const char* exceptionName() const {
163        return "lemon::Bfs::UninitializedParameter";
164      }
165    };
166
167    typedef TR Traits;
168    ///The type of the underlying graph.
169    typedef typename TR::Graph Graph;
170    ///\e
171    typedef typename Graph::Node Node;
172    ///\e
173    typedef typename Graph::NodeIt NodeIt;
174    ///\e
175    typedef typename Graph::Edge Edge;
176    ///\e
177    typedef typename Graph::OutEdgeIt OutEdgeIt;
178   
179    ///\brief The type of the map that stores the last
180    ///edges of the shortest paths.
181    typedef typename TR::PredMap PredMap;
182//     ///\brief The type of the map that stores the last but one
183//     ///nodes of the shortest paths.
184//     typedef typename TR::PredNodeMap PredNodeMap;
185    ///The type of the map indicating which nodes are reached.
186    typedef typename TR::ReachedMap ReachedMap;
187    ///The type of the map indicating which nodes are processed.
188    typedef typename TR::ProcessedMap ProcessedMap;
189    ///The type of the map that stores the dists of the nodes.
190    typedef typename TR::DistMap DistMap;
191  private:
192    /// Pointer to the underlying graph.
193    const Graph *G;
194    ///Pointer to the map of predecessors edges.
195    PredMap *_pred;
196    ///Indicates if \ref _pred is locally allocated (\c true) or not.
197    bool local_pred;
198//     ///Pointer to the map of predecessors nodes.
199//     PredNodeMap *_predNode;
200//     ///Indicates if \ref _predNode is locally allocated (\c true) or not.
201//     bool local_predNode;
202    ///Pointer to the map of distances.
203    DistMap *_dist;
204    ///Indicates if \ref _dist is locally allocated (\c true) or not.
205    bool local_dist;
206    ///Pointer to the map of reached status of the nodes.
207    ReachedMap *_reached;
208    ///Indicates if \ref _reached is locally allocated (\c true) or not.
209    bool local_reached;
210    ///Pointer to the map of processed status of the nodes.
211    ProcessedMap *_processed;
212    ///Indicates if \ref _processed is locally allocated (\c true) or not.
213    bool local_processed;
214
215    std::vector<typename Graph::Node> _queue;
216    int _queue_head,_queue_tail,_queue_next_dist;
217    int _curr_dist;
218//     ///The source node of the last execution.
219//     Node source;
220
221    ///Creates the maps if necessary.
222   
223    ///\todo Error if \c G are \c NULL.
224    ///\todo Better memory allocation (instead of new).
225    void create_maps()
226    {
227      if(!_pred) {
228        local_pred = true;
229        _pred = Traits::createPredMap(*G);
230      }
231//       if(!_predNode) {
232//      local_predNode = true;
233//      _predNode = Traits::createPredNodeMap(*G);
234//       }
235      if(!_dist) {
236        local_dist = true;
237        _dist = Traits::createDistMap(*G);
238      }
239      if(!_reached) {
240        local_reached = true;
241        _reached = Traits::createReachedMap(*G);
242      }
243      if(!_processed) {
244        local_processed = true;
245        _processed = Traits::createProcessedMap(*G);
246      }
247    }
248   
249  public :
250 
251    ///\name Named template parameters
252
253    ///@{
254
255    template <class T>
256    struct DefPredMapTraits : public Traits {
257      typedef T PredMap;
258      static PredMap *createPredMap(const Graph &G)
259      {
260        throw UninitializedParameter();
261      }
262    };
263    ///\ref named-templ-param "Named parameter" for setting PredMap type
264
265    ///\ref named-templ-param "Named parameter" for setting PredMap type
266    ///
267    template <class T>
268    class DefPredMap : public Bfs< Graph, DefPredMapTraits<T> > { };
269   
270//     template <class T>
271//     struct DefPredNodeMapTraits : public Traits {
272//       typedef T PredNodeMap;
273//       static PredNodeMap *createPredNodeMap(const Graph &G)
274//       {
275//      throw UninitializedParameter();
276//       }
277//     };
278//     ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
279
280//     ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
281//     ///
282//     template <class T>
283//     class DefPredNodeMap : public Bfs< Graph,
284//                                          LengthMap,
285//                                          DefPredNodeMapTraits<T> > { };
286   
287    template <class T>
288    struct DefDistMapTraits : public Traits {
289      typedef T DistMap;
290      static DistMap *createDistMap(const Graph &G)
291      {
292        throw UninitializedParameter();
293      }
294    };
295    ///\ref named-templ-param "Named parameter" for setting DistMap type
296
297    ///\ref named-templ-param "Named parameter" for setting DistMap type
298    ///
299    template <class T>
300    class DefDistMap : public Bfs< Graph,
301                                   DefDistMapTraits<T> > { };
302   
303    template <class T>
304    struct DefReachedMapTraits : public Traits {
305      typedef T ReachedMap;
306      static ReachedMap *createReachedMap(const Graph &G)
307      {
308        throw UninitializedParameter();
309      }
310    };
311    ///\ref named-templ-param "Named parameter" for setting ReachedMap type
312
313    ///\ref named-templ-param "Named parameter" for setting ReachedMap type
314    ///
315    template <class T>
316    class DefReachedMap : public Bfs< Graph,
317                                      DefReachedMapTraits<T> > { };
318   
319    struct DefGraphReachedMapTraits : public Traits {
320      typedef typename Graph::template NodeMap<bool> ReachedMap;
321      static ReachedMap *createReachedMap(const Graph &G)
322      {
323        return new ReachedMap(G);
324      }
325    };
326    template <class T>
327    struct DefProcessedMapTraits : public Traits {
328      typedef T ProcessedMap;
329      static ProcessedMap *createProcessedMap(const Graph &G)
330      {
331        throw UninitializedParameter();
332      }
333    };
334    ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
335
336    ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
337    ///
338    template <class T>
339    class DefProcessedMap : public Bfs< Graph,
340                                        DefProcessedMapTraits<T> > { };
341   
342    struct DefGraphProcessedMapTraits : public Traits {
343      typedef typename Graph::template NodeMap<bool> ProcessedMap;
344      static ProcessedMap *createProcessedMap(const Graph &G)
345      {
346        return new ProcessedMap(G);
347      }
348    };
349    ///\brief \ref named-templ-param "Named parameter"
350    ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
351    ///
352    ///\ref named-templ-param "Named parameter"
353    ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
354    ///If you don't set it explicitly, it will be automatically allocated.
355    template <class T>
356    class DefProcessedMapToBeDefaultMap :
357      public Bfs< Graph,
358                  DefGraphProcessedMapTraits> { };
359   
360    ///@}
361
362  public:     
363   
364    ///Constructor.
365   
366    ///\param _G the graph the algorithm will run on.
367    ///
368    Bfs(const Graph& _G) :
369      G(&_G),
370      _pred(NULL), local_pred(false),
371//       _predNode(NULL), local_predNode(false),
372      _dist(NULL), local_dist(false),
373      _reached(NULL), local_reached(false),
374      _processed(NULL), local_processed(false)
375    { }
376   
377    ///Destructor.
378    ~Bfs()
379    {
380      if(local_pred) delete _pred;
381//       if(local_predNode) delete _predNode;
382      if(local_dist) delete _dist;
383      if(local_reached) delete _reached;
384      if(local_processed) delete _processed;
385    }
386
387    ///Sets the map storing the predecessor edges.
388
389    ///Sets the map storing the predecessor edges.
390    ///If you don't use this function before calling \ref run(),
391    ///it will allocate one. The destructor deallocates this
392    ///automatically allocated map, of course.
393    ///\return <tt> (*this) </tt>
394    Bfs &predMap(PredMap &m)
395    {
396      if(local_pred) {
397        delete _pred;
398        local_pred=false;
399      }
400      _pred = &m;
401      return *this;
402    }
403
404    ///Sets the map indicating the reached nodes.
405
406    ///Sets the map indicating the reached nodes.
407    ///If you don't use this function before calling \ref run(),
408    ///it will allocate one. The destructor deallocates this
409    ///automatically allocated map, of course.
410    ///\return <tt> (*this) </tt>
411    Bfs &reachedMap(ReachedMap &m)
412    {
413      if(local_reached) {
414        delete _reached;
415        local_reached=false;
416      }
417      _reached = &m;
418      return *this;
419    }
420
421    ///Sets the map indicating the processed nodes.
422
423    ///Sets the map indicating the processed nodes.
424    ///If you don't use this function before calling \ref run(),
425    ///it will allocate one. The destructor deallocates this
426    ///automatically allocated map, of course.
427    ///\return <tt> (*this) </tt>
428    Bfs &processedMap(ProcessedMap &m)
429    {
430      if(local_processed) {
431        delete _processed;
432        local_processed=false;
433      }
434      _processed = &m;
435      return *this;
436    }
437
438//     ///Sets the map storing the predecessor nodes.
439
440//     ///Sets the map storing the predecessor nodes.
441//     ///If you don't use this function before calling \ref run(),
442//     ///it will allocate one. The destructor deallocates this
443//     ///automatically allocated map, of course.
444//     ///\return <tt> (*this) </tt>
445//     Bfs &predNodeMap(PredNodeMap &m)
446//     {
447//       if(local_predNode) {
448//      delete _predNode;
449//      local_predNode=false;
450//       }
451//       _predNode = &m;
452//       return *this;
453//     }
454
455    ///Sets the map storing the distances calculated by the algorithm.
456
457    ///Sets the map storing the distances calculated by the algorithm.
458    ///If you don't use this function before calling \ref run(),
459    ///it will allocate one. The destructor deallocates this
460    ///automatically allocated map, of course.
461    ///\return <tt> (*this) </tt>
462    Bfs &distMap(DistMap &m)
463    {
464      if(local_dist) {
465        delete _dist;
466        local_dist=false;
467      }
468      _dist = &m;
469      return *this;
470    }
471
472  public:
473    ///\name Execution control
474    ///The simplest way to execute the algorithm is to use
475    ///one of the member functions called \c run(...).
476    ///\n
477    ///If you need more control on the execution,
478    ///first you must call \ref init(), then you can add several source nodes
479    ///with \ref addSource().
480    ///Finally \ref start() will perform the actual path
481    ///computation.
482
483    ///@{
484
485    ///Initializes the internal data structures.
486
487    ///Initializes the internal data structures.
488    ///
489    void init()
490    {
491      create_maps();
492      _queue.resize(countNodes(*G));
493      _queue_head=_queue_tail=0;
494      _curr_dist=1;
495      for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
496        _pred->set(u,INVALID);
497//      _predNode->set(u,INVALID);
498        _reached->set(u,false);
499        _processed->set(u,false);
500      }
501    }
502   
503    ///Adds a new source node.
504
505    ///Adds a new source node to the set of nodes to be processed.
506    ///
507    void addSource(Node s)
508    {
509      if(!(*_reached)[s])
510        {
511          _reached->set(s,true);
512          _pred->set(s,INVALID);
513          _dist->set(s,0);
514          _queue[_queue_head++]=s;
515          _queue_next_dist=_queue_head;
516        }
517    }
518   
519    ///Processes the next node.
520
521    ///Processes the next node.
522    ///
523    ///\return The processed node.
524    ///
525    ///\warning The queue must not be empty!
526    Node processNextNode()
527    {
528      if(_queue_tail==_queue_next_dist) {
529        _curr_dist++;
530        _queue_next_dist=_queue_head;
531      }
532      Node n=_queue[_queue_tail++];
533      _processed->set(n,true);
534      Node m;
535      for(OutEdgeIt e(*G,n);e!=INVALID;++e)
536        if(!(*_reached)[m=G->target(e)]) {
537          _queue[_queue_head++]=m;
538          _reached->set(m,true);
539          _pred->set(m,e);
540//        _pred_node->set(m,n);
541          _dist->set(m,_curr_dist);
542        }
543      return n;
544    }
545     
546    ///Next node to be processed.
547
548    ///Next node to be processed.
549    ///
550    ///\return The next node to be processed or INVALID if the queue is
551    /// empty.
552    Node nextNode()
553    {
554      return _queue_tail<_queue_head?_queue[_queue_tail]:INVALID;
555    }
556 
557    ///\brief Returns \c false if there are nodes
558    ///to be processed in the queue
559    ///
560    ///Returns \c false if there are nodes
561    ///to be processed in the queue
562    bool emptyQueue() { return _queue_tail==_queue_head; }
563    ///Returns the number of the nodes to be processed.
564   
565    ///Returns the number of the nodes to be processed in the queue.
566    ///
567    int queueSize() { return _queue_head-_queue_tail; }
568   
569    ///Executes the algorithm.
570
571    ///Executes the algorithm.
572    ///
573    ///\pre init() must be called and at least one node should be added
574    ///with addSource() before using this function.
575    ///
576    ///This method runs the %BFS algorithm from the root node(s)
577    ///in order to
578    ///compute the
579    ///shortest path to each node. The algorithm computes
580    ///- The shortest path tree.
581    ///- The distance of each node from the root(s).
582    ///
583    void start()
584    {
585      while ( !emptyQueue() ) processNextNode();
586    }
587   
588    ///Executes the algorithm until \c dest is reached.
589
590    ///Executes the algorithm until \c dest is reached.
591    ///
592    ///\pre init() must be called and at least one node should be added
593    ///with addSource() before using this function.
594    ///
595    ///This method runs the %BFS algorithm from the root node(s)
596    ///in order to
597    ///compute the
598    ///shortest path to \c dest. The algorithm computes
599    ///- The shortest path to \c  dest.
600    ///- The distance of \c dest from the root(s).
601    ///
602    void start(Node dest)
603    {
604      while ( !emptyQueue() && _queue[_queue_tail]!=dest ) processNextNode();
605    }
606   
607    ///Executes the algorithm until a condition is met.
608
609    ///Executes the algorithm until a condition is met.
610    ///
611    ///\pre init() must be called and at least one node should be added
612    ///with addSource() before using this function.
613    ///
614    ///\param nm must be a bool (or convertible) node map. The algorithm
615    ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
616    template<class NM>
617      void start(const NM &nm)
618      {
619        while ( !emptyQueue() && !nm[_queue[_queue_tail]] ) processNextNode();
620      }
621   
622    ///Runs %BFS algorithm from node \c s.
623   
624    ///This method runs the %BFS algorithm from a root node \c s
625    ///in order to
626    ///compute the
627    ///shortest path to each node. The algorithm computes
628    ///- The shortest path tree.
629    ///- The distance of each node from the root.
630    ///
631    ///\note d.run(s) is just a shortcut of the following code.
632    ///\code
633    ///  d.init();
634    ///  d.addSource(s);
635    ///  d.start();
636    ///\endcode
637    void run(Node s) {
638      init();
639      addSource(s);
640      start();
641    }
642   
643    ///Finds the shortest path between \c s and \c t.
644   
645    ///Finds the shortest path between \c s and \c t.
646    ///
647    ///\return The length of the shortest s---t path if there exists one,
648    ///0 otherwise.
649    ///\note Apart from the return value, d.run(s) is
650    ///just a shortcut of the following code.
651    ///\code
652    ///  d.init();
653    ///  d.addSource(s);
654    ///  d.start(t);
655    ///\endcode
656    int run(Node s,Node t) {
657      init();
658      addSource(s);
659      start(t);
660      return reached(t)?_curr_dist-1+(_queue_tail==_queue_next_dist):0;
661    }
662   
663    ///@}
664
665    ///\name Query Functions
666    ///The result of the %BFS algorithm can be obtained using these
667    ///functions.\n
668    ///Before the use of these functions,
669    ///either run() or start() must be called.
670   
671    ///@{
672
673    ///Copies the shortest path to \c t into \c p
674   
675    ///This function copies the shortest path to \c t into \c p.
676    ///If \c t is a source itself or unreachable, then it does not
677    ///alter \c p.
678    ///\todo Is it the right way to handle unreachable nodes?
679    ///\return Returns \c true if a path to \c t was actually copied to \c p,
680    ///\c false otherwise.
681    ///\sa DirPath
682    template<class P>
683    bool getPath(P &p,Node t)
684    {
685      if(reached(t)) {
686        p.clear();
687        typename P::Builder b(p);
688        for(b.setStartNode(t);pred(t)!=INVALID;t=predNode(t))
689          b.pushFront(pred(t));
690        b.commit();
691        return true;
692      }
693      return false;
694    }
695
696    ///The distance of a node from the root(s).
697
698    ///Returns the distance of a node from the root(s).
699    ///\pre \ref run() must be called before using this function.
700    ///\warning If node \c v in unreachable from the root(s) the return value
701    ///of this function is undefined.
702    int dist(Node v) const { return (*_dist)[v]; }
703
704    ///Returns the 'previous edge' of the shortest path tree.
705
706    ///For a node \c v it returns the 'previous edge'
707    ///of the shortest path tree,
708    ///i.e. it returns the last edge of a shortest path from the root(s) to \c
709    ///v. It is \ref INVALID
710    ///if \c v is unreachable from the root(s) or \c v is a root. The
711    ///shortest path tree used here is equal to the shortest path tree used in
712    ///\ref predNode().
713    ///\pre Either \ref run() or \ref start() must be called before using
714    ///this function.
715    ///\todo predEdge could be a better name.
716    Edge pred(Node v) const { return (*_pred)[v];}
717
718    ///Returns the 'previous node' of the shortest path tree.
719
720    ///For a node \c v it returns the 'previous node'
721    ///of the shortest path tree,
722    ///i.e. it returns the last but one node from a shortest path from the
723    ///root(a) to \c /v.
724    ///It is INVALID if \c v is unreachable from the root(s) or
725    ///if \c v itself a root.
726    ///The shortest path tree used here is equal to the shortest path
727    ///tree used in \ref pred().
728    ///\pre Either \ref run() or \ref start() must be called before
729    ///using this function.
730    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
731                                  G->source((*_pred)[v]); }
732   
733    ///Returns a reference to the NodeMap of distances.
734
735    ///Returns a reference to the NodeMap of distances.
736    ///\pre Either \ref run() or \ref init() must
737    ///be called before using this function.
738    const DistMap &distMap() const { return *_dist;}
739 
740    ///Returns a reference to the shortest path tree map.
741
742    ///Returns a reference to the NodeMap of the edges of the
743    ///shortest path tree.
744    ///\pre Either \ref run() or \ref init()
745    ///must be called before using this function.
746    const PredMap &predMap() const { return *_pred;}
747 
748//     ///Returns a reference to the map of nodes of shortest paths.
749
750//     ///Returns a reference to the NodeMap of the last but one nodes of the
751//     ///shortest path tree.
752//     ///\pre \ref run() must be called before using this function.
753//     const PredNodeMap &predNodeMap() const { return *_predNode;}
754
755    ///Checks if a node is reachable from the root.
756
757    ///Returns \c true if \c v is reachable from the root.
758    ///\warning The source nodes are indicated as unreached.
759    ///\pre Either \ref run() or \ref start()
760    ///must be called before using this function.
761    ///
762    bool reached(Node v) { return (*_reached)[v]; }
763   
764    ///@}
765  };
766
767  ///Default traits class of Bfs function.
768
769  ///Default traits class of Bfs function.
770  ///\param GR Graph type.
771  template<class GR>
772  struct BfsWizardDefaultTraits
773  {
774    ///The graph type the algorithm runs on.
775    typedef GR Graph;
776    ///\brief The type of the map that stores the last
777    ///edges of the shortest paths.
778    ///
779    ///The type of the map that stores the last
780    ///edges of the shortest paths.
781    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
782    ///
783    typedef NullMap<typename Graph::Node,typename GR::Edge> PredMap;
784    ///Instantiates a PredMap.
785 
786    ///This function instantiates a \ref PredMap.
787    ///\param g is the graph, to which we would like to define the PredMap.
788    ///\todo The graph alone may be insufficient to initialize
789#ifdef DOXYGEN
790    static PredMap *createPredMap(const GR &g)
791#else
792    static PredMap *createPredMap(const GR &)
793#endif
794    {
795      return new PredMap();
796    }
797//     ///\brief The type of the map that stores the last but one
798//     ///nodes of the shortest paths.
799//     ///
800//     ///The type of the map that stores the last but one
801//     ///nodes of the shortest paths.
802//     ///It must meet the \ref concept::WriteMap "WriteMap" concept.
803//     ///
804//     typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
805//     ///Instantiates a PredNodeMap.
806   
807//     ///This function instantiates a \ref PredNodeMap.
808//     ///\param G is the graph, to which
809//     ///we would like to define the \ref PredNodeMap
810//     static PredNodeMap *createPredNodeMap(const GR &G)
811//     {
812//       return new PredNodeMap();
813//     }
814
815    ///The type of the map that indicates which nodes are processed.
816 
817    ///The type of the map that indicates which nodes are processed.
818    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
819    ///\todo named parameter to set this type, function to read and write.
820    typedef NullMap<typename Graph::Node,bool> ProcessedMap;
821    ///Instantiates a ProcessedMap.
822 
823    ///This function instantiates a \ref ProcessedMap.
824    ///\param g is the graph, to which
825    ///we would like to define the \ref ProcessedMap
826#ifdef DOXYGEN
827    static ProcessedMap *createProcessedMap(const GR &g)
828#else
829    static ProcessedMap *createProcessedMap(const GR &)
830#endif
831    {
832      return new ProcessedMap();
833    }
834    ///The type of the map that indicates which nodes are reached.
835 
836    ///The type of the map that indicates which nodes are reached.
837    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
838    ///\todo named parameter to set this type, function to read and write.
839    typedef typename Graph::template NodeMap<bool> ReachedMap;
840    ///Instantiates a ReachedMap.
841 
842    ///This function instantiates a \ref ReachedMap.
843    ///\param G is the graph, to which
844    ///we would like to define the \ref ReachedMap.
845    static ReachedMap *createReachedMap(const GR &G)
846    {
847      return new ReachedMap(G);
848    }
849    ///The type of the map that stores the dists of the nodes.
850 
851    ///The type of the map that stores the dists of the nodes.
852    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
853    ///
854    typedef NullMap<typename Graph::Node,int> DistMap;
855    ///Instantiates a DistMap.
856 
857    ///This function instantiates a \ref DistMap.
858    ///\param g is the graph, to which we would like to define the \ref DistMap
859#ifdef DOXYGEN
860    static DistMap *createDistMap(const GR &g)
861#else
862    static DistMap *createDistMap(const GR &)
863#endif
864    {
865      return new DistMap();
866    }
867  };
868 
869  /// Default traits used by \ref BfsWizard
870
871  /// To make it easier to use Bfs algorithm
872  ///we have created a wizard class.
873  /// This \ref BfsWizard class needs default traits,
874  ///as well as the \ref Bfs class.
875  /// The \ref BfsWizardBase is a class to be the default traits of the
876  /// \ref BfsWizard class.
877  template<class GR>
878  class BfsWizardBase : public BfsWizardDefaultTraits<GR>
879  {
880
881    typedef BfsWizardDefaultTraits<GR> Base;
882  protected:
883    /// Type of the nodes in the graph.
884    typedef typename Base::Graph::Node Node;
885
886    /// Pointer to the underlying graph.
887    void *_g;
888    ///Pointer to the map of reached nodes.
889    void *_reached;
890    ///Pointer to the map of processed nodes.
891    void *_processed;
892    ///Pointer to the map of predecessors edges.
893    void *_pred;
894//     ///Pointer to the map of predecessors nodes.
895//     void *_predNode;
896    ///Pointer to the map of distances.
897    void *_dist;
898    ///Pointer to the source node.
899    Node _source;
900   
901    public:
902    /// Constructor.
903   
904    /// This constructor does not require parameters, therefore it initiates
905    /// all of the attributes to default values (0, INVALID).
906    BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
907//                         _predNode(0),
908                           _dist(0), _source(INVALID) {}
909
910    /// Constructor.
911   
912    /// This constructor requires some parameters,
913    /// listed in the parameters list.
914    /// Others are initiated to 0.
915    /// \param g is the initial value of  \ref _g
916    /// \param s is the initial value of  \ref _source
917    BfsWizardBase(const GR &g, Node s=INVALID) :
918      _g((void *)&g), _reached(0), _processed(0), _pred(0),
919//       _predNode(0),
920      _dist(0), _source(s) {}
921
922  };
923 
924  /// A class to make the usage of Bfs algorithm easier
925
926  /// This class is created to make it easier to use Bfs algorithm.
927  /// It uses the functions and features of the plain \ref Bfs,
928  /// but it is much simpler to use it.
929  ///
930  /// Simplicity means that the way to change the types defined
931  /// in the traits class is based on functions that returns the new class
932  /// and not on templatable built-in classes.
933  /// When using the plain \ref Bfs
934  /// the new class with the modified type comes from
935  /// the original class by using the ::
936  /// operator. In the case of \ref BfsWizard only
937  /// a function have to be called and it will
938  /// return the needed class.
939  ///
940  /// It does not have own \ref run method. When its \ref run method is called
941  /// it initiates a plain \ref Bfs class, and calls the \ref Bfs::run
942  /// method of it.
943  template<class TR>
944  class BfsWizard : public TR
945  {
946    typedef TR Base;
947
948    ///The type of the underlying graph.
949    typedef typename TR::Graph Graph;
950    //\e
951    typedef typename Graph::Node Node;
952    //\e
953    typedef typename Graph::NodeIt NodeIt;
954    //\e
955    typedef typename Graph::Edge Edge;
956    //\e
957    typedef typename Graph::OutEdgeIt OutEdgeIt;
958   
959    ///\brief The type of the map that stores
960    ///the reached nodes
961    typedef typename TR::ReachedMap ReachedMap;
962    ///\brief The type of the map that stores
963    ///the processed nodes
964    typedef typename TR::ProcessedMap ProcessedMap;
965    ///\brief The type of the map that stores the last
966    ///edges of the shortest paths.
967    typedef typename TR::PredMap PredMap;
968//     ///\brief The type of the map that stores the last but one
969//     ///nodes of the shortest paths.
970//     typedef typename TR::PredNodeMap PredNodeMap;
971    ///The type of the map that stores the dists of the nodes.
972    typedef typename TR::DistMap DistMap;
973
974public:
975    /// Constructor.
976    BfsWizard() : TR() {}
977
978    /// Constructor that requires parameters.
979
980    /// Constructor that requires parameters.
981    /// These parameters will be the default values for the traits class.
982    BfsWizard(const Graph &g, Node s=INVALID) :
983      TR(g,s) {}
984
985    ///Copy constructor
986    BfsWizard(const TR &b) : TR(b) {}
987
988    ~BfsWizard() {}
989
990    ///Runs Bfs algorithm from a given node.
991   
992    ///Runs Bfs algorithm from a given node.
993    ///The node can be given by the \ref source function.
994    void run()
995    {
996      if(Base::_source==INVALID) throw UninitializedParameter();
997      Bfs<Graph,TR> alg(*(Graph*)Base::_g);
998      if(Base::_reached)
999        alg.reachedMap(*(ReachedMap*)Base::_reached);
1000      if(Base::_processed) alg.processedMap(*(ProcessedMap*)Base::_processed);
1001      if(Base::_pred) alg.predMap(*(PredMap*)Base::_pred);
1002//       if(Base::_predNode) alg.predNodeMap(*(PredNodeMap*)Base::_predNode);
1003      if(Base::_dist) alg.distMap(*(DistMap*)Base::_dist);
1004      alg.run(Base::_source);
1005    }
1006
1007    ///Runs Bfs algorithm from the given node.
1008
1009    ///Runs Bfs algorithm from the given node.
1010    ///\param s is the given source.
1011    void run(Node s)
1012    {
1013      Base::_source=s;
1014      run();
1015    }
1016
1017    template<class T>
1018    struct DefPredMapBase : public Base {
1019      typedef T PredMap;
1020      static PredMap *createPredMap(const Graph &) { return 0; };
1021      DefPredMapBase(const TR &b) : TR(b) {}
1022    };
1023   
1024    ///\brief \ref named-templ-param "Named parameter"
1025    ///function for setting PredMap
1026    ///
1027    /// \ref named-templ-param "Named parameter"
1028    ///function for setting PredMap
1029    ///
1030    template<class T>
1031    BfsWizard<DefPredMapBase<T> > predMap(const T &t)
1032    {
1033      Base::_pred=(void *)&t;
1034      return BfsWizard<DefPredMapBase<T> >(*this);
1035    }
1036   
1037 
1038    template<class T>
1039    struct DefReachedMapBase : public Base {
1040      typedef T ReachedMap;
1041      static ReachedMap *createReachedMap(const Graph &) { return 0; };
1042      DefReachedMapBase(const TR &b) : TR(b) {}
1043    };
1044   
1045    ///\brief \ref named-templ-param "Named parameter"
1046    ///function for setting ReachedMap
1047    ///
1048    /// \ref named-templ-param "Named parameter"
1049    ///function for setting ReachedMap
1050    ///
1051    template<class T>
1052    BfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
1053    {
1054      Base::_pred=(void *)&t;
1055      return BfsWizard<DefReachedMapBase<T> >(*this);
1056    }
1057   
1058
1059    template<class T>
1060    struct DefProcessedMapBase : public Base {
1061      typedef T ProcessedMap;
1062      static ProcessedMap *createProcessedMap(const Graph &) { return 0; };
1063      DefProcessedMapBase(const TR &b) : TR(b) {}
1064    };
1065   
1066    ///\brief \ref named-templ-param "Named parameter"
1067    ///function for setting ProcessedMap
1068    ///
1069    /// \ref named-templ-param "Named parameter"
1070    ///function for setting ProcessedMap
1071    ///
1072    template<class T>
1073    BfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
1074    {
1075      Base::_pred=(void *)&t;
1076      return BfsWizard<DefProcessedMapBase<T> >(*this);
1077    }
1078   
1079
1080//     template<class T>
1081//     struct DefPredNodeMapBase : public Base {
1082//       typedef T PredNodeMap;
1083//       static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
1084//       DefPredNodeMapBase(const TR &b) : TR(b) {}
1085//     };
1086   
1087//     ///\brief \ref named-templ-param "Named parameter"
1088//     ///function for setting PredNodeMap type
1089//     ///
1090//     /// \ref named-templ-param "Named parameter"
1091//     ///function for setting PredNodeMap type
1092//     ///
1093//     template<class T>
1094//     BfsWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t)
1095//     {
1096//       Base::_predNode=(void *)&t;
1097//       return BfsWizard<DefPredNodeMapBase<T> >(*this);
1098//     }
1099   
1100    template<class T>
1101    struct DefDistMapBase : public Base {
1102      typedef T DistMap;
1103      static DistMap *createDistMap(const Graph &) { return 0; };
1104      DefDistMapBase(const TR &b) : TR(b) {}
1105    };
1106   
1107    ///\brief \ref named-templ-param "Named parameter"
1108    ///function for setting DistMap type
1109    ///
1110    /// \ref named-templ-param "Named parameter"
1111    ///function for setting DistMap type
1112    ///
1113    template<class T>
1114    BfsWizard<DefDistMapBase<T> > distMap(const T &t)
1115    {
1116      Base::_dist=(void *)&t;
1117      return BfsWizard<DefDistMapBase<T> >(*this);
1118    }
1119   
1120    /// Sets the source node, from which the Bfs algorithm runs.
1121
1122    /// Sets the source node, from which the Bfs algorithm runs.
1123    /// \param s is the source node.
1124    BfsWizard<TR> &source(Node s)
1125    {
1126      Base::_source=s;
1127      return *this;
1128    }
1129   
1130  };
1131 
1132  ///Function type interface for Bfs algorithm.
1133
1134  /// \ingroup flowalgs
1135  ///Function type interface for Bfs algorithm.
1136  ///
1137  ///This function also has several
1138  ///\ref named-templ-func-param "named parameters",
1139  ///they are declared as the members of class \ref BfsWizard.
1140  ///The following
1141  ///example shows how to use these parameters.
1142  ///\code
1143  ///  bfs(g,source).predMap(preds).run();
1144  ///\endcode
1145  ///\warning Don't forget to put the \ref BfsWizard::run() "run()"
1146  ///to the end of the parameter list.
1147  ///\sa BfsWizard
1148  ///\sa Bfs
1149  template<class GR>
1150  BfsWizard<BfsWizardBase<GR> >
1151  bfs(const GR &g,typename GR::Node s=INVALID)
1152  {
1153    return BfsWizard<BfsWizardBase<GR> >(g,s);
1154  }
1155
1156} //END OF NAMESPACE LEMON
1157
1158#endif
1159
Note: See TracBrowser for help on using the repository browser.