3

Summation of the edge weights in negative cycles is negative. With this concept, is there any method to generate graphs with random positive and negative edge weight, and without negative cycle? Such graphs are useful for testing the bellman_ford_shortest_paths method.

Note: In this post they generate graph without those conditions with boost library.

Community
  • 1
  • 1
moksef
  • 344
  • 1
  • 5
  • 17

1 Answers1

2

I'd suggest using generate_random_graph to ... generate a random graph and fix any negative cycles as a post-processing step.

E.g.:

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/random.hpp>
#include <random>
#include <iostream>

using Graph = boost::adjacency_list<
    boost::vecS,
    boost::vecS,
    boost::directedS, 
    boost::no_property,
    boost::property<boost::edge_weight_t, double> >;

int main()
{
    std::mt19937 prng;
    Graph g;
    generate_random_graph(g, 100, 200, prng);

    // find cycles with negative sum and just add a large enough value to one
    // of the participating edges to make it postive
}
sehe
  • 374,641
  • 47
  • 450
  • 633
  • thanks. would you complete your answer (`comment` parts) with [this post](http://stackoverflow.com/questions/2839908/find-all-cycles-in-graph-redux). – moksef Mar 12 '16 at 15:51
  • I'd prefer if you tried that (it's the right approach). I don't have a lot of time (I just posted the skeleton because it seemed much simpler than the thing you linked to in the question). If you get stuck, you can post a new question about that and I'll surely find it. – sehe Mar 12 '16 at 15:53