include/GTL/dijkstra.h

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