COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bfs.h @ 1721:c0f5e8401373

Last change on this file since 1721:c0f5e8401373 was 1710:f531c16dd923, checked in by Balazs Dezso, 18 years ago

Bug solved in named parameters
Simplify my Johnson algorithm

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