COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bfs.h @ 1623:c3defc3590aa

Last change on this file since 1623:c3defc3590aa was 1536:308150155bb5, checked in by Alpar Juttner, 14 years ago

Kill several doxygen warnings

File size: 35.1 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,
269                                        DefPredMapTraits<T> > { };
270   
271//     template <class T>
272//     struct DefPredNodeMapTraits : public Traits {
273//       typedef T PredNodeMap;
274//       static PredNodeMap *createPredNodeMap(const Graph &G)
275//       {
276//      throw UninitializedParameter();
277//       }
278//     };
279//     ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
280
281//     ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
282//     ///
283//     template <class T>
284//     class DefPredNodeMap : public Bfs< Graph,
285//                                          LengthMap,
286//                                          DefPredNodeMapTraits<T> > { };
287   
288    template <class T>
289    struct DefDistMapTraits : public Traits {
290      typedef T DistMap;
291      static DistMap *createDistMap(const Graph &G)
292      {
293        throw UninitializedParameter();
294      }
295    };
296    ///\ref named-templ-param "Named parameter" for setting DistMap type
297
298    ///\ref named-templ-param "Named parameter" for setting DistMap type
299    ///
300    template <class T>
301    class DefDistMap : public Bfs< Graph,
302                                   DefDistMapTraits<T> > { };
303   
304    template <class T>
305    struct DefReachedMapTraits : public Traits {
306      typedef T ReachedMap;
307      static ReachedMap *createReachedMap(const Graph &G)
308      {
309        throw UninitializedParameter();
310      }
311    };
312    ///\ref named-templ-param "Named parameter" for setting ReachedMap type
313
314    ///\ref named-templ-param "Named parameter" for setting ReachedMap type
315    ///
316    template <class T>
317    class DefReachedMap : public Bfs< Graph,
318                                      DefReachedMapTraits<T> > { };
319   
320    struct DefGraphReachedMapTraits : public Traits {
321      typedef typename Graph::template NodeMap<bool> ReachedMap;
322      static ReachedMap *createReachedMap(const Graph &G)
323      {
324        return new ReachedMap(G);
325      }
326    };
327    template <class T>
328    struct DefProcessedMapTraits : public Traits {
329      typedef T ProcessedMap;
330      static ProcessedMap *createProcessedMap(const Graph &G)
331      {
332        throw UninitializedParameter();
333      }
334    };
335    ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
336
337    ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
338    ///
339    template <class T>
340    class DefProcessedMap : public Bfs< Graph,
341                                        DefProcessedMapTraits<T> > { };
342   
343    struct DefGraphProcessedMapTraits : public Traits {
344      typedef typename Graph::template NodeMap<bool> ProcessedMap;
345      static ProcessedMap *createProcessedMap(const Graph &G)
346      {
347        return new ProcessedMap(G);
348      }
349    };
350    ///\brief \ref named-templ-param "Named parameter"
351    ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
352    ///
353    ///\ref named-templ-param "Named parameter"
354    ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
355    ///If you don't set it explicitly, it will be automatically allocated.
356    template <class T>
357    class DefProcessedMapToBeDefaultMap :
358      public Bfs< Graph,
359                  DefGraphProcessedMapTraits> { };
360   
361    ///@}
362
363  public:     
364   
365    ///Constructor.
366   
367    ///\param _G the graph the algorithm will run on.
368    ///
369    Bfs(const Graph& _G) :
370      G(&_G),
371      _pred(NULL), local_pred(false),
372//       _predNode(NULL), local_predNode(false),
373      _dist(NULL), local_dist(false),
374      _reached(NULL), local_reached(false),
375      _processed(NULL), local_processed(false)
376    { }
377   
378    ///Destructor.
379    ~Bfs()
380    {
381      if(local_pred) delete _pred;
382//       if(local_predNode) delete _predNode;
383      if(local_dist) delete _dist;
384      if(local_reached) delete _reached;
385      if(local_processed) delete _processed;
386    }
387
388    ///Sets the map storing the predecessor edges.
389
390    ///Sets the map storing the predecessor edges.
391    ///If you don't use this function before calling \ref run(),
392    ///it will allocate one. The destructor deallocates this
393    ///automatically allocated map, of course.
394    ///\return <tt> (*this) </tt>
395    Bfs &predMap(PredMap &m)
396    {
397      if(local_pred) {
398        delete _pred;
399        local_pred=false;
400      }
401      _pred = &m;
402      return *this;
403    }
404
405    ///Sets the map indicating the reached nodes.
406
407    ///Sets the map indicating the reached nodes.
408    ///If you don't use this function before calling \ref run(),
409    ///it will allocate one. The destructor deallocates this
410    ///automatically allocated map, of course.
411    ///\return <tt> (*this) </tt>
412    Bfs &reachedMap(ReachedMap &m)
413    {
414      if(local_reached) {
415        delete _reached;
416        local_reached=false;
417      }
418      _reached = &m;
419      return *this;
420    }
421
422    ///Sets the map indicating the processed nodes.
423
424    ///Sets the map indicating the processed nodes.
425    ///If you don't use this function before calling \ref run(),
426    ///it will allocate one. The destructor deallocates this
427    ///automatically allocated map, of course.
428    ///\return <tt> (*this) </tt>
429    Bfs &processedMap(ProcessedMap &m)
430    {
431      if(local_processed) {
432        delete _processed;
433        local_processed=false;
434      }
435      _processed = &m;
436      return *this;
437    }
438
439//     ///Sets the map storing the predecessor nodes.
440
441//     ///Sets the map storing the predecessor nodes.
442//     ///If you don't use this function before calling \ref run(),
443//     ///it will allocate one. The destructor deallocates this
444//     ///automatically allocated map, of course.
445//     ///\return <tt> (*this) </tt>
446//     Bfs &predNodeMap(PredNodeMap &m)
447//     {
448//       if(local_predNode) {
449//      delete _predNode;
450//      local_predNode=false;
451//       }
452//       _predNode = &m;
453//       return *this;
454//     }
455
456    ///Sets the map storing the distances calculated by the algorithm.
457
458    ///Sets the map storing the distances calculated by the algorithm.
459    ///If you don't use this function before calling \ref run(),
460    ///it will allocate one. The destructor deallocates this
461    ///automatically allocated map, of course.
462    ///\return <tt> (*this) </tt>
463    Bfs &distMap(DistMap &m)
464    {
465      if(local_dist) {
466        delete _dist;
467        local_dist=false;
468      }
469      _dist = &m;
470      return *this;
471    }
472
473  public:
474    ///\name Execution control
475    ///The simplest way to execute the algorithm is to use
476    ///one of the member functions called \c run(...).
477    ///\n
478    ///If you need more control on the execution,
479    ///first you must call \ref init(), then you can add several source nodes
480    ///with \ref addSource().
481    ///Finally \ref start() will perform the actual path
482    ///computation.
483
484    ///@{
485
486    ///Initializes the internal data structures.
487
488    ///Initializes the internal data structures.
489    ///
490    void init()
491    {
492      create_maps();
493      _queue.resize(countNodes(*G));
494      _queue_head=_queue_tail=0;
495      _curr_dist=1;
496      for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
497        _pred->set(u,INVALID);
498//      _predNode->set(u,INVALID);
499        _reached->set(u,false);
500        _processed->set(u,false);
501      }
502    }
503   
504    ///Adds a new source node.
505
506    ///Adds a new source node to the set of nodes to be processed.
507    ///
508    void addSource(Node s)
509    {
510      if(!(*_reached)[s])
511        {
512          _reached->set(s,true);
513          _pred->set(s,INVALID);
514          _dist->set(s,0);
515          _queue[_queue_head++]=s;
516          _queue_next_dist=_queue_head;
517        }
518    }
519   
520    ///Processes the next node.
521
522    ///Processes the next node.
523    ///
524    ///\return The processed node.
525    ///
526    ///\warning The queue must not be empty!
527    Node processNextNode()
528    {
529      if(_queue_tail==_queue_next_dist) {
530        _curr_dist++;
531        _queue_next_dist=_queue_head;
532      }
533      Node n=_queue[_queue_tail++];
534      _processed->set(n,true);
535      Node m;
536      for(OutEdgeIt e(*G,n);e!=INVALID;++e)
537        if(!(*_reached)[m=G->target(e)]) {
538          _queue[_queue_head++]=m;
539          _reached->set(m,true);
540          _pred->set(m,e);
541//        _pred_node->set(m,n);
542          _dist->set(m,_curr_dist);
543        }
544      return n;
545    }
546     
547    ///\brief Returns \c false if there are nodes
548    ///to be processed in the queue
549    ///
550    ///Returns \c false if there are nodes
551    ///to be processed in the queue
552    bool emptyQueue() { return _queue_tail==_queue_head; }
553    ///Returns the number of the nodes to be processed.
554   
555    ///Returns the number of the nodes to be processed in the queue.
556    ///
557    int queueSize() { return _queue_head-_queue_tail; }
558   
559    ///Executes the algorithm.
560
561    ///Executes the algorithm.
562    ///
563    ///\pre init() must be called and at least one node should be added
564    ///with addSource() before using this function.
565    ///
566    ///This method runs the %BFS algorithm from the root node(s)
567    ///in order to
568    ///compute the
569    ///shortest path to each node. The algorithm computes
570    ///- The shortest path tree.
571    ///- The distance of each node from the root(s).
572    ///
573    void start()
574    {
575      while ( !emptyQueue() ) processNextNode();
576    }
577   
578    ///Executes the algorithm until \c dest is reached.
579
580    ///Executes the algorithm until \c dest is reached.
581    ///
582    ///\pre init() must be called and at least one node should be added
583    ///with addSource() before using this function.
584    ///
585    ///This method runs the %BFS algorithm from the root node(s)
586    ///in order to
587    ///compute the
588    ///shortest path to \c dest. The algorithm computes
589    ///- The shortest path to \c  dest.
590    ///- The distance of \c dest from the root(s).
591    ///
592    void start(Node dest)
593    {
594      while ( !emptyQueue() && _queue[_queue_tail]!=dest ) processNextNode();
595    }
596   
597    ///Executes the algorithm until a condition is met.
598
599    ///Executes the algorithm until a condition is met.
600    ///
601    ///\pre init() must be called and at least one node should be added
602    ///with addSource() before using this function.
603    ///
604    ///\param nm must be a bool (or convertible) node map. The algorithm
605    ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
606    template<class NM>
607      void start(const NM &nm)
608      {
609        while ( !emptyQueue() && !nm[_queue[_queue_tail]] ) processNextNode();
610      }
611   
612    ///Runs %BFS algorithm from node \c s.
613   
614    ///This method runs the %BFS algorithm from a root node \c s
615    ///in order to
616    ///compute the
617    ///shortest path to each node. The algorithm computes
618    ///- The shortest path tree.
619    ///- The distance of each node from the root.
620    ///
621    ///\note d.run(s) is just a shortcut of the following code.
622    ///\code
623    ///  d.init();
624    ///  d.addSource(s);
625    ///  d.start();
626    ///\endcode
627    void run(Node s) {
628      init();
629      addSource(s);
630      start();
631    }
632   
633    ///Finds the shortest path between \c s and \c t.
634   
635    ///Finds the shortest path between \c s and \c t.
636    ///
637    ///\return The length of the shortest s---t path if there exists one,
638    ///0 otherwise.
639    ///\note Apart from the return value, d.run(s) is
640    ///just a shortcut of the following code.
641    ///\code
642    ///  d.init();
643    ///  d.addSource(s);
644    ///  d.start(t);
645    ///\endcode
646    int run(Node s,Node t) {
647      init();
648      addSource(s);
649      start(t);
650      return reached(t)?_curr_dist-1+(_queue_tail==_queue_next_dist):0;
651    }
652   
653    ///@}
654
655    ///\name Query Functions
656    ///The result of the %BFS algorithm can be obtained using these
657    ///functions.\n
658    ///Before the use of these functions,
659    ///either run() or start() must be called.
660   
661    ///@{
662
663    ///Copies the shortest path to \c t into \c p
664   
665    ///This function copies the shortest path to \c t into \c p.
666    ///If \c t is a source itself or unreachable, then it does not
667    ///alter \c p.
668    ///\todo Is it the right way to handle unreachable nodes?
669    ///\return Returns \c true if a path to \c t was actually copied to \c p,
670    ///\c false otherwise.
671    ///\sa DirPath
672    template<class P>
673    bool getPath(P &p,Node t)
674    {
675      if(reached(t)) {
676        p.clear();
677        typename P::Builder b(p);
678        for(b.setStartNode(t);pred(t)!=INVALID;t=predNode(t))
679          b.pushFront(pred(t));
680        b.commit();
681        return true;
682      }
683      return false;
684    }
685
686    ///The distance of a node from the root(s).
687
688    ///Returns the distance of a node from the root(s).
689    ///\pre \ref run() must be called before using this function.
690    ///\warning If node \c v in unreachable from the root(s) the return value
691    ///of this function is undefined.
692    int dist(Node v) const { return (*_dist)[v]; }
693
694    ///Returns the 'previous edge' of the shortest path tree.
695
696    ///For a node \c v it returns the 'previous edge'
697    ///of the shortest path tree,
698    ///i.e. it returns the last edge of a shortest path from the root(s) to \c
699    ///v. It is \ref INVALID
700    ///if \c v is unreachable from the root(s) or \c v is a root. The
701    ///shortest path tree used here is equal to the shortest path tree used in
702    ///\ref predNode(Node v).
703    ///\pre Either \ref run() or \ref start() must be called before using
704    ///this function.
705    ///\todo predEdge could be a better name.
706    Edge pred(Node v) const { return (*_pred)[v];}
707
708    ///Returns the 'previous node' of the shortest path tree.
709
710    ///For a node \c v it returns the 'previous node'
711    ///of the shortest path tree,
712    ///i.e. it returns the last but one node from a shortest path from the
713    ///root(a) to \c /v.
714    ///It is INVALID if \c v is unreachable from the root(s) or
715    ///if \c v itself a root.
716    ///The shortest path tree used here is equal to the shortest path
717    ///tree used in \ref pred(Node v).
718    ///\pre Either \ref run() or \ref start() must be called before
719    ///using this function.
720    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
721                                  G->source((*_pred)[v]); }
722   
723    ///Returns a reference to the NodeMap of distances.
724
725    ///Returns a reference to the NodeMap of distances.
726    ///\pre Either \ref run() or \ref init() must
727    ///be called before using this function.
728    const DistMap &distMap() const { return *_dist;}
729 
730    ///Returns a reference to the shortest path tree map.
731
732    ///Returns a reference to the NodeMap of the edges of the
733    ///shortest path tree.
734    ///\pre Either \ref run() or \ref init()
735    ///must be called before using this function.
736    const PredMap &predMap() const { return *_pred;}
737 
738//     ///Returns a reference to the map of nodes of shortest paths.
739
740//     ///Returns a reference to the NodeMap of the last but one nodes of the
741//     ///shortest path tree.
742//     ///\pre \ref run() must be called before using this function.
743//     const PredNodeMap &predNodeMap() const { return *_predNode;}
744
745    ///Checks if a node is reachable from the root.
746
747    ///Returns \c true if \c v is reachable from the root.
748    ///\warning The source nodes are indicated as unreached.
749    ///\pre Either \ref run() or \ref start()
750    ///must be called before using this function.
751    ///
752    bool reached(Node v) { return (*_reached)[v]; }
753   
754    ///@}
755  };
756
757  ///Default traits class of Bfs function.
758
759  ///Default traits class of Bfs function.
760  ///\param GR Graph type.
761  template<class GR>
762  struct BfsWizardDefaultTraits
763  {
764    ///The graph type the algorithm runs on.
765    typedef GR Graph;
766    ///\brief The type of the map that stores the last
767    ///edges of the shortest paths.
768    ///
769    ///The type of the map that stores the last
770    ///edges of the shortest paths.
771    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
772    ///
773    typedef NullMap<typename Graph::Node,typename GR::Edge> PredMap;
774    ///Instantiates a PredMap.
775 
776    ///This function instantiates a \ref PredMap.
777    ///\param g is the graph, to which we would like to define the PredMap.
778    ///\todo The graph alone may be insufficient to initialize
779#ifdef DOXYGEN
780    static PredMap *createPredMap(const GR &g)
781#else
782    static PredMap *createPredMap(const GR &)
783#endif
784    {
785      return new PredMap();
786    }
787//     ///\brief The type of the map that stores the last but one
788//     ///nodes of the shortest paths.
789//     ///
790//     ///The type of the map that stores the last but one
791//     ///nodes of the shortest paths.
792//     ///It must meet the \ref concept::WriteMap "WriteMap" concept.
793//     ///
794//     typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
795//     ///Instantiates a PredNodeMap.
796   
797//     ///This function instantiates a \ref PredNodeMap.
798//     ///\param G is the graph, to which
799//     ///we would like to define the \ref PredNodeMap
800//     static PredNodeMap *createPredNodeMap(const GR &G)
801//     {
802//       return new PredNodeMap();
803//     }
804
805    ///The type of the map that indicates which nodes are processed.
806 
807    ///The type of the map that indicates which nodes are processed.
808    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
809    ///\todo named parameter to set this type, function to read and write.
810    typedef NullMap<typename Graph::Node,bool> ProcessedMap;
811    ///Instantiates a ProcessedMap.
812 
813    ///This function instantiates a \ref ProcessedMap.
814    ///\param g is the graph, to which
815    ///we would like to define the \ref ProcessedMap
816#ifdef DOXYGEN
817    static ProcessedMap *createProcessedMap(const GR &g)
818#else
819    static ProcessedMap *createProcessedMap(const GR &)
820#endif
821    {
822      return new ProcessedMap();
823    }
824    ///The type of the map that indicates which nodes are reached.
825 
826    ///The type of the map that indicates which nodes are reached.
827    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
828    ///\todo named parameter to set this type, function to read and write.
829    typedef typename Graph::template NodeMap<bool> ReachedMap;
830    ///Instantiates a ReachedMap.
831 
832    ///This function instantiates a \ref ReachedMap.
833    ///\param G is the graph, to which
834    ///we would like to define the \ref ReachedMap.
835    static ReachedMap *createReachedMap(const GR &G)
836    {
837      return new ReachedMap(G);
838    }
839    ///The type of the map that stores the dists of the nodes.
840 
841    ///The type of the map that stores the dists of the nodes.
842    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
843    ///
844    typedef NullMap<typename Graph::Node,int> DistMap;
845    ///Instantiates a DistMap.
846 
847    ///This function instantiates a \ref DistMap.
848    ///\param g is the graph, to which we would like to define the \ref DistMap
849#ifdef DOXYGEN
850    static DistMap *createDistMap(const GR &g)
851#else
852    static DistMap *createDistMap(const GR &)
853#endif
854    {
855      return new DistMap();
856    }
857  };
858 
859  /// Default traits used by \ref BfsWizard
860
861  /// To make it easier to use Bfs algorithm
862  ///we have created a wizard class.
863  /// This \ref BfsWizard class needs default traits,
864  ///as well as the \ref Bfs class.
865  /// The \ref BfsWizardBase is a class to be the default traits of the
866  /// \ref BfsWizard class.
867  template<class GR>
868  class BfsWizardBase : public BfsWizardDefaultTraits<GR>
869  {
870
871    typedef BfsWizardDefaultTraits<GR> Base;
872  protected:
873    /// Type of the nodes in the graph.
874    typedef typename Base::Graph::Node Node;
875
876    /// Pointer to the underlying graph.
877    void *_g;
878    ///Pointer to the map of reached nodes.
879    void *_reached;
880    ///Pointer to the map of processed nodes.
881    void *_processed;
882    ///Pointer to the map of predecessors edges.
883    void *_pred;
884//     ///Pointer to the map of predecessors nodes.
885//     void *_predNode;
886    ///Pointer to the map of distances.
887    void *_dist;
888    ///Pointer to the source node.
889    Node _source;
890   
891    public:
892    /// Constructor.
893   
894    /// This constructor does not require parameters, therefore it initiates
895    /// all of the attributes to default values (0, INVALID).
896    BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
897//                         _predNode(0),
898                           _dist(0), _source(INVALID) {}
899
900    /// Constructor.
901   
902    /// This constructor requires some parameters,
903    /// listed in the parameters list.
904    /// Others are initiated to 0.
905    /// \param g is the initial value of  \ref _g
906    /// \param s is the initial value of  \ref _source
907    BfsWizardBase(const GR &g, Node s=INVALID) :
908      _g((void *)&g), _reached(0), _processed(0), _pred(0),
909//       _predNode(0),
910      _dist(0), _source(s) {}
911
912  };
913 
914  /// A class to make the usage of Bfs algorithm easier
915
916  /// This class is created to make it easier to use Bfs algorithm.
917  /// It uses the functions and features of the plain \ref Bfs,
918  /// but it is much simpler to use it.
919  ///
920  /// Simplicity means that the way to change the types defined
921  /// in the traits class is based on functions that returns the new class
922  /// and not on templatable built-in classes.
923  /// When using the plain \ref Bfs
924  /// the new class with the modified type comes from
925  /// the original class by using the ::
926  /// operator. In the case of \ref BfsWizard only
927  /// a function have to be called and it will
928  /// return the needed class.
929  ///
930  /// It does not have own \ref run method. When its \ref run method is called
931  /// it initiates a plain \ref Bfs class, and calls the \ref Bfs::run
932  /// method of it.
933  template<class TR>
934  class BfsWizard : public TR
935  {
936    typedef TR Base;
937
938    ///The type of the underlying graph.
939    typedef typename TR::Graph Graph;
940    //\e
941    typedef typename Graph::Node Node;
942    //\e
943    typedef typename Graph::NodeIt NodeIt;
944    //\e
945    typedef typename Graph::Edge Edge;
946    //\e
947    typedef typename Graph::OutEdgeIt OutEdgeIt;
948   
949    ///\brief The type of the map that stores
950    ///the reached nodes
951    typedef typename TR::ReachedMap ReachedMap;
952    ///\brief The type of the map that stores
953    ///the processed nodes
954    typedef typename TR::ProcessedMap ProcessedMap;
955    ///\brief The type of the map that stores the last
956    ///edges of the shortest paths.
957    typedef typename TR::PredMap PredMap;
958//     ///\brief The type of the map that stores the last but one
959//     ///nodes of the shortest paths.
960//     typedef typename TR::PredNodeMap PredNodeMap;
961    ///The type of the map that stores the dists of the nodes.
962    typedef typename TR::DistMap DistMap;
963
964public:
965    /// Constructor.
966    BfsWizard() : TR() {}
967
968    /// Constructor that requires parameters.
969
970    /// Constructor that requires parameters.
971    /// These parameters will be the default values for the traits class.
972    BfsWizard(const Graph &g, Node s=INVALID) :
973      TR(g,s) {}
974
975    ///Copy constructor
976    BfsWizard(const TR &b) : TR(b) {}
977
978    ~BfsWizard() {}
979
980    ///Runs Bfs algorithm from a given node.
981   
982    ///Runs Bfs algorithm from a given node.
983    ///The node can be given by the \ref source function.
984    void run()
985    {
986      if(Base::_source==INVALID) throw UninitializedParameter();
987      Bfs<Graph,TR> alg(*(Graph*)Base::_g);
988      if(Base::_reached)
989        alg.reachedMap(*(ReachedMap*)Base::_reached);
990      if(Base::_processed) alg.processedMap(*(ProcessedMap*)Base::_processed);
991      if(Base::_pred) alg.predMap(*(PredMap*)Base::_pred);
992//       if(Base::_predNode) alg.predNodeMap(*(PredNodeMap*)Base::_predNode);
993      if(Base::_dist) alg.distMap(*(DistMap*)Base::_dist);
994      alg.run(Base::_source);
995    }
996
997    ///Runs Bfs algorithm from the given node.
998
999    ///Runs Bfs algorithm from the given node.
1000    ///\param s is the given source.
1001    void run(Node s)
1002    {
1003      Base::_source=s;
1004      run();
1005    }
1006
1007    template<class T>
1008    struct DefPredMapBase : public Base {
1009      typedef T PredMap;
1010      static PredMap *createPredMap(const Graph &) { return 0; };
1011      DefPredMapBase(const TR &b) : TR(b) {}
1012    };
1013   
1014    ///\brief \ref named-templ-param "Named parameter"
1015    ///function for setting PredMap
1016    ///
1017    /// \ref named-templ-param "Named parameter"
1018    ///function for setting PredMap
1019    ///
1020    template<class T>
1021    BfsWizard<DefPredMapBase<T> > predMap(const T &t)
1022    {
1023      Base::_pred=(void *)&t;
1024      return BfsWizard<DefPredMapBase<T> >(*this);
1025    }
1026   
1027 
1028    template<class T>
1029    struct DefReachedMapBase : public Base {
1030      typedef T ReachedMap;
1031      static ReachedMap *createReachedMap(const Graph &) { return 0; };
1032      DefReachedMapBase(const TR &b) : TR(b) {}
1033    };
1034   
1035    ///\brief \ref named-templ-param "Named parameter"
1036    ///function for setting ReachedMap
1037    ///
1038    /// \ref named-templ-param "Named parameter"
1039    ///function for setting ReachedMap
1040    ///
1041    template<class T>
1042    BfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
1043    {
1044      Base::_pred=(void *)&t;
1045      return BfsWizard<DefReachedMapBase<T> >(*this);
1046    }
1047   
1048
1049    template<class T>
1050    struct DefProcessedMapBase : public Base {
1051      typedef T ProcessedMap;
1052      static ProcessedMap *createProcessedMap(const Graph &) { return 0; };
1053      DefProcessedMapBase(const TR &b) : TR(b) {}
1054    };
1055   
1056    ///\brief \ref named-templ-param "Named parameter"
1057    ///function for setting ProcessedMap
1058    ///
1059    /// \ref named-templ-param "Named parameter"
1060    ///function for setting ProcessedMap
1061    ///
1062    template<class T>
1063    BfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
1064    {
1065      Base::_pred=(void *)&t;
1066      return BfsWizard<DefProcessedMapBase<T> >(*this);
1067    }
1068   
1069
1070//     template<class T>
1071//     struct DefPredNodeMapBase : public Base {
1072//       typedef T PredNodeMap;
1073//       static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
1074//       DefPredNodeMapBase(const TR &b) : TR(b) {}
1075//     };
1076   
1077//     ///\brief \ref named-templ-param "Named parameter"
1078//     ///function for setting PredNodeMap type
1079//     ///
1080//     /// \ref named-templ-param "Named parameter"
1081//     ///function for setting PredNodeMap type
1082//     ///
1083//     template<class T>
1084//     BfsWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t)
1085//     {
1086//       Base::_predNode=(void *)&t;
1087//       return BfsWizard<DefPredNodeMapBase<T> >(*this);
1088//     }
1089   
1090    template<class T>
1091    struct DefDistMapBase : public Base {
1092      typedef T DistMap;
1093      static DistMap *createDistMap(const Graph &) { return 0; };
1094      DefDistMapBase(const TR &b) : TR(b) {}
1095    };
1096   
1097    ///\brief \ref named-templ-param "Named parameter"
1098    ///function for setting DistMap type
1099    ///
1100    /// \ref named-templ-param "Named parameter"
1101    ///function for setting DistMap type
1102    ///
1103    template<class T>
1104    BfsWizard<DefDistMapBase<T> > distMap(const T &t)
1105    {
1106      Base::_dist=(void *)&t;
1107      return BfsWizard<DefDistMapBase<T> >(*this);
1108    }
1109   
1110    /// Sets the source node, from which the Bfs algorithm runs.
1111
1112    /// Sets the source node, from which the Bfs algorithm runs.
1113    /// \param s is the source node.
1114    BfsWizard<TR> &source(Node s)
1115    {
1116      Base::_source=s;
1117      return *this;
1118    }
1119   
1120  };
1121 
1122  ///Function type interface for Bfs algorithm.
1123
1124  /// \ingroup flowalgs
1125  ///Function type interface for Bfs algorithm.
1126  ///
1127  ///This function also has several
1128  ///\ref named-templ-func-param "named parameters",
1129  ///they are declared as the members of class \ref BfsWizard.
1130  ///The following
1131  ///example shows how to use these parameters.
1132  ///\code
1133  ///  bfs(g,source).predMap(preds).run();
1134  ///\endcode
1135  ///\warning Don't forget to put the \ref BfsWizard::run() "run()"
1136  ///to the end of the parameter list.
1137  ///\sa BfsWizard
1138  ///\sa Bfs
1139  template<class GR>
1140  BfsWizard<BfsWizardBase<GR> >
1141  bfs(const GR &g,typename GR::Node s=INVALID)
1142  {
1143    return BfsWizard<BfsWizardBase<GR> >(g,s);
1144  }
1145
1146} //END OF NAMESPACE LEMON
1147
1148#endif
1149
Note: See TracBrowser for help on using the repository browser.