COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bfs.h @ 1709:a323456bf7c8

Last change on this file since 1709:a323456bf7c8 was 1709:a323456bf7c8, checked in by Balazs Dezso, 18 years ago

Template Named Parameter bugfix

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