include/GTL/bellman_ford.h

0001 /* This software is distributed under the GNU Lesser General Public License */
0002 //==========================================================================
0003 //
0004 //   bellman_ford.h
0005 //
0006 //==========================================================================
0007 // $Id: bellman_ford.h,v 1.5 2003/03/24 15:58:54 raitner Exp $
0008
0009 #ifndef GTL_BELLMAN_FORD_H
0010 #define GTL_BELLMAN_FORD_H
0011
0012 #include <GTL/GTL.h>
0013 #include <GTL/algorithm.h>
0014 #include <GTL/node_map.h>
0015 #include <GTL/edge_map.h>
0016
0017 __GTL_BEGIN_NAMESPACE
0018
0019
0020 /**
0021  * $Date: 2003/03/24 15:58:54 $
0022  * $Revision: 1.5 $
0023  *
0024  * @brief Bellman Ford %algorithm.
0025  *
0026  * Implementation of the single source shortest path due to
0027  * Bellman and Ford. Unlike Dijkstra's SSSP %algorithm this one
0028  * allows negative edge weights, as long as there are no cycles
0029  * with negative weight. If there are negative cycles this
0030  * implementation finds them.
0031  */
0032
0033 class GTL_EXTERN bellman_ford : public algorithm
0034 {
0035 public:
0036
0037     /**
0038      * @brief Constructor.
0039      */
0040     bellman_ford();
0041
0042     /**
0043      * @brief Destructor.
0044      */
0045     virtual ~bellman_ford();
0046
0047     /**
0048      * @brief Checks whether the preconditions for Bellman Ford
0049      * are satisfied.
0050      *
0051      * The Precondition are that the weights of the edges
0052      * have been set and that the graph has at least one node.
0053      *
0054      * @param G graph.
0055      * @retval algorithm::GTL_OK if %algorithm can be applied
0056      * @retval algorithm::GTL_ERROR otherwise.
0057      */
0058     int check (graph& G);
0059
0060     int run (graph& G);
0061
0062     /**
0063      * @brief Resets the algorithm.
0064      *
0065      * The weights are not reset. You can apply this algorithms
0066      * twice without setting the weights for the second call.
0067      */
0068     void reset ();
0069
0070     /**
0071      * @brief Sets source.
0072      *
0073      * The default source is the invalid %node (node::node()),
0074      * in this case an arbitrary %node is chosen and stored when
0075      * this algorithm is run.
0076      *
0077      * @param n source.
0078      */
0079     void source (const node& n) {s = n;}
0080
0081     /**
0082      * @brief Returns source.
0083      *
0084      * @return source.
0085      */
0086     node source () const {return s;}
0087
0088     /**
0089      * @brief Sets weights of the edges.
0090      *
0091      * This method @b must be called before run.
0092      *
0093      * @param w weights of the edges.
0094      */
0095     void weights (const edge_map<double>& weight) {w = weight; vars_set = true; }
0096
0097     /**
0098      * @brief Enables or disables the storing of predecessors.
0099      *
0100      * If enabled for every %node the predecessor on the shortest
0101      * path from will be stored.
0102      *
0103      * @param set if true predecessors will be stored.
0104      * @sa bellman_ford::predecessor_node,
0105      * bellman_ford::predecessor_edge
0106      */
0107     void store_preds (bool set);
0108
0109     /**
0110      * @brief Returns whether the storing of predecessors is enabled.
0111      *
0112      * @retval true iff the storing of predecessors is enabled.
0113      *
0114      * @sa bellman_ford::predecessor_node,
0115      * bellman_ford::predecessor_edge
0116      */
0117     bool store_preds () const {return preds != 0;}
0118
0119     /**
0120      * @brief Returns whether is reachable from source.
0121      *
0122      * @param n node
0123      */
0124     bool reached (const node& n) const {return !inf[n];}
0125
0126     /**
0127      * @brief Returns the distance from source to @a n
0128      *
0129      * @param n node
0130      */
0131     double distance (const node& n) const {return d[n];}
0132
0133     /**
0134      * @brief edge to predecessor of %node @a n on the shortest
0135      * path from source
0136      *
0137      * If @a n is a root or wasn't reached the return value is
0138      * the invalid %edge edge::edge().
0139      *
0140      * @em Please @em note that this requires that this option
0141      * was enabled during last run.
0142      *
0143      * @param n node.
0144      * @return predecessor of @a n.
0145      * @sa bellman_ford::store_preds
0146      */
0147     edge predecessor_edge (const node& n) const
0148     {assert (preds); return (*preds)[n];}
0149
0150     /**
0151      * @brief predecessor of %node @a n on the shortest
0152      * path from source
0153      *
0154      * If @a n is a root or wasn't reached the return value is
0155      * the invalid %node node::node().
0156      *
0157      * @em Please @em note that this requires that this option
0158      * was enabled during last run.
0159      *
0160      * @param n node.
0161      * @return predecessor of @a n.
0162      * @sa bellman_ford::store_preds
0163      */
0164     node predecessor_node (const node& n) const
0165     {edge e = predecessor_edge(n); return e == edge() ? node() : e.opposite(n); }
0166
0167     /**
0168      * @brief Returns whether there is a cycle with negative
0169      * weight.
0170      */
0171     bool negative_cycle() const
0172     {return cycle;}
0173
0174 private:
0175
0176
0177     /**
0178      * @brief Main method for Bellman Ford
0179      *
0180      * @param e edge to be relaxed
0181      */
0182     void relax (const edge& e, bool dir);
0183
0184     /**
0185      * @brief Stores source.
0186      *
0187      * @sa bellman_ford::source.
0188      */
0189     node s;
0190
0191     /**
0192      * @brief Stores the weights of the edges.
0193      *
0194      * @sa bellman_ford::weights.
0195      */
0196     edge_map<double> w;
0197
0198     /**
0199      * @brief Indicates whether weights were set.
0200      *
0201      * @sa bellman_ford::weights.
0202      */
0203     bool vars_set;
0204
0205     /**
0206      * @brief distance from source s.
0207      *
0208      * @sa bellman_ford::distance.
0209      */
0210     node_map<double> d;
0211
0212     /**
0213      * @brief Indicates whether the node has distance infinity
0214      *
0215      * @sa bellman_ford::distance.
0216      */
0217     node_map<bool> inf;
0218
0219     /**
0220      * @brief Stores father of each %node (if enabled)
0221      *
0222      * @sa bellman_ford::store_preds
0223      */
0224     node_map<edge>* preds;
0225
0226     /**
0227      * @brief Indicates whether there is a cycle with negative
0228      * weight
0229      *
0230      * @sa bellman_ford::negative_cycle.
0231      */
0232     bool cycle;
0233 };
0234
0235 __GTL_END_NAMESPACE
0236
0237 #endif // GTL_BELLMAN_FORD_H