gtl/src/bellman_ford.cpp

0001 /* This software is distributed under the GNU Lesser General Public License */
0002 //==========================================================================
0003 //
0004 //   bellman_ford.cpp
0005 //
0006 //==========================================================================
0007 // $Id: bellman_ford.cpp,v 1.4 2003/01/30 17:50:56 raitner Exp $
0008
0009 #include <GTL/bellman_ford.h>
0010
0011 #ifdef __GTL_MSVCC
0012 #   ifdef _DEBUG
0013 #   ifndef SEARCH_MEMORY_LEAKS_ENABLED
0014 #   error SEARCH NOT ENABLED
0015 #   endif
0016 #   define new DEBUG_NEW
0017 #   undef THIS_FILE
0018     static char THIS_FILE[] = __FILE__;
0019 #   endif   // _DEBUG
0020 #endif  // __GTL_MSVCC
0021
0022 __GTL_BEGIN_NAMESPACE
0023
0024 bellman_ford::bellman_ford()
0025 {
0026     vars_set = false;
0027     preds = 0;
0028 }
0029
0030 bellman_ford::~bellman_ford()
0031 {
0032     if (preds) delete preds;
0033 }
0034
0035 void bellman_ford::store_preds (bool set)
0036 {
0037     if (set && !preds) {
0038     preds = new node_map<edge>;
0039     } else if (!set && preds) {
0040     delete preds;
0041     preds = 0;
0042     }
0043 }
0044
0045
0046 int bellman_ford::check(graph& G)
0047 {
0048     if (!vars_set)
0049     {
0050     return algorithm::GTL_ERROR;
0051     }
0052
0053     if (G.nodes_begin() == G.nodes_end())
0054     {
0055     return algorithm::GTL_ERROR;
0056     }
0057
0058     return algorithm::GTL_OK;
0059 }
0060
0061 int bellman_ford::run(graph& G)
0062 {
0063     if (s == node())
0064     {
0065     s = *(G.nodes_begin());
0066     }
0067
0068     //----------------------------------------------------------------------
0069     //   initialize
0070     //----------------------------------------------------------------------
0071
0072     inf.init (G, true);
0073
0074     if (preds) {
0075     preds->init (G, edge());
0076     }
0077
0078     inf[s] = false;
0079     d[s] = 0;
0080     cycle = false;
0081
0082     //----------------------------------------------------------------------
0083     //   relax
0084     //----------------------------------------------------------------------
0085
0086     graph::edge_iterator it, end;
0087
0088     for (int i = 1; i < G.number_of_nodes(); ++i)
0089     {
0090     for (it = G.edges_begin(), end = G.edges_end(); it != end; ++it)
0091     {
0092             relax (*it, true);
0093
0094             if (G.is_undirected())
0095             {
0096                 relax(*it, false);
0097             }
0098     }
0099     }
0100
0101     //----------------------------------------------------------------------
0102     //   cycle detection
0103     //----------------------------------------------------------------------
0104
0105     for (it = G.edges_begin(), end = G.edges_end(); it != end; ++it)
0106     {
0107     node u = (*it).source();
0108     node v = (*it).target();
0109
0110     if(!inf[u] && !inf[v])
0111     {
0112         if (d[v] > d[u] + w[*it])
0113         {
0114         cycle = true;
0115         }
0116     }
0117     }
0118
0119     return algorithm::GTL_OK;
0120 }
0121
0122 void bellman_ford::reset()
0123 {
0124 }
0125
0126 void bellman_ford::relax(const edge& e, bool dir )
0127 {
0128     node u = e.source();
0129     node v = e.target();
0130
0131     if (!dir) {
0132         node tmp = u;
0133         u = v;
0134         v = tmp;
0135     }
0136
0137     if (!inf[u] && (inf[v] || (d[v] > d[u] + w[e])))
0138     {
0139     d[v] = d[u] + w[e];
0140     inf[v] = false;
0141
0142     if (preds)
0143     {
0144         (*preds)[v] = e;
0145     }
0146     }
0147 }
0148
0149
0150
0151 __GTL_END_NAMESPACE