COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bfs.h @ 1882:2c3f6c7e01b4

Last change on this file since 1882:2c3f6c7e01b4 was 1875:98698b69a902, checked in by Alpar Juttner, 14 years ago

Happy new year to LEMON

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