gtl/tests/bellman_ford_test.cpp

0001 /* This software is distributed under the GNU Lesser General Public License */
0002 //==========================================================================
0003 //
0004 //   bellman_ford_test.cpp
0005 //
0006 //==========================================================================
0007 // $Id: bellman_ford_test.cpp,v 1.2 2002/11/07 13:38:37 raitner Exp $
0008
0009 #include <iostream>
0010
0011 #include <GTL/graph.h>
0012 #include <GTL/bellman_ford.h>
0013 #include <GTL/edge_map.h>
0014
0015 #ifdef __GTL_MSVCC
0016 #   ifdef _DEBUG
0017 #   define new DEBUG_NEW
0018 #   undef THIS_FILE
0019     static char THIS_FILE[] = __FILE__;
0020 #   endif   // _DEBUG
0021 #endif  // __GTL_MSVCC
0022
0023 int main (int argc, char* argv[])
0024 {
0025     graph G;
0026     G.make_directed();
0027     node n1 = G.new_node();
0028     node n2 = G.new_node();
0029     node n3 = G.new_node();
0030     node n4 = G.new_node();
0031     node n5 = G.new_node();
0032     node n6 = G.new_node();
0033
0034     edge e1_2 = G.new_edge(n1, n2);
0035     edge e2_3 = G.new_edge(n2, n3);
0036     edge e1_6 = G.new_edge(n1, n6);
0037     edge e3_6 = G.new_edge(n3, n6);
0038     edge e4_3 = G.new_edge(n4, n3);
0039     edge e6_4 = G.new_edge(n6, n4);
0040     edge e6_5 = G.new_edge(n6, n5);
0041     edge e5_4 = G.new_edge(n5, n4);
0042     edge e5_1 = G.new_edge(n5, n1);
0043
0044     edge_map<double> w(G);
0045     w[e1_2] = 1;
0046     w[e2_3] = 2;
0047     w[e1_6] = 8;
0048     w[e3_6] = 3;
0049     w[e4_3] = 2;
0050     w[e6_4] = 1;
0051     w[e6_5] = 3;
0052     w[e5_4] = 10;
0053     w[e5_1] = 2;
0054
0055     node_map<double> result(G);
0056     result[n1] = 0;
0057     result[n2] = 1;
0058     result[n3] = 3;
0059     result[n4] = 7;
0060     result[n5] = 9;
0061     result[n6] = 6;
0062
0063     node_map<node> preds(G);
0064     preds[n1] = node();
0065     preds[n2] = n1;
0066     preds[n3] = n2;
0067     preds[n4] = n6;
0068     preds[n5] = n6;
0069     preds[n6] = n3;
0070
0071     bellman_ford B;
0072     B.store_preds(true);
0073     B.source(n1);
0074     B.weights(w);
0075
0076     G.save("test.gml");
0077
0078     cout << "Bellman Ford with positive edge weights" << endl;
0079
0080     if (B.check(G) == algorithm::GTL_OK)
0081     {
0082     cout << "check OK" << endl;
0083     }
0084     else
0085     {
0086     cout << "check FAILED" << endl;
0087     exit(1);
0088     }
0089
0090     if (B.run(G) == algorithm::GTL_OK)
0091     {
0092     cout << "run OK" << endl;
0093     }
0094     else
0095     {
0096     cout << "run FAILED" << endl;
0097     exit(1);
0098     }
0099
0100     graph::node_iterator it, end;
0101
0102     for (it = G.nodes_begin(), end = G.nodes_end(); it != end; ++it)
0103     {
0104     if(result[*it] != B.distance(*it))
0105     {
0106         cout << "Distance for node " << *it << " FAILED" << endl;
0107         exit(1);
0108     }
0109     }
0110
0111     cout << "Distances OK" << endl;
0112
0113     for (it = G.nodes_begin(), end = G.nodes_end(); it != end; ++it)
0114     {
0115     if(preds[*it] != B.predecessor_node(*it))
0116     {
0117         cout << "Predecessor for node " << *it << " FAILED" << endl;
0118         exit(1);
0119     }
0120     }
0121
0122     cout << "Predecessors OK" << endl;
0123
0124     if (B.negative_cycle())
0125     {
0126     cout << "Negative Cycle FAILED" << endl;
0127     }
0128     else
0129     {
0130     cout << "Negative Cycle OK" << endl;
0131     }
0132
0133     //----------------------------------------------------------------------
0134     //   negative edge weights
0135     //----------------------------------------------------------------------
0136
0137     B.reset();
0138
0139     cout << "Bellman Ford with some negative edge weights" << endl;
0140
0141     w[e1_2] = 1;
0142     w[e2_3] = 2;
0143     w[e1_6] = -3;
0144     w[e3_6] = 3;
0145     w[e4_3] = 2;
0146     w[e6_4] = 1;
0147     w[e6_5] = 3;
0148     w[e5_4] = 10;
0149     w[e5_1] = 2;
0150
0151     B.weights(w);
0152
0153     result[n1] = 0;
0154     result[n2] = 1;
0155     result[n3] = 0;
0156     result[n4] = -2;
0157     result[n5] = 0;
0158     result[n6] = -3;
0159
0160     preds[n1] = node();
0161     preds[n2] = n1;
0162     preds[n3] = n4;
0163     preds[n4] = n6;
0164     preds[n5] = n6;
0165     preds[n6] = n1;
0166
0167      G.save("test2.gml");
0168
0169
0170     if (B.check(G) == algorithm::GTL_OK)
0171     {
0172     cout << "check OK" << endl;
0173     }
0174     else
0175     {
0176     cout << "check FAILED" << endl;
0177     exit(1);
0178     }
0179
0180     if (B.run(G) == algorithm::GTL_OK)
0181     {
0182     cout << "run OK" << endl;
0183     }
0184     else
0185     {
0186     cout << "run FAILED" << endl;
0187     exit(1);
0188     }
0189
0190     for (it = G.nodes_begin(), end = G.nodes_end(); it != end; ++it)
0191     {
0192     if(result[*it] != B.distance(*it))
0193     {
0194         cout << "Distance for node " << *it << " FAILED" << endl;
0195         exit(1);
0196     }
0197     }
0198
0199     cout << "Distances OK" << endl;
0200
0201     for (it = G.nodes_begin(), end = G.nodes_end(); it != end; ++it)
0202     {
0203     if(preds[*it] != B.predecessor_node(*it))
0204     {
0205         cout << "Predecessor for node " << *it << " FAILED" << endl;
0206         exit(1);
0207     }
0208     }
0209
0210     cout << "Predecessors OK" << endl;
0211
0212     if (B.negative_cycle())
0213     {
0214     cout << "Negative Cycle FAILED" << endl;
0215     }
0216     else
0217     {
0218     cout << "Negative Cycle OK" << endl;
0219     }
0220
0221     //----------------------------------------------------------------------
0222     //   negative cycle
0223     //----------------------------------------------------------------------
0224
0225     B.reset();
0226
0227     cout << "Bellman Ford with negative cycle" << endl;
0228
0229     w[e1_2] = 1;
0230     w[e2_3] = 2;
0231     w[e1_6] = -8;
0232     w[e3_6] = 3;
0233     w[e4_3] = 2;
0234     w[e6_4] = 1;
0235     w[e6_5] = 3;
0236     w[e5_4] = 10;
0237     w[e5_1] = 2;
0238
0239     B.weights(w);
0240
0241     if (B.check(G) == algorithm::GTL_OK)
0242     {
0243     cout << "check OK" << endl;
0244     }
0245     else
0246     {
0247     cout << "check FAILED" << endl;
0248     exit(1);
0249     }
0250
0251     if (B.run(G) == algorithm::GTL_OK)
0252     {
0253     cout << "run OK" << endl;
0254     }
0255     else
0256     {
0257     cout << "run FAILED" << endl;
0258     exit(1);
0259     }
0260
0261     if (B.negative_cycle())
0262     {
0263     cout << "Negative Cycle OK" << endl;
0264     }
0265     else
0266     {
0267     cout << "Negative Cycle FAILED" << endl;
0268     }
0269 }