19 #ifndef LEMON_BFS_H |
19 #ifndef LEMON_BFS_H |
20 #define LEMON_BFS_H |
20 #define LEMON_BFS_H |
21 |
21 |
22 ///\ingroup search |
22 ///\ingroup search |
23 ///\file |
23 ///\file |
24 ///\brief Bfs algorithm. |
24 ///\brief BFS algorithm. |
25 |
25 |
26 #include <lemon/list_graph.h> |
26 #include <lemon/list_graph.h> |
27 #include <lemon/graph_utils.h> |
27 #include <lemon/graph_utils.h> |
28 #include <lemon/bits/path_dump.h> |
28 #include <lemon/bits/path_dump.h> |
29 #include <lemon/bits/invalid.h> |
29 #include <lemon/bits/invalid.h> |
30 #include <lemon/error.h> |
30 #include <lemon/error.h> |
31 #include <lemon/maps.h> |
31 #include <lemon/maps.h> |
32 |
32 |
33 namespace lemon { |
33 namespace lemon { |
34 |
34 |
35 |
|
36 |
|
37 ///Default traits class of Bfs class. |
35 ///Default traits class of Bfs class. |
38 |
36 |
39 ///Default traits class of Bfs class. |
37 ///Default traits class of Bfs class. |
40 ///\tparam GR Digraph type. |
38 ///\tparam GR Digraph type. |
41 template<class GR> |
39 template<class GR> |
42 struct BfsDefaultTraits |
40 struct BfsDefaultTraits |
43 { |
41 { |
44 ///The digraph type the algorithm runs on. |
42 ///The type of the digraph the algorithm runs on. |
45 typedef GR Digraph; |
43 typedef GR Digraph; |
46 ///\brief The type of the map that stores the last |
44 |
|
45 ///\brief The type of the map that stores the predecessor |
47 ///arcs of the shortest paths. |
46 ///arcs of the shortest paths. |
48 /// |
47 /// |
49 ///The type of the map that stores the last |
48 ///The type of the map that stores the predecessor |
50 ///arcs of the shortest paths. |
49 ///arcs of the shortest paths. |
51 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
50 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
52 /// |
51 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; |
53 typedef typename Digraph::template NodeMap<typename GR::Arc> PredMap; |
52 ///Instantiates a \ref PredMap. |
54 ///Instantiates a PredMap. |
|
55 |
53 |
56 ///This function instantiates a \ref PredMap. |
54 ///This function instantiates a \ref PredMap. |
57 ///\param G is the digraph, to which we would like to define the PredMap. |
55 ///\param g is the digraph, to which we would like to define the |
|
56 ///\ref PredMap. |
58 ///\todo The digraph alone may be insufficient to initialize |
57 ///\todo The digraph alone may be insufficient to initialize |
59 static PredMap *createPredMap(const GR &G) |
58 static PredMap *createPredMap(const Digraph &g) |
60 { |
59 { |
61 return new PredMap(G); |
60 return new PredMap(g); |
62 } |
61 } |
|
62 |
63 ///The type of the map that indicates which nodes are processed. |
63 ///The type of the map that indicates which nodes are processed. |
64 |
64 |
65 ///The type of the map that indicates which nodes are processed. |
65 ///The type of the map that indicates which nodes are processed. |
66 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
66 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
67 ///\todo named parameter to set this type, function to read and write. |
67 ///By default it is a NullMap. |
68 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; |
68 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; |
69 ///Instantiates a ProcessedMap. |
69 ///Instantiates a \ref ProcessedMap. |
70 |
70 |
71 ///This function instantiates a \ref ProcessedMap. |
71 ///This function instantiates a \ref ProcessedMap. |
72 ///\param g is the digraph, to which |
72 ///\param g is the digraph, to which |
73 ///we would like to define the \ref ProcessedMap |
73 ///we would like to define the \ref ProcessedMap |
74 #ifdef DOXYGEN |
74 #ifdef DOXYGEN |
75 static ProcessedMap *createProcessedMap(const GR &g) |
75 static ProcessedMap *createProcessedMap(const Digraph &g) |
76 #else |
76 #else |
77 static ProcessedMap *createProcessedMap(const GR &) |
77 static ProcessedMap *createProcessedMap(const Digraph &) |
78 #endif |
78 #endif |
79 { |
79 { |
80 return new ProcessedMap(); |
80 return new ProcessedMap(); |
81 } |
81 } |
|
82 |
82 ///The type of the map that indicates which nodes are reached. |
83 ///The type of the map that indicates which nodes are reached. |
83 |
84 |
84 ///The type of the map that indicates which nodes are reached. |
85 ///The type of the map that indicates which nodes are reached. |
|
86 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. |
|
87 typedef typename Digraph::template NodeMap<bool> ReachedMap; |
|
88 ///Instantiates a \ref ReachedMap. |
|
89 |
|
90 ///This function instantiates a \ref ReachedMap. |
|
91 ///\param g is the digraph, to which |
|
92 ///we would like to define the \ref ReachedMap. |
|
93 static ReachedMap *createReachedMap(const Digraph &g) |
|
94 { |
|
95 return new ReachedMap(g); |
|
96 } |
|
97 |
|
98 ///The type of the map that stores the distances of the nodes. |
|
99 |
|
100 ///The type of the map that stores the distances of the nodes. |
85 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
101 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
86 ///\todo named parameter to set this type, function to read and write. |
|
87 typedef typename Digraph::template NodeMap<bool> ReachedMap; |
|
88 ///Instantiates a ReachedMap. |
|
89 |
|
90 ///This function instantiates a \ref ReachedMap. |
|
91 ///\param G is the digraph, to which |
|
92 ///we would like to define the \ref ReachedMap. |
|
93 static ReachedMap *createReachedMap(const GR &G) |
|
94 { |
|
95 return new ReachedMap(G); |
|
96 } |
|
97 ///The type of the map that stores the dists of the nodes. |
|
98 |
|
99 ///The type of the map that stores the dists of the nodes. |
|
100 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
|
101 /// |
|
102 typedef typename Digraph::template NodeMap<int> DistMap; |
102 typedef typename Digraph::template NodeMap<int> DistMap; |
103 ///Instantiates a DistMap. |
103 ///Instantiates a \ref DistMap. |
104 |
104 |
105 ///This function instantiates a \ref DistMap. |
105 ///This function instantiates a \ref DistMap. |
106 ///\param G is the digraph, to which we would like to define |
106 ///\param g is the digraph, to which we would like to define the |
107 ///the \ref DistMap |
107 ///\ref DistMap. |
108 static DistMap *createDistMap(const GR &G) |
108 static DistMap *createDistMap(const Digraph &g) |
109 { |
109 { |
110 return new DistMap(G); |
110 return new DistMap(g); |
111 } |
111 } |
112 }; |
112 }; |
113 |
113 |
114 ///%BFS algorithm class. |
114 ///%BFS algorithm class. |
115 |
115 |
116 ///\ingroup search |
116 ///\ingroup search |
117 ///This class provides an efficient implementation of the %BFS algorithm. |
117 ///This class provides an efficient implementation of the %BFS algorithm. |
118 /// |
118 /// |
119 ///\tparam GR The digraph type the algorithm runs on. The default value is |
119 ///There is also a \ref bfs() "function type interface" for the BFS |
120 ///\ref ListDigraph. The value of GR is not used directly by Bfs, it |
120 ///algorithm, which is convenient in the simplier cases and it can be |
121 ///is only passed to \ref BfsDefaultTraits. |
121 ///used easier. |
|
122 /// |
|
123 ///\tparam GR The type of the digraph the algorithm runs on. |
|
124 ///The default value is \ref ListDigraph. The value of GR is not used |
|
125 ///directly by \ref Bfs, it is only passed to \ref BfsDefaultTraits. |
122 ///\tparam TR Traits class to set various data types used by the algorithm. |
126 ///\tparam TR Traits class to set various data types used by the algorithm. |
123 ///The default traits class is |
127 ///The default traits class is |
124 ///\ref BfsDefaultTraits "BfsDefaultTraits<GR>". |
128 ///\ref BfsDefaultTraits "BfsDefaultTraits<GR>". |
125 ///See \ref BfsDefaultTraits for the documentation of |
129 ///See \ref BfsDefaultTraits for the documentation of |
126 ///a Bfs traits class. |
130 ///a Bfs traits class. |
127 |
|
128 #ifdef DOXYGEN |
131 #ifdef DOXYGEN |
129 template <typename GR, |
132 template <typename GR, |
130 typename TR> |
133 typename TR> |
131 #else |
134 #else |
132 template <typename GR=ListDigraph, |
135 template <typename GR=ListDigraph, |
133 typename TR=BfsDefaultTraits<GR> > |
136 typename TR=BfsDefaultTraits<GR> > |
134 #endif |
137 #endif |
135 class Bfs { |
138 class Bfs { |
136 public: |
139 public: |
137 /** |
140 ///\ref Exception for uninitialized parameters. |
138 * \brief \ref Exception for uninitialized parameters. |
141 |
139 * |
142 ///This error represents problems in the initialization of the |
140 * This error represents problems in the initialization |
143 ///parameters of the algorithm. |
141 * of the parameters of the algorithms. |
|
142 */ |
|
143 class UninitializedParameter : public lemon::UninitializedParameter { |
144 class UninitializedParameter : public lemon::UninitializedParameter { |
144 public: |
145 public: |
145 virtual const char* what() const throw() { |
146 virtual const char* what() const throw() { |
146 return "lemon::Bfs::UninitializedParameter"; |
147 return "lemon::Bfs::UninitializedParameter"; |
147 } |
148 } |
148 }; |
149 }; |
149 |
150 |
|
151 ///The type of the digraph the algorithm runs on. |
|
152 typedef typename TR::Digraph Digraph; |
|
153 |
|
154 ///\brief The type of the map that stores the predecessor arcs of the |
|
155 ///shortest paths. |
|
156 typedef typename TR::PredMap PredMap; |
|
157 ///The type of the map that stores the distances of the nodes. |
|
158 typedef typename TR::DistMap DistMap; |
|
159 ///The type of the map that indicates which nodes are reached. |
|
160 typedef typename TR::ReachedMap ReachedMap; |
|
161 ///The type of the map that indicates which nodes are processed. |
|
162 typedef typename TR::ProcessedMap ProcessedMap; |
|
163 ///The type of the paths. |
|
164 typedef PredMapPath<Digraph, PredMap> Path; |
|
165 |
|
166 ///The traits class. |
150 typedef TR Traits; |
167 typedef TR Traits; |
151 ///The type of the underlying digraph. |
168 |
152 typedef typename TR::Digraph Digraph; |
|
153 |
|
154 ///\brief The type of the map that stores the last |
|
155 ///arcs of the shortest paths. |
|
156 typedef typename TR::PredMap PredMap; |
|
157 ///The type of the map indicating which nodes are reached. |
|
158 typedef typename TR::ReachedMap ReachedMap; |
|
159 ///The type of the map indicating which nodes are processed. |
|
160 typedef typename TR::ProcessedMap ProcessedMap; |
|
161 ///The type of the map that stores the dists of the nodes. |
|
162 typedef typename TR::DistMap DistMap; |
|
163 private: |
169 private: |
164 |
170 |
165 typedef typename Digraph::Node Node; |
171 typedef typename Digraph::Node Node; |
166 typedef typename Digraph::NodeIt NodeIt; |
172 typedef typename Digraph::NodeIt NodeIt; |
167 typedef typename Digraph::Arc Arc; |
173 typedef typename Digraph::Arc Arc; |
168 typedef typename Digraph::OutArcIt OutArcIt; |
174 typedef typename Digraph::OutArcIt OutArcIt; |
169 |
175 |
170 /// Pointer to the underlying digraph. |
176 //Pointer to the underlying digraph. |
171 const Digraph *G; |
177 const Digraph *G; |
172 ///Pointer to the map of predecessors arcs. |
178 //Pointer to the map of predecessor arcs. |
173 PredMap *_pred; |
179 PredMap *_pred; |
174 ///Indicates if \ref _pred is locally allocated (\c true) or not. |
180 //Indicates if _pred is locally allocated (true) or not. |
175 bool local_pred; |
181 bool local_pred; |
176 ///Pointer to the map of distances. |
182 //Pointer to the map of distances. |
177 DistMap *_dist; |
183 DistMap *_dist; |
178 ///Indicates if \ref _dist is locally allocated (\c true) or not. |
184 //Indicates if _dist is locally allocated (true) or not. |
179 bool local_dist; |
185 bool local_dist; |
180 ///Pointer to the map of reached status of the nodes. |
186 //Pointer to the map of reached status of the nodes. |
181 ReachedMap *_reached; |
187 ReachedMap *_reached; |
182 ///Indicates if \ref _reached is locally allocated (\c true) or not. |
188 //Indicates if _reached is locally allocated (true) or not. |
183 bool local_reached; |
189 bool local_reached; |
184 ///Pointer to the map of processed status of the nodes. |
190 //Pointer to the map of processed status of the nodes. |
185 ProcessedMap *_processed; |
191 ProcessedMap *_processed; |
186 ///Indicates if \ref _processed is locally allocated (\c true) or not. |
192 //Indicates if _processed is locally allocated (true) or not. |
187 bool local_processed; |
193 bool local_processed; |
188 |
194 |
189 std::vector<typename Digraph::Node> _queue; |
195 std::vector<typename Digraph::Node> _queue; |
190 int _queue_head,_queue_tail,_queue_next_dist; |
196 int _queue_head,_queue_tail,_queue_next_dist; |
191 int _curr_dist; |
197 int _curr_dist; |
192 |
198 |
193 ///Creates the maps if necessary. |
199 ///Creates the maps if necessary. |
194 |
|
195 ///\todo Better memory allocation (instead of new). |
200 ///\todo Better memory allocation (instead of new). |
196 void create_maps() |
201 void create_maps() |
197 { |
202 { |
198 if(!_pred) { |
203 if(!_pred) { |
199 local_pred = true; |
204 local_pred = true; |
544 if (nm[m] && rnode == INVALID) rnode = m; |
555 if (nm[m] && rnode == INVALID) rnode = m; |
545 } |
556 } |
546 return n; |
557 return n; |
547 } |
558 } |
548 |
559 |
549 ///Next node to be processed. |
560 ///The next node to be processed. |
550 |
561 |
551 ///Next node to be processed. |
562 ///Returns the next node to be processed or \c INVALID if the queue |
552 /// |
563 ///is empty. |
553 ///\return The next node to be processed or INVALID if the queue is |
564 Node nextNode() const |
554 /// empty. |
|
555 Node nextNode() |
|
556 { |
565 { |
557 return _queue_tail<_queue_head?_queue[_queue_tail]:INVALID; |
566 return _queue_tail<_queue_head?_queue[_queue_tail]:INVALID; |
558 } |
567 } |
559 |
568 |
560 ///\brief Returns \c false if there are nodes |
569 ///\brief Returns \c false if there are nodes |
561 ///to be processed in the queue |
570 ///to be processed. |
562 /// |
571 /// |
563 ///Returns \c false if there are nodes |
572 ///Returns \c false if there are nodes |
564 ///to be processed in the queue |
573 ///to be processed in the queue. |
565 bool emptyQueue() { return _queue_tail==_queue_head; } |
574 bool emptyQueue() const { return _queue_tail==_queue_head; } |
|
575 |
566 ///Returns the number of the nodes to be processed. |
576 ///Returns the number of the nodes to be processed. |
567 |
577 |
568 ///Returns the number of the nodes to be processed in the queue. |
578 ///Returns the number of the nodes to be processed in the queue. |
569 int queueSize() { return _queue_head-_queue_tail; } |
579 int queueSize() const { return _queue_head-_queue_tail; } |
570 |
580 |
571 ///Executes the algorithm. |
581 ///Executes the algorithm. |
572 |
582 |
573 ///Executes the algorithm. |
583 ///Executes the algorithm. |
574 /// |
584 /// |
575 ///\pre init() must be called and at least one node should be added |
|
576 ///with addSource() before using this function. |
|
577 /// |
|
578 ///This method runs the %BFS algorithm from the root node(s) |
585 ///This method runs the %BFS algorithm from the root node(s) |
579 ///in order to |
586 ///in order to compute the shortest path to each node. |
580 ///compute the |
587 /// |
581 ///shortest path to each node. The algorithm computes |
588 ///The algorithm computes |
582 ///- The shortest path tree. |
589 ///- the shortest path tree (forest), |
583 ///- The distance of each node from the root(s). |
590 ///- the distance of each node from the root(s). |
|
591 /// |
|
592 ///\pre init() must be called and at least one root node should be |
|
593 ///added with addSource() before using this function. |
|
594 /// |
|
595 ///\note <tt>b.start()</tt> is just a shortcut of the following code. |
|
596 ///\code |
|
597 /// while ( !b.emptyQueue() ) { |
|
598 /// b.processNextNode(); |
|
599 /// } |
|
600 ///\endcode |
584 void start() |
601 void start() |
585 { |
602 { |
586 while ( !emptyQueue() ) processNextNode(); |
603 while ( !emptyQueue() ) processNextNode(); |
587 } |
604 } |
588 |
605 |
589 ///Executes the algorithm until \c dest is reached. |
606 ///Executes the algorithm until the given target node is reached. |
590 |
607 |
591 ///Executes the algorithm until \c dest is reached. |
608 ///Executes the algorithm until the given target node is reached. |
592 /// |
|
593 ///\pre init() must be called and at least one node should be added |
|
594 ///with addSource() before using this function. |
|
595 /// |
609 /// |
596 ///This method runs the %BFS algorithm from the root node(s) |
610 ///This method runs the %BFS algorithm from the root node(s) |
597 ///in order to compute the shortest path to \c dest. |
611 ///in order to compute the shortest path to \c dest. |
|
612 /// |
598 ///The algorithm computes |
613 ///The algorithm computes |
599 ///- The shortest path to \c dest. |
614 ///- the shortest path to \c dest, |
600 ///- The distance of \c dest from the root(s). |
615 ///- the distance of \c dest from the root(s). |
|
616 /// |
|
617 ///\pre init() must be called and at least one root node should be |
|
618 ///added with addSource() before using this function. |
|
619 /// |
|
620 ///\note <tt>b.start(t)</tt> is just a shortcut of the following code. |
|
621 ///\code |
|
622 /// bool reach = false; |
|
623 /// while ( !b.emptyQueue() && !reach ) { |
|
624 /// b.processNextNode(t, reach); |
|
625 /// } |
|
626 ///\endcode |
601 void start(Node dest) |
627 void start(Node dest) |
602 { |
628 { |
603 bool reach = false; |
629 bool reach = false; |
604 while ( !emptyQueue() && !reach ) processNextNode(dest, reach); |
630 while ( !emptyQueue() && !reach ) processNextNode(dest, reach); |
605 } |
631 } |
606 |
632 |
607 ///Executes the algorithm until a condition is met. |
633 ///Executes the algorithm until a condition is met. |
608 |
634 |
609 ///Executes the algorithm until a condition is met. |
635 ///Executes the algorithm until a condition is met. |
610 /// |
636 /// |
611 ///\pre init() must be called and at least one node should be added |
637 ///This method runs the %BFS algorithm from the root node(s) in |
612 ///with addSource() before using this function. |
638 ///order to compute the shortest path to a node \c v with |
613 /// |
639 /// <tt>nm[v]</tt> true, if such a node can be found. |
614 ///\param nm must be a bool (or convertible) node map. The |
640 /// |
615 ///algorithm will stop when it reaches a node \c v with |
641 ///\param nm A \c bool (or convertible) node map. The algorithm |
616 /// <tt>nm[v]</tt> true. |
642 ///will stop when it reaches a node \c v with <tt>nm[v]</tt> true. |
617 /// |
643 /// |
618 ///\return The reached node \c v with <tt>nm[v]</tt> true or |
644 ///\return The reached node \c v with <tt>nm[v]</tt> true or |
619 ///\c INVALID if no such node was found. |
645 ///\c INVALID if no such node was found. |
620 template<class NM> |
646 /// |
621 Node start(const NM &nm) |
647 ///\pre init() must be called and at least one root node should be |
|
648 ///added with addSource() before using this function. |
|
649 /// |
|
650 ///\note <tt>b.start(nm)</tt> is just a shortcut of the following code. |
|
651 ///\code |
|
652 /// Node rnode = INVALID; |
|
653 /// while ( !b.emptyQueue() && rnode == INVALID ) { |
|
654 /// b.processNextNode(nm, rnode); |
|
655 /// } |
|
656 /// return rnode; |
|
657 ///\endcode |
|
658 template<class NodeBoolMap> |
|
659 Node start(const NodeBoolMap &nm) |
622 { |
660 { |
623 Node rnode = INVALID; |
661 Node rnode = INVALID; |
624 while ( !emptyQueue() && rnode == INVALID ) { |
662 while ( !emptyQueue() && rnode == INVALID ) { |
625 processNextNode(nm, rnode); |
663 processNextNode(nm, rnode); |
626 } |
664 } |
627 return rnode; |
665 return rnode; |
628 } |
666 } |
629 |
667 |
630 ///Runs %BFS algorithm from node \c s. |
668 ///Runs the algorithm from the given node. |
631 |
669 |
632 ///This method runs the %BFS algorithm from a root node \c s |
670 ///This method runs the %BFS algorithm from node \c s |
633 ///in order to |
671 ///in order to compute the shortest path to each node. |
634 ///compute the |
672 /// |
635 ///shortest path to each node. The algorithm computes |
673 ///The algorithm computes |
636 ///- The shortest path tree. |
674 ///- the shortest path tree, |
637 ///- The distance of each node from the root. |
675 ///- the distance of each node from the root. |
638 /// |
676 /// |
639 ///\note b.run(s) is just a shortcut of the following code. |
677 ///\note <tt>b.run(s)</tt> is just a shortcut of the following code. |
640 ///\code |
678 ///\code |
641 /// b.init(); |
679 /// b.init(); |
642 /// b.addSource(s); |
680 /// b.addSource(s); |
643 /// b.start(); |
681 /// b.start(); |
644 ///\endcode |
682 ///\endcode |
666 addSource(s); |
706 addSource(s); |
667 start(t); |
707 start(t); |
668 return reached(t) ? _curr_dist : 0; |
708 return reached(t) ? _curr_dist : 0; |
669 } |
709 } |
670 |
710 |
|
711 ///Runs the algorithm to visit all nodes in the digraph. |
|
712 |
|
713 ///This method runs the %BFS algorithm in order to |
|
714 ///compute the shortest path to each node. |
|
715 /// |
|
716 ///The algorithm computes |
|
717 ///- the shortest path tree (forest), |
|
718 ///- the distance of each node from the root(s). |
|
719 /// |
|
720 ///\note <tt>b.run(s)</tt> is just a shortcut of the following code. |
|
721 ///\code |
|
722 /// b.init(); |
|
723 /// for (NodeIt n(gr); n != INVALID; ++n) { |
|
724 /// if (!b.reached(n)) { |
|
725 /// b.addSource(n); |
|
726 /// b.start(); |
|
727 /// } |
|
728 /// } |
|
729 ///\endcode |
|
730 void run() { |
|
731 init(); |
|
732 for (NodeIt n(*G); n != INVALID; ++n) { |
|
733 if (!reached(n)) { |
|
734 addSource(n); |
|
735 start(); |
|
736 } |
|
737 } |
|
738 } |
|
739 |
671 ///@} |
740 ///@} |
672 |
741 |
673 ///\name Query Functions |
742 ///\name Query Functions |
674 ///The result of the %BFS algorithm can be obtained using these |
743 ///The result of the %BFS algorithm can be obtained using these |
675 ///functions.\n |
744 ///functions.\n |
676 ///Before the use of these functions, |
745 ///Either \ref lemon::Bfs::run() "run()" or \ref lemon::Bfs::start() |
677 ///either run() or start() must be calleb. |
746 ///"start()" must be called before using them. |
678 |
747 |
679 ///@{ |
748 ///@{ |
680 |
749 |
681 typedef PredMapPath<Digraph, PredMap> Path; |
750 ///The shortest path to a node. |
682 |
751 |
683 ///Gives back the shortest path. |
752 ///Returns the shortest path to a node. |
684 |
753 /// |
685 ///Gives back the shortest path. |
754 ///\warning \c t should be reachable from the root(s). |
686 ///\pre The \c t should be reachable from the source. |
755 /// |
687 Path path(Node t) |
756 ///\pre Either \ref run() or \ref start() must be called before |
688 { |
757 ///using this function. |
689 return Path(*G, *_pred, t); |
758 Path path(Node t) const { return Path(*G, *_pred, t); } |
690 } |
|
691 |
759 |
692 ///The distance of a node from the root(s). |
760 ///The distance of a node from the root(s). |
693 |
761 |
694 ///Returns the distance of a node from the root(s). |
762 ///Returns the distance of a node from the root(s). |
695 ///\pre \ref run() must be called before using this function. |
763 /// |
696 ///\warning If node \c v in unreachable from the root(s) the return value |
764 ///\warning If node \c v is not reachable from the root(s), then |
697 ///of this function is undefined. |
765 ///the return value of this function is undefined. |
|
766 /// |
|
767 ///\pre Either \ref run() or \ref start() must be called before |
|
768 ///using this function. |
698 int dist(Node v) const { return (*_dist)[v]; } |
769 int dist(Node v) const { return (*_dist)[v]; } |
699 |
770 |
700 ///Returns the 'previous arc' of the shortest path tree. |
771 ///Returns the 'previous arc' of the shortest path tree for a node. |
701 |
772 |
702 ///For a node \c v it returns the 'previous arc' |
773 ///This function returns the 'previous arc' of the shortest path |
703 ///of the shortest path tree, |
774 ///tree for the node \c v, i.e. it returns the last arc of a |
704 ///i.e. it returns the last arc of a shortest path from the root(s) to \c |
775 ///shortest path from the root(s) to \c v. It is \c INVALID if \c v |
705 ///v. It is \ref INVALID |
776 ///is not reachable from the root(s) or if \c v is a root. |
706 ///if \c v is unreachable from the root(s) or \c v is a root. The |
777 /// |
707 ///shortest path tree used here is equal to the shortest path tree used in |
778 ///The shortest path tree used here is equal to the shortest path |
708 ///\ref predNode(). |
779 ///tree used in \ref predNode(). |
709 ///\pre Either \ref run() or \ref start() must be called before using |
780 /// |
710 ///this function. |
781 ///\pre Either \ref run() or \ref start() must be called before |
|
782 ///using this function. |
711 Arc predArc(Node v) const { return (*_pred)[v];} |
783 Arc predArc(Node v) const { return (*_pred)[v];} |
712 |
784 |
713 ///Returns the 'previous node' of the shortest path tree. |
785 ///Returns the 'previous node' of the shortest path tree for a node. |
714 |
786 |
715 ///For a node \c v it returns the 'previous node' |
787 ///This function returns the 'previous node' of the shortest path |
716 ///of the shortest path tree, |
788 ///tree for the node \c v, i.e. it returns the last but one node |
717 ///i.e. it returns the last but one node from a shortest path from the |
789 ///from a shortest path from the root(s) to \c v. It is \c INVALID |
718 ///root(a) to \c /v. |
790 ///if \c v is not reachable from the root(s) or if \c v is a root. |
719 ///It is INVALID if \c v is unreachable from the root(s) or |
791 /// |
720 ///if \c v itself a root. |
|
721 ///The shortest path tree used here is equal to the shortest path |
792 ///The shortest path tree used here is equal to the shortest path |
722 ///tree used in \ref predArc(). |
793 ///tree used in \ref predArc(). |
|
794 /// |
723 ///\pre Either \ref run() or \ref start() must be called before |
795 ///\pre Either \ref run() or \ref start() must be called before |
724 ///using this function. |
796 ///using this function. |
725 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: |
797 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: |
726 G->source((*_pred)[v]); } |
798 G->source((*_pred)[v]); } |
727 |
799 |
728 ///Returns a reference to the NodeMap of distances. |
800 ///\brief Returns a const reference to the node map that stores the |
729 |
801 /// distances of the nodes. |
730 ///Returns a reference to the NodeMap of distances. |
802 /// |
731 ///\pre Either \ref run() or \ref init() must |
803 ///Returns a const reference to the node map that stores the distances |
732 ///be called before using this function. |
804 ///of the nodes calculated by the algorithm. |
|
805 /// |
|
806 ///\pre Either \ref run() or \ref init() |
|
807 ///must be called before using this function. |
733 const DistMap &distMap() const { return *_dist;} |
808 const DistMap &distMap() const { return *_dist;} |
734 |
809 |
735 ///Returns a reference to the shortest path tree map. |
810 ///\brief Returns a const reference to the node map that stores the |
736 |
811 ///predecessor arcs. |
737 ///Returns a reference to the NodeMap of the arcs of the |
812 /// |
738 ///shortest path tree. |
813 ///Returns a const reference to the node map that stores the predecessor |
|
814 ///arcs, which form the shortest path tree. |
|
815 /// |
739 ///\pre Either \ref run() or \ref init() |
816 ///\pre Either \ref run() or \ref init() |
740 ///must be called before using this function. |
817 ///must be called before using this function. |
741 const PredMap &predMap() const { return *_pred;} |
818 const PredMap &predMap() const { return *_pred;} |
742 |
819 |
743 ///Checks if a node is reachable from the root. |
820 ///Checks if a node is reachable from the root(s). |
744 |
821 |
745 ///Returns \c true if \c v is reachable from the root. |
822 ///Returns \c true if \c v is reachable from the root(s). |
746 ///\warning The source nodes are indicated as unreached. |
|
747 ///\pre Either \ref run() or \ref start() |
823 ///\pre Either \ref run() or \ref start() |
748 ///must be called before using this function. |
824 ///must be called before using this function. |
749 /// |
825 bool reached(Node v) const { return (*_reached)[v]; } |
750 bool reached(Node v) { return (*_reached)[v]; } |
|
751 |
826 |
752 ///@} |
827 ///@} |
753 }; |
828 }; |
754 |
829 |
755 ///Default traits class of Bfs function. |
830 ///Default traits class of bfs() function. |
756 |
831 |
757 ///Default traits class of Bfs function. |
832 ///Default traits class of bfs() function. |
758 ///\tparam GR Digraph type. |
833 ///\tparam GR Digraph type. |
759 template<class GR> |
834 template<class GR> |
760 struct BfsWizardDefaultTraits |
835 struct BfsWizardDefaultTraits |
761 { |
836 { |
762 ///The digraph type the algorithm runs on. |
837 ///The type of the digraph the algorithm runs on. |
763 typedef GR Digraph; |
838 typedef GR Digraph; |
764 ///\brief The type of the map that stores the last |
839 |
|
840 ///\brief The type of the map that stores the predecessor |
765 ///arcs of the shortest paths. |
841 ///arcs of the shortest paths. |
766 /// |
842 /// |
767 ///The type of the map that stores the last |
843 ///The type of the map that stores the predecessor |
768 ///arcs of the shortest paths. |
844 ///arcs of the shortest paths. |
769 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
845 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
770 /// |
846 typedef NullMap<typename Digraph::Node,typename Digraph::Arc> PredMap; |
771 typedef NullMap<typename Digraph::Node,typename GR::Arc> PredMap; |
847 ///Instantiates a \ref PredMap. |
772 ///Instantiates a PredMap. |
|
773 |
848 |
774 ///This function instantiates a \ref PredMap. |
849 ///This function instantiates a \ref PredMap. |
775 ///\param g is the digraph, to which we would like to define the PredMap. |
850 ///\param g is the digraph, to which we would like to define the |
|
851 ///\ref PredMap. |
776 ///\todo The digraph alone may be insufficient to initialize |
852 ///\todo The digraph alone may be insufficient to initialize |
777 #ifdef DOXYGEN |
853 #ifdef DOXYGEN |
778 static PredMap *createPredMap(const GR &g) |
854 static PredMap *createPredMap(const Digraph &g) |
779 #else |
855 #else |
780 static PredMap *createPredMap(const GR &) |
856 static PredMap *createPredMap(const Digraph &) |
781 #endif |
857 #endif |
782 { |
858 { |
783 return new PredMap(); |
859 return new PredMap(); |
784 } |
860 } |
785 |
861 |
786 ///The type of the map that indicates which nodes are processed. |
862 ///The type of the map that indicates which nodes are processed. |
787 |
863 |
788 ///The type of the map that indicates which nodes are processed. |
864 ///The type of the map that indicates which nodes are processed. |
789 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
865 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
790 ///\todo named parameter to set this type, function to read and write. |
|
791 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; |
866 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; |
792 ///Instantiates a ProcessedMap. |
867 ///Instantiates a \ref ProcessedMap. |
793 |
868 |
794 ///This function instantiates a \ref ProcessedMap. |
869 ///This function instantiates a \ref ProcessedMap. |
795 ///\param g is the digraph, to which |
870 ///\param g is the digraph, to which |
796 ///we would like to define the \ref ProcessedMap |
871 ///we would like to define the \ref ProcessedMap. |
797 #ifdef DOXYGEN |
872 #ifdef DOXYGEN |
798 static ProcessedMap *createProcessedMap(const GR &g) |
873 static ProcessedMap *createProcessedMap(const Digraph &g) |
799 #else |
874 #else |
800 static ProcessedMap *createProcessedMap(const GR &) |
875 static ProcessedMap *createProcessedMap(const Digraph &) |
801 #endif |
876 #endif |
802 { |
877 { |
803 return new ProcessedMap(); |
878 return new ProcessedMap(); |
804 } |
879 } |
|
880 |
805 ///The type of the map that indicates which nodes are reached. |
881 ///The type of the map that indicates which nodes are reached. |
806 |
882 |
807 ///The type of the map that indicates which nodes are reached. |
883 ///The type of the map that indicates which nodes are reached. |
|
884 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. |
|
885 typedef typename Digraph::template NodeMap<bool> ReachedMap; |
|
886 ///Instantiates a \ref ReachedMap. |
|
887 |
|
888 ///This function instantiates a \ref ReachedMap. |
|
889 ///\param g is the digraph, to which |
|
890 ///we would like to define the \ref ReachedMap. |
|
891 static ReachedMap *createReachedMap(const Digraph &g) |
|
892 { |
|
893 return new ReachedMap(g); |
|
894 } |
|
895 |
|
896 ///The type of the map that stores the distances of the nodes. |
|
897 |
|
898 ///The type of the map that stores the distances of the nodes. |
808 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
899 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
809 ///\todo named parameter to set this type, function to read and write. |
|
810 typedef typename Digraph::template NodeMap<bool> ReachedMap; |
|
811 ///Instantiates a ReachedMap. |
|
812 |
|
813 ///This function instantiates a \ref ReachedMap. |
|
814 ///\param G is the digraph, to which |
|
815 ///we would like to define the \ref ReachedMap. |
|
816 static ReachedMap *createReachedMap(const GR &G) |
|
817 { |
|
818 return new ReachedMap(G); |
|
819 } |
|
820 ///The type of the map that stores the dists of the nodes. |
|
821 |
|
822 ///The type of the map that stores the dists of the nodes. |
|
823 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
|
824 /// |
900 /// |
825 typedef NullMap<typename Digraph::Node,int> DistMap; |
901 typedef NullMap<typename Digraph::Node,int> DistMap; |
826 ///Instantiates a DistMap. |
902 ///Instantiates a \ref DistMap. |
827 |
903 |
828 ///This function instantiates a \ref DistMap. |
904 ///This function instantiates a \ref DistMap. |
829 ///\param g is the digraph, to which we would like to define |
905 ///\param g is the digraph, to which we would like to define |
830 ///the \ref DistMap |
906 ///the \ref DistMap |
831 #ifdef DOXYGEN |
907 #ifdef DOXYGEN |
832 static DistMap *createDistMap(const GR &g) |
908 static DistMap *createDistMap(const Digraph &g) |
833 #else |
909 #else |
834 static DistMap *createDistMap(const GR &) |
910 static DistMap *createDistMap(const Digraph &) |
835 #endif |
911 #endif |
836 { |
912 { |
837 return new DistMap(); |
913 return new DistMap(); |
838 } |
914 } |
839 }; |
915 }; |
840 |
916 |
841 /// Default traits used by \ref BfsWizard |
917 /// Default traits class used by \ref BfsWizard |
842 |
918 |
843 /// To make it easier to use Bfs algorithm |
919 /// To make it easier to use Bfs algorithm |
844 ///we have created a wizard class. |
920 /// we have created a wizard class. |
845 /// This \ref BfsWizard class needs default traits, |
921 /// This \ref BfsWizard class needs default traits, |
846 ///as well as the \ref Bfs class. |
922 /// as well as the \ref Bfs class. |
847 /// The \ref BfsWizardBase is a class to be the default traits of the |
923 /// The \ref BfsWizardBase is a class to be the default traits of the |
848 /// \ref BfsWizard class. |
924 /// \ref BfsWizard class. |
849 template<class GR> |
925 template<class GR> |
850 class BfsWizardBase : public BfsWizardDefaultTraits<GR> |
926 class BfsWizardBase : public BfsWizardDefaultTraits<GR> |
851 { |
927 { |
852 |
928 |
853 typedef BfsWizardDefaultTraits<GR> Base; |
929 typedef BfsWizardDefaultTraits<GR> Base; |
854 protected: |
930 protected: |
855 /// Type of the nodes in the digraph. |
931 //The type of the nodes in the digraph. |
856 typedef typename Base::Digraph::Node Node; |
932 typedef typename Base::Digraph::Node Node; |
857 |
933 |
858 /// Pointer to the underlying digraph. |
934 //Pointer to the digraph the algorithm runs on. |
859 void *_g; |
935 void *_g; |
860 ///Pointer to the map of reached nodes. |
936 //Pointer to the map of reached nodes. |
861 void *_reached; |
937 void *_reached; |
862 ///Pointer to the map of processed nodes. |
938 //Pointer to the map of processed nodes. |
863 void *_processed; |
939 void *_processed; |
864 ///Pointer to the map of predecessors arcs. |
940 //Pointer to the map of predecessors arcs. |
865 void *_pred; |
941 void *_pred; |
866 ///Pointer to the map of distances. |
942 //Pointer to the map of distances. |
867 void *_dist; |
943 void *_dist; |
868 ///Pointer to the source node. |
944 //Pointer to the source node. |
869 Node _source; |
945 Node _source; |
870 |
946 |
871 public: |
947 public: |
872 /// Constructor. |
948 /// Constructor. |
873 |
949 |
874 /// This constructor does not require parameters, therefore it initiates |
950 /// This constructor does not require parameters, therefore it initiates |
875 /// all of the attributes to default values (0, INVALID). |
951 /// all of the attributes to default values (0, INVALID). |
876 BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), |
952 BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), |
877 _dist(0), _source(INVALID) {} |
953 _dist(0), _source(INVALID) {} |
878 |
954 |
879 /// Constructor. |
955 /// Constructor. |
880 |
956 |
881 /// This constructor requires some parameters, |
957 /// This constructor requires some parameters, |
882 /// listed in the parameters list. |
958 /// listed in the parameters list. |
883 /// Others are initiated to 0. |
959 /// Others are initiated to 0. |
884 /// \param g is the initial value of \ref _g |
960 /// \param g The digraph the algorithm runs on. |
885 /// \param s is the initial value of \ref _source |
961 /// \param s The source node. |
886 BfsWizardBase(const GR &g, Node s=INVALID) : |
962 BfsWizardBase(const GR &g, Node s=INVALID) : |
887 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))), |
963 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))), |
888 _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {} |
964 _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {} |
889 |
965 |
890 }; |
966 }; |
891 |
967 |
892 /// A class to make the usage of Bfs algorithm easier |
968 /// Auxiliary class for the function type interface of BFS algorithm. |
893 |
969 |
894 /// This class is created to make it easier to use Bfs algorithm. |
970 /// This auxiliary class is created to implement the function type |
895 /// It uses the functions and features of the plain \ref Bfs, |
971 /// interface of \ref Bfs algorithm. It uses the functions and features |
896 /// but it is much simpler to use it. |
972 /// of the plain \ref Bfs, but it is much simpler to use it. |
|
973 /// It should only be used through the \ref bfs() function, which makes |
|
974 /// it easier to use the algorithm. |
897 /// |
975 /// |
898 /// Simplicity means that the way to change the types defined |
976 /// Simplicity means that the way to change the types defined |
899 /// in the traits class is based on functions that returns the new class |
977 /// in the traits class is based on functions that returns the new class |
900 /// and not on templatable built-in classes. |
978 /// and not on templatable built-in classes. |
901 /// When using the plain \ref Bfs |
979 /// When using the plain \ref Bfs |
902 /// the new class with the modified type comes from |
980 /// the new class with the modified type comes from |
903 /// the original class by using the :: |
981 /// the original class by using the :: |
904 /// operator. In the case of \ref BfsWizard only |
982 /// operator. In the case of \ref BfsWizard only |
905 /// a function have to be called and it will |
983 /// a function have to be called, and it will |
906 /// return the needed class. |
984 /// return the needed class. |
907 /// |
985 /// |
908 /// It does not have own \ref run method. When its \ref run method is called |
986 /// It does not have own \ref run() method. When its \ref run() method |
909 /// it initiates a plain \ref Bfs class, and calls the \ref Bfs::run |
987 /// is called, it initiates a plain \ref Bfs object, and calls the |
910 /// method of it. |
988 /// \ref Bfs::run() method of it. |
911 template<class TR> |
989 template<class TR> |
912 class BfsWizard : public TR |
990 class BfsWizard : public TR |
913 { |
991 { |
914 typedef TR Base; |
992 typedef TR Base; |
915 |
993 |
916 ///The type of the underlying digraph. |
994 ///The type of the digraph the algorithm runs on. |
917 typedef typename TR::Digraph Digraph; |
995 typedef typename TR::Digraph Digraph; |
918 //\e |
996 |
919 typedef typename Digraph::Node Node; |
997 typedef typename Digraph::Node Node; |
920 //\e |
|
921 typedef typename Digraph::NodeIt NodeIt; |
998 typedef typename Digraph::NodeIt NodeIt; |
922 //\e |
|
923 typedef typename Digraph::Arc Arc; |
999 typedef typename Digraph::Arc Arc; |
924 //\e |
|
925 typedef typename Digraph::OutArcIt OutArcIt; |
1000 typedef typename Digraph::OutArcIt OutArcIt; |
926 |
1001 |
927 ///\brief The type of the map that stores |
1002 ///\brief The type of the map that stores the predecessor |
928 ///the reached nodes |
|
929 typedef typename TR::ReachedMap ReachedMap; |
|
930 ///\brief The type of the map that stores |
|
931 ///the processed nodes |
|
932 typedef typename TR::ProcessedMap ProcessedMap; |
|
933 ///\brief The type of the map that stores the last |
|
934 ///arcs of the shortest paths. |
1003 ///arcs of the shortest paths. |
935 typedef typename TR::PredMap PredMap; |
1004 typedef typename TR::PredMap PredMap; |
936 ///The type of the map that stores the dists of the nodes. |
1005 ///\brief The type of the map that stores the distances of the nodes. |
937 typedef typename TR::DistMap DistMap; |
1006 typedef typename TR::DistMap DistMap; |
|
1007 ///\brief The type of the map that indicates which nodes are reached. |
|
1008 typedef typename TR::ReachedMap ReachedMap; |
|
1009 ///\brief The type of the map that indicates which nodes are processed. |
|
1010 typedef typename TR::ProcessedMap ProcessedMap; |
938 |
1011 |
939 public: |
1012 public: |
|
1013 |
940 /// Constructor. |
1014 /// Constructor. |
941 BfsWizard() : TR() {} |
1015 BfsWizard() : TR() {} |
942 |
1016 |
943 /// Constructor that requires parameters. |
1017 /// Constructor that requires parameters. |
944 |
1018 |
969 if(Base::_dist) |
1043 if(Base::_dist) |
970 alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist)); |
1044 alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist)); |
971 alg.run(Base::_source); |
1045 alg.run(Base::_source); |
972 } |
1046 } |
973 |
1047 |
974 ///Runs Bfs algorithm from the given node. |
1048 ///Runs BFS algorithm from the given node. |
975 |
1049 |
976 ///Runs Bfs algorithm from the given node. |
1050 ///Runs BFS algorithm from the given node. |
977 ///\param s is the given source. |
1051 ///\param s is the given source. |
978 void run(Node s) |
1052 void run(Node s) |
979 { |
1053 { |
980 Base::_source=s; |
1054 Base::_source=s; |
981 run(); |
1055 run(); |
|
1056 } |
|
1057 |
|
1058 /// Sets the source node, from which the Bfs algorithm runs. |
|
1059 |
|
1060 /// Sets the source node, from which the Bfs algorithm runs. |
|
1061 /// \param s is the source node. |
|
1062 BfsWizard<TR> &source(Node s) |
|
1063 { |
|
1064 Base::_source=s; |
|
1065 return *this; |
982 } |
1066 } |
983 |
1067 |
984 template<class T> |
1068 template<class T> |
985 struct DefPredMapBase : public Base { |
1069 struct DefPredMapBase : public Base { |
986 typedef T PredMap; |
1070 typedef T PredMap; |
987 static PredMap *createPredMap(const Digraph &) { return 0; }; |
1071 static PredMap *createPredMap(const Digraph &) { return 0; }; |
988 DefPredMapBase(const TR &b) : TR(b) {} |
1072 DefPredMapBase(const TR &b) : TR(b) {} |
989 }; |
1073 }; |
990 |
|
991 ///\brief \ref named-templ-param "Named parameter" |
1074 ///\brief \ref named-templ-param "Named parameter" |
992 ///function for setting PredMap |
1075 ///for setting \ref PredMap object. |
993 /// |
1076 /// |
994 /// \ref named-templ-param "Named parameter" |
1077 /// \ref named-templ-param "Named parameter" |
995 ///function for setting PredMap |
1078 ///for setting \ref PredMap object. |
996 /// |
|
997 template<class T> |
1079 template<class T> |
998 BfsWizard<DefPredMapBase<T> > predMap(const T &t) |
1080 BfsWizard<DefPredMapBase<T> > predMap(const T &t) |
999 { |
1081 { |
1000 Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1082 Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1001 return BfsWizard<DefPredMapBase<T> >(*this); |
1083 return BfsWizard<DefPredMapBase<T> >(*this); |
1002 } |
1084 } |
1003 |
|
1004 |
1085 |
1005 template<class T> |
1086 template<class T> |
1006 struct DefReachedMapBase : public Base { |
1087 struct DefReachedMapBase : public Base { |
1007 typedef T ReachedMap; |
1088 typedef T ReachedMap; |
1008 static ReachedMap *createReachedMap(const Digraph &) { return 0; }; |
1089 static ReachedMap *createReachedMap(const Digraph &) { return 0; }; |
1009 DefReachedMapBase(const TR &b) : TR(b) {} |
1090 DefReachedMapBase(const TR &b) : TR(b) {} |
1010 }; |
1091 }; |
1011 |
|
1012 ///\brief \ref named-templ-param "Named parameter" |
1092 ///\brief \ref named-templ-param "Named parameter" |
1013 ///function for setting ReachedMap |
1093 ///for setting \ref ReachedMap object. |
1014 /// |
1094 /// |
1015 /// \ref named-templ-param "Named parameter" |
1095 /// \ref named-templ-param "Named parameter" |
1016 ///function for setting ReachedMap |
1096 ///for setting \ref ReachedMap object. |
1017 /// |
|
1018 template<class T> |
1097 template<class T> |
1019 BfsWizard<DefReachedMapBase<T> > reachedMap(const T &t) |
1098 BfsWizard<DefReachedMapBase<T> > reachedMap(const T &t) |
1020 { |
1099 { |
1021 Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1100 Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1022 return BfsWizard<DefReachedMapBase<T> >(*this); |
1101 return BfsWizard<DefReachedMapBase<T> >(*this); |
1023 } |
1102 } |
1024 |
|
1025 |
1103 |
1026 template<class T> |
1104 template<class T> |
1027 struct DefProcessedMapBase : public Base { |
1105 struct DefProcessedMapBase : public Base { |
1028 typedef T ProcessedMap; |
1106 typedef T ProcessedMap; |
1029 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; }; |
1107 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; }; |
1030 DefProcessedMapBase(const TR &b) : TR(b) {} |
1108 DefProcessedMapBase(const TR &b) : TR(b) {} |
1031 }; |
1109 }; |
1032 |
|
1033 ///\brief \ref named-templ-param "Named parameter" |
1110 ///\brief \ref named-templ-param "Named parameter" |
1034 ///function for setting ProcessedMap |
1111 ///for setting \ref ProcessedMap object. |
1035 /// |
1112 /// |
1036 /// \ref named-templ-param "Named parameter" |
1113 /// \ref named-templ-param "Named parameter" |
1037 ///function for setting ProcessedMap |
1114 ///for setting \ref ProcessedMap object. |
1038 /// |
|
1039 template<class T> |
1115 template<class T> |
1040 BfsWizard<DefProcessedMapBase<T> > processedMap(const T &t) |
1116 BfsWizard<DefProcessedMapBase<T> > processedMap(const T &t) |
1041 { |
1117 { |
1042 Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1118 Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1043 return BfsWizard<DefProcessedMapBase<T> >(*this); |
1119 return BfsWizard<DefProcessedMapBase<T> >(*this); |
1044 } |
1120 } |
1045 |
|
1046 |
1121 |
1047 template<class T> |
1122 template<class T> |
1048 struct DefDistMapBase : public Base { |
1123 struct DefDistMapBase : public Base { |
1049 typedef T DistMap; |
1124 typedef T DistMap; |
1050 static DistMap *createDistMap(const Digraph &) { return 0; }; |
1125 static DistMap *createDistMap(const Digraph &) { return 0; }; |
1051 DefDistMapBase(const TR &b) : TR(b) {} |
1126 DefDistMapBase(const TR &b) : TR(b) {} |
1052 }; |
1127 }; |
1053 |
|
1054 ///\brief \ref named-templ-param "Named parameter" |
1128 ///\brief \ref named-templ-param "Named parameter" |
1055 ///function for setting DistMap type |
1129 ///for setting \ref DistMap object. |
1056 /// |
1130 /// |
1057 /// \ref named-templ-param "Named parameter" |
1131 /// \ref named-templ-param "Named parameter" |
1058 ///function for setting DistMap type |
1132 ///for setting \ref DistMap object. |
1059 /// |
|
1060 template<class T> |
1133 template<class T> |
1061 BfsWizard<DefDistMapBase<T> > distMap(const T &t) |
1134 BfsWizard<DefDistMapBase<T> > distMap(const T &t) |
1062 { |
1135 { |
1063 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1136 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1064 return BfsWizard<DefDistMapBase<T> >(*this); |
1137 return BfsWizard<DefDistMapBase<T> >(*this); |
1065 } |
|
1066 |
|
1067 /// Sets the source node, from which the Bfs algorithm runs. |
|
1068 |
|
1069 /// Sets the source node, from which the Bfs algorithm runs. |
|
1070 /// \param s is the source node. |
|
1071 BfsWizard<TR> &source(Node s) |
|
1072 { |
|
1073 Base::_source=s; |
|
1074 return *this; |
|
1075 } |
1138 } |
1076 |
1139 |
1077 }; |
1140 }; |
1078 |
1141 |
1079 ///Function type interface for Bfs algorithm. |
1142 ///Function type interface for Bfs algorithm. |
1099 { |
1162 { |
1100 return BfsWizard<BfsWizardBase<GR> >(g,s); |
1163 return BfsWizard<BfsWizardBase<GR> >(g,s); |
1101 } |
1164 } |
1102 |
1165 |
1103 #ifdef DOXYGEN |
1166 #ifdef DOXYGEN |
1104 /// \brief Visitor class for bfs. |
1167 /// \brief Visitor class for BFS. |
1105 /// |
1168 /// |
1106 /// This class defines the interface of the BfsVisit events, and |
1169 /// This class defines the interface of the BfsVisit events, and |
1107 /// it could be the base of a real Visitor class. |
1170 /// it could be the base of a real visitor class. |
1108 template <typename _Digraph> |
1171 template <typename _Digraph> |
1109 struct BfsVisitor { |
1172 struct BfsVisitor { |
1110 typedef _Digraph Digraph; |
1173 typedef _Digraph Digraph; |
1111 typedef typename Digraph::Arc Arc; |
1174 typedef typename Digraph::Arc Arc; |
1112 typedef typename Digraph::Node Node; |
1175 typedef typename Digraph::Node Node; |
1113 /// \brief Called when the arc reach a node. |
1176 /// \brief Called for the source node(s) of the BFS. |
1114 /// |
1177 /// |
1115 /// It is called when the bfs find an arc which target is not |
1178 /// This function is called for the source node(s) of the BFS. |
1116 /// reached yet. |
1179 void start(const Node& node) {} |
|
1180 /// \brief Called when a node is reached first time. |
|
1181 /// |
|
1182 /// This function is called when a node is reached first time. |
|
1183 void reach(const Node& node) {} |
|
1184 /// \brief Called when a node is processed. |
|
1185 /// |
|
1186 /// This function is called when a node is processed. |
|
1187 void process(const Node& node) {} |
|
1188 /// \brief Called when an arc reaches a new node. |
|
1189 /// |
|
1190 /// This function is called when the BFS finds an arc whose target node |
|
1191 /// is not reached yet. |
1117 void discover(const Arc& arc) {} |
1192 void discover(const Arc& arc) {} |
1118 /// \brief Called when the node reached first time. |
1193 /// \brief Called when an arc is examined but its target node is |
1119 /// |
|
1120 /// It is Called when the node reached first time. |
|
1121 void reach(const Node& node) {} |
|
1122 /// \brief Called when the arc examined but target of the arc |
|
1123 /// already discovered. |
1194 /// already discovered. |
1124 /// |
1195 /// |
1125 /// It called when the arc examined but the target of the arc |
1196 /// This function is called when an arc is examined but its target node is |
1126 /// already discovered. |
1197 /// already discovered. |
1127 void examine(const Arc& arc) {} |
1198 void examine(const Arc& arc) {} |
1128 /// \brief Called for the source node of the bfs. |
|
1129 /// |
|
1130 /// It is called for the source node of the bfs. |
|
1131 void start(const Node& node) {} |
|
1132 /// \brief Called when the node processed. |
|
1133 /// |
|
1134 /// It is Called when the node processed. |
|
1135 void process(const Node& node) {} |
|
1136 }; |
1199 }; |
1137 #else |
1200 #else |
1138 template <typename _Digraph> |
1201 template <typename _Digraph> |
1139 struct BfsVisitor { |
1202 struct BfsVisitor { |
1140 typedef _Digraph Digraph; |
1203 typedef _Digraph Digraph; |
1141 typedef typename Digraph::Arc Arc; |
1204 typedef typename Digraph::Arc Arc; |
1142 typedef typename Digraph::Node Node; |
1205 typedef typename Digraph::Node Node; |
|
1206 void start(const Node&) {} |
|
1207 void reach(const Node&) {} |
|
1208 void process(const Node&) {} |
1143 void discover(const Arc&) {} |
1209 void discover(const Arc&) {} |
1144 void reach(const Node&) {} |
|
1145 void examine(const Arc&) {} |
1210 void examine(const Arc&) {} |
1146 void start(const Node&) {} |
|
1147 void process(const Node&) {} |
|
1148 |
1211 |
1149 template <typename _Visitor> |
1212 template <typename _Visitor> |
1150 struct Constraints { |
1213 struct Constraints { |
1151 void constraints() { |
1214 void constraints() { |
1152 Arc arc; |
1215 Arc arc; |
1153 Node node; |
1216 Node node; |
|
1217 visitor.start(node); |
|
1218 visitor.reach(node); |
|
1219 visitor.process(node); |
1154 visitor.discover(arc); |
1220 visitor.discover(arc); |
1155 visitor.reach(node); |
|
1156 visitor.examine(arc); |
1221 visitor.examine(arc); |
1157 visitor.start(node); |
|
1158 visitor.process(node); |
|
1159 } |
1222 } |
1160 _Visitor& visitor; |
1223 _Visitor& visitor; |
1161 }; |
1224 }; |
1162 }; |
1225 }; |
1163 #endif |
1226 #endif |
1164 |
1227 |
1165 /// \brief Default traits class of BfsVisit class. |
1228 /// \brief Default traits class of BfsVisit class. |
1166 /// |
1229 /// |
1167 /// Default traits class of BfsVisit class. |
1230 /// Default traits class of BfsVisit class. |
1168 /// \tparam _Digraph Digraph type. |
1231 /// \tparam _Digraph The type of the digraph the algorithm runs on. |
1169 template<class _Digraph> |
1232 template<class _Digraph> |
1170 struct BfsVisitDefaultTraits { |
1233 struct BfsVisitDefaultTraits { |
1171 |
1234 |
1172 /// \brief The digraph type the algorithm runs on. |
1235 /// \brief The type of the digraph the algorithm runs on. |
1173 typedef _Digraph Digraph; |
1236 typedef _Digraph Digraph; |
1174 |
1237 |
1175 /// \brief The type of the map that indicates which nodes are reached. |
1238 /// \brief The type of the map that indicates which nodes are reached. |
1176 /// |
1239 /// |
1177 /// The type of the map that indicates which nodes are reached. |
1240 /// The type of the map that indicates which nodes are reached. |
1178 /// It must meet the \ref concepts::WriteMap "WriteMap" concept. |
1241 /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. |
1179 /// \todo named parameter to set this type, function to read and write. |
|
1180 typedef typename Digraph::template NodeMap<bool> ReachedMap; |
1242 typedef typename Digraph::template NodeMap<bool> ReachedMap; |
1181 |
1243 |
1182 /// \brief Instantiates a ReachedMap. |
1244 /// \brief Instantiates a \ref ReachedMap. |
1183 /// |
1245 /// |
1184 /// This function instantiates a \ref ReachedMap. |
1246 /// This function instantiates a \ref ReachedMap. |
1185 /// \param digraph is the digraph, to which |
1247 /// \param digraph is the digraph, to which |
1186 /// we would like to define the \ref ReachedMap. |
1248 /// we would like to define the \ref ReachedMap. |
1187 static ReachedMap *createReachedMap(const Digraph &digraph) { |
1249 static ReachedMap *createReachedMap(const Digraph &digraph) { |
1462 } |
1529 } |
1463 } |
1530 } |
1464 return n; |
1531 return n; |
1465 } |
1532 } |
1466 |
1533 |
1467 /// \brief Next node to be processed. |
1534 /// \brief The next node to be processed. |
1468 /// |
1535 /// |
1469 /// Next node to be processed. |
1536 /// Returns the next node to be processed or \c INVALID if the queue |
1470 /// |
1537 /// is empty. |
1471 /// \return The next node to be processed or INVALID if the stack is |
1538 Node nextNode() const { |
1472 /// empty. |
|
1473 Node nextNode() { |
|
1474 return _list_front != _list_back ? _list[_list_front + 1] : INVALID; |
1539 return _list_front != _list_back ? _list[_list_front + 1] : INVALID; |
1475 } |
1540 } |
1476 |
1541 |
1477 /// \brief Returns \c false if there are nodes |
1542 /// \brief Returns \c false if there are nodes |
1478 /// to be processed in the queue |
1543 /// to be processed. |
1479 /// |
1544 /// |
1480 /// Returns \c false if there are nodes |
1545 /// Returns \c false if there are nodes |
1481 /// to be processed in the queue |
1546 /// to be processed in the queue. |
1482 bool emptyQueue() { return _list_front == _list_back; } |
1547 bool emptyQueue() const { return _list_front == _list_back; } |
1483 |
1548 |
1484 /// \brief Returns the number of the nodes to be processed. |
1549 /// \brief Returns the number of the nodes to be processed. |
1485 /// |
1550 /// |
1486 /// Returns the number of the nodes to be processed in the queue. |
1551 /// Returns the number of the nodes to be processed in the queue. |
1487 int queueSize() { return _list_back - _list_front; } |
1552 int queueSize() const { return _list_back - _list_front; } |
1488 |
1553 |
1489 /// \brief Executes the algorithm. |
1554 /// \brief Executes the algorithm. |
1490 /// |
1555 /// |
1491 /// Executes the algorithm. |
1556 /// Executes the algorithm. |
1492 /// |
1557 /// |
1493 /// \pre init() must be called and at least one node should be added |
1558 /// This method runs the %BFS algorithm from the root node(s) |
|
1559 /// in order to compute the shortest path to each node. |
|
1560 /// |
|
1561 /// The algorithm computes |
|
1562 /// - the shortest path tree (forest), |
|
1563 /// - the distance of each node from the root(s). |
|
1564 /// |
|
1565 /// \pre init() must be called and at least one root node should be added |
1494 /// with addSource() before using this function. |
1566 /// with addSource() before using this function. |
|
1567 /// |
|
1568 /// \note <tt>b.start()</tt> is just a shortcut of the following code. |
|
1569 /// \code |
|
1570 /// while ( !b.emptyQueue() ) { |
|
1571 /// b.processNextNode(); |
|
1572 /// } |
|
1573 /// \endcode |
1495 void start() { |
1574 void start() { |
1496 while ( !emptyQueue() ) processNextNode(); |
1575 while ( !emptyQueue() ) processNextNode(); |
1497 } |
1576 } |
1498 |
1577 |
1499 /// \brief Executes the algorithm until \c dest is reached. |
1578 /// \brief Executes the algorithm until the given target node is reached. |
1500 /// |
1579 /// |
1501 /// Executes the algorithm until \c dest is reached. |
1580 /// Executes the algorithm until the given target node is reached. |
1502 /// |
1581 /// |
1503 /// \pre init() must be called and at least one node should be added |
1582 /// This method runs the %BFS algorithm from the root node(s) |
1504 /// with addSource() before using this function. |
1583 /// in order to compute the shortest path to \c dest. |
|
1584 /// |
|
1585 /// The algorithm computes |
|
1586 /// - the shortest path to \c dest, |
|
1587 /// - the distance of \c dest from the root(s). |
|
1588 /// |
|
1589 /// \pre init() must be called and at least one root node should be |
|
1590 /// added with addSource() before using this function. |
|
1591 /// |
|
1592 /// \note <tt>b.start(t)</tt> is just a shortcut of the following code. |
|
1593 /// \code |
|
1594 /// bool reach = false; |
|
1595 /// while ( !b.emptyQueue() && !reach ) { |
|
1596 /// b.processNextNode(t, reach); |
|
1597 /// } |
|
1598 /// \endcode |
1505 void start(Node dest) { |
1599 void start(Node dest) { |
1506 bool reach = false; |
1600 bool reach = false; |
1507 while ( !emptyQueue() && !reach ) processNextNode(dest, reach); |
1601 while ( !emptyQueue() && !reach ) processNextNode(dest, reach); |
1508 } |
1602 } |
1509 |
1603 |
1510 /// \brief Executes the algorithm until a condition is met. |
1604 /// \brief Executes the algorithm until a condition is met. |
1511 /// |
1605 /// |
1512 /// Executes the algorithm until a condition is met. |
1606 /// Executes the algorithm until a condition is met. |
1513 /// |
1607 /// |
1514 /// \pre init() must be called and at least one node should be added |
1608 /// This method runs the %BFS algorithm from the root node(s) in |
1515 /// with addSource() before using this function. |
1609 /// order to compute the shortest path to a node \c v with |
1516 /// |
1610 /// <tt>nm[v]</tt> true, if such a node can be found. |
1517 ///\param nm must be a bool (or convertible) node map. The |
1611 /// |
1518 ///algorithm will stop when it reaches a node \c v with |
1612 /// \param nm must be a bool (or convertible) node map. The |
|
1613 /// algorithm will stop when it reaches a node \c v with |
1519 /// <tt>nm[v]</tt> true. |
1614 /// <tt>nm[v]</tt> true. |
1520 /// |
1615 /// |
1521 ///\return The reached node \c v with <tt>nm[v]</tt> true or |
1616 /// \return The reached node \c v with <tt>nm[v]</tt> true or |
1522 ///\c INVALID if no such node was found. |
1617 /// \c INVALID if no such node was found. |
|
1618 /// |
|
1619 /// \pre init() must be called and at least one root node should be |
|
1620 /// added with addSource() before using this function. |
|
1621 /// |
|
1622 /// \note <tt>b.start(nm)</tt> is just a shortcut of the following code. |
|
1623 /// \code |
|
1624 /// Node rnode = INVALID; |
|
1625 /// while ( !b.emptyQueue() && rnode == INVALID ) { |
|
1626 /// b.processNextNode(nm, rnode); |
|
1627 /// } |
|
1628 /// return rnode; |
|
1629 /// \endcode |
1523 template <typename NM> |
1630 template <typename NM> |
1524 Node start(const NM &nm) { |
1631 Node start(const NM &nm) { |
1525 Node rnode = INVALID; |
1632 Node rnode = INVALID; |
1526 while ( !emptyQueue() && rnode == INVALID ) { |
1633 while ( !emptyQueue() && rnode == INVALID ) { |
1527 processNextNode(nm, rnode); |
1634 processNextNode(nm, rnode); |
1528 } |
1635 } |
1529 return rnode; |
1636 return rnode; |
1530 } |
1637 } |
1531 |
1638 |
1532 /// \brief Runs %BFSVisit algorithm from node \c s. |
1639 /// \brief Runs the algorithm from the given node. |
1533 /// |
1640 /// |
1534 /// This method runs the %BFS algorithm from a root node \c s. |
1641 /// This method runs the %BFS algorithm from node \c s |
1535 /// \note b.run(s) is just a shortcut of the following code. |
1642 /// in order to compute the shortest path to each node. |
|
1643 /// |
|
1644 /// The algorithm computes |
|
1645 /// - the shortest path tree, |
|
1646 /// - the distance of each node from the root. |
|
1647 /// |
|
1648 /// \note <tt>b.run(s)</tt> is just a shortcut of the following code. |
1536 ///\code |
1649 ///\code |
1537 /// b.init(); |
1650 /// b.init(); |
1538 /// b.addSource(s); |
1651 /// b.addSource(s); |
1539 /// b.start(); |
1652 /// b.start(); |
1540 ///\endcode |
1653 ///\endcode |