include/GTL/bid_dijkstra.h

0001 /* This software is distributed under the GNU Lesser General Public License */
0002 //==========================================================================
0003 //
0004 //   bid_dijkstra.h
0005 //
0006 //==========================================================================
0007 // $Id: bid_dijkstra.h,v 1.3 2003/03/24 15:58:54 raitner Exp $
0008
0009 #ifndef GTL_BID_DIJKSTRA_H
0010 #define GTL_BID_DIJKSTRA_H
0011
0012 #include <GTL/GTL.h>
0013 #include <GTL/graph.h>
0014 #include <GTL/node_map.h>
0015 #include <GTL/edge_map.h>
0016 #include <GTL/algorithm.h>
0017
0018 __GTL_BEGIN_NAMESPACE
0019
0020 /**
0021  * $Date: 2003/03/24 15:58:54 $
0022  * $Revision: 1.3 $
0023  *
0024  * @brief Dijkstra's Algorithm for computing a shortest path from a single
0025  * source to a single target.
0026  *
0027  * This class implements Dijkstra's algorithm in a bidirectional manner for
0028  * computing a shortest path from a single source to a single target in
0029  * \f$\mathcal{O}((|V| + |E|) log |V|)\f$ worst case.
0030  *
0031  * @sa dijkstra
0032  * @sa bellman_ford
0033  *
0034  * @author Christian Bachmaier chris@infosun.fmi.uni-passau.de
0035  */
0036 class GTL_EXTERN bid_dijkstra : public algorithm
0037 {
0038 public:
0039     /**
0040      * @brief Iterator type for traversing %nodes on one shortest path.
0041      */
0042     typedef list<node>::const_iterator shortest_path_node_iterator;
0043
0044     /**
0045      * @brief Iterator type for traversing %edges on one shortest path.
0046      */
0047     typedef list<edge>::const_iterator shortest_path_edge_iterator;
0048
0049     /**
0050      * @internal
0051      */
0052     enum node_color {white, grey, black};
0053
0054     /**
0055      * @brief Default constructor.
0056      *
0057      * Enables only the calculation of shortest paths.
0058      *
0059      * @sa algorithm::algorithm
0060      */
0061     bid_dijkstra();
0062
0063     /**
0064      * @brief Destructor.
0065      *
0066      * @sa algorithm::~algorithm
0067      */
0068     virtual ~bid_dijkstra();
0069
0070     /**
0071      * @brief Sets source and target %node.
0072      *
0073      * Must be executed every time before check and run of this %algorithm.
0074      *
0075      * @param s source %node
0076      * @param t target %node
0077      */
0078     void source_target(const node& s, const node& t);
0079
0080     /**
0081      * @brief Sets weights of the edges.
0082      *
0083      * This method @b must be called before check and run.
0084      *
0085      * @param weight weights of the %edges
0086      */
0087     void weights(const edge_map<double>& weight);
0088
0089     /**
0090      * @brief Enables or disables the storing of the shortest path.
0091      *
0092      * If enabled for every %node and edge on the shortest path from source
0093      * to target will be stored.
0094      *
0095      * @param set true if path should be stored
0096      *
0097      * @sa dijkstra::predecessor_node
0098      * @sa dijkstra::predecessor_edge
0099      */
0100     void store_path(bool set);
0101
0102     /**
0103      * @brief Checks whether the preconditions for bidirectional Dijkstra are
0104      * satisfied.
0105      *
0106      * The Precondition are that the weights of the edges have been set and
0107      * that the graph has at least one %node. Additionally all %edge weights
0108      * must be \f$\ge 0\f$ and and source and target %nodes must be found in
0109      * @p G.
0110      *
0111      * @param G graph
0112      *
0113      * @retval algorithm::GTL_OK if %algorithm can be applied
0114      * @retval algorithm::GTL_ERROR otherwise
0115      *
0116      * @sa dijkstra::source
0117      * @sa dijkstra::weigths
0118      * @sa algorithm::check
0119      */
0120     virtual int check(graph& G);
0121
0122     /**
0123      * @brief Runs shortest path algorithm on @p G.
0124      *
0125      * This should return always algorithm::GTL_OK. The return value only
0126      * tracks errors that might occur.
0127      * Afterwards the result of the test can be accessed via access methods.
0128      *
0129      * @param G graph
0130      *
0131      * @retval algorithm::GTL_OK on success
0132      * @retval algorithm::GTL_ERROR otherwise
0133      *
0134      * @sa algorithm::run
0135      */
0136     int run(graph& G);
0137
0138     /**
0139      * @brief Returns source %node.
0140      *
0141      * @return source %node
0142      */
0143     node source() const;
0144
0145     /**
0146      * @brief Returns target %node if set, <code>node::node()</code> else.
0147      *
0148      * @return target %node
0149      */
0150     node target() const;
0151
0152     /**
0153      * @brief Returns whether the storing of the shortest path is enabled.
0154      *
0155      * @return @c true iff the storing of path is enabled.
0156      *
0157      * @sa dijkstra::predecessor
0158      */
0159     bool store_path() const;
0160
0161     /**
0162      * @brief Returns whether target is reachable from source.
0163      *
0164      * @return @c true iff target was reached from source
0165      */
0166     bool reached() const;
0167
0168     /**
0169      * @brief Returns the distance from source %node to target %node.
0170      *
0171      * @return distance if target is bid_dijkstra::reached, <code>-1.0</code>
0172      * else
0173      */
0174     double distance() const;
0175
0176     /**
0177      * @brief Returns an iterator to the beginning (to the source %node) of
0178      * the shortest %node path to target %node.
0179      *
0180      * @return beginning %node iterator of the shortest path
0181      *
0182      * @sa bid_dijkstra::store_path
0183      *
0184      * @note The method requires that path calculation option was
0185      * enabled during last run.
0186      */
0187     shortest_path_node_iterator shortest_path_nodes_begin();
0188
0189     /**
0190      * @brief Returns an iterator one after the end (one after target
0191      * %node) of the shortest %node path to target %node.
0192      *
0193      * @return shortest path end %node iterator
0194      *
0195      * @sa bid_dijkstra::store_path
0196      *
0197      * @note The method requires that path calculation option was
0198      * enabled during last run.
0199      */
0200     shortest_path_node_iterator shortest_path_nodes_end();
0201
0202     /**
0203      * @brief Returns an iterator to the beginning %edge of the shortest
0204      * %edge path to target %node.
0205      *
0206      * @sa bid_dijkstra::store_path
0207      *
0208      * @return beginning %edge iterator of the shortest path
0209      *
0210      * @note The method requires that path calculation option was
0211      * enabled during last run.
0212      */
0213     shortest_path_edge_iterator shortest_path_edges_begin();
0214
0215     /**
0216      * @brief Returns an iterator one after the end of a shortest %edge path
0217      * to target %node.
0218      *
0219      * @sa bid_dijkstra::store_path
0220      *
0221      * @return shortest path end %edge iterator
0222      *
0223      * @note The method requires that predecessor calculation option was
0224      * enabled during last run.
0225      */
0226     shortest_path_edge_iterator shortest_path_edges_end();
0227
0228     /**
0229      * @brief Resets Dijkstra's bidirectional algorithm.
0230      *
0231      * It prepares the algorithm to be applied again, possibly to another
0232      * graph.
0233      *
0234      * @note The weights are not reset. You can apply this algorithms
0235      *
0236      * @sa algorithm::reset
0237      */
0238     virtual void reset();
0239 private:
0240     /**
0241      * @internal
0242      * Stores source.
0243      *
0244      * @sa bid_dijkstra::source.
0245      */
0246     node s;
0247
0248     /**
0249      * @internal
0250      * Stores target.
0251      *
0252      * @sa bid_dijkstra::source.
0253      */
0254     node t;
0255
0256     /**
0257      * @internal
0258      * Indicates whether weights were set.
0259      *
0260      * @sa bid_dijkstra::weights.
0261      */
0262     bool weights_set;
0263
0264     /**
0265      * @internal
0266      * Indicates whether predecessors should be computed.
0267      *
0268      * @sa bid_dijkstra::store_preds.
0269      */
0270     bool path_set;
0271
0272     /**
0273      * @internal
0274      * Stores the weights of the %edges.
0275      *
0276      * @sa bid_dijkstra::weights.
0277      */
0278     edge_map<double> weight;
0279
0280     /**
0281      * @internal
0282      * Stores distance between @s and @t.
0283      * (default: -1.0)
0284      */
0285     double dist;
0286
0287     /**
0288      * @internal
0289      * Stores if @a t can be reached from @s.
0290      * (default: false)
0291      */
0292     bool reached_t;
0293
0294     /**
0295      * @internal
0296      * Stores predecessor of each %node in shortest path.
0297      * (default: edge() (if enabled))
0298      */
0299     node_map<edge> pred;
0300
0301     /**
0302      * @internal
0303      * Stores successor of each %node in shortest path tree.
0304      * (default: edge() (if enabled))
0305      */
0306     node_map<edge> succ;
0307
0308     /**
0309      * @internal
0310      * Indicates the current %node status.
0311      * (default: black)
0312      */
0313     node_map<int> source_mark;
0314
0315     /**
0316      * @internal
0317      * Indicates the current %node status.
0318      * (default: black)
0319      */
0320     node_map<int> target_mark;
0321
0322     /**
0323      * @internal
0324      * Distance from source @a s.
0325      * (default: -1.0)
0326      */
0327     node_map<double> source_dist;
0328
0329     /**
0330      * @internal
0331      * Distance to target @a t.
0332      * (default: -1.0)
0333      */
0334     node_map<double> target_dist;
0335
0336     /**
0337      * @internal
0338      * Stores for target %node @a t a list of nodes on the shortest path
0339      * from source @a s to it.
0340      * (default: empty)
0341      *
0342      * @sa dijkstra::shortest_path_nodes_begin
0343      * @sa dijkstra::shortest_path_nodes_end
0344      */
0345     list<node> shortest_path_node_list;
0346
0347     /**
0348      * @internal
0349      * Stores for target %node @a t a list of edges on the shortest path
0350      * from source @a s to it.
0351      * (default: empty)
0352      *
0353      * @sa dijkstra::shortest_path_edges_begin
0354      * @sa dijkstra::shortest_path_edges_end
0355      */
0356     list<edge> shortest_path_edge_list;
0357
0358     /**
0359      * @internal
0360      * Prepares the %algorithm to be applied once again.
0361      */
0362     void reset_algorithm();
0363
0364     /**
0365      * @internal
0366      * Inits data structure.
0367      */
0368     void init(graph& G);
0369
0370     /**
0371      * @internal
0372      * Fills ordered lists @a shortest_path_node_list and @a
0373      * shortest_path_edge_list with nodes respective edges of shortest path
0374      * from @a s to @a t. Calculates distance.
0375      *
0376      * @param n first white node of the two directions
0377      */
0378     void fill_node_edge_lists(const node& n);
0379 };
0380
0381 __GTL_END_NAMESPACE
0382
0383 #endif // GTL_BID_DIJKSTRA_H
0384
0385 //--------------------------------------------------------------------------
0386 //   end of file
0387 //--------------------------------------------------------------------------