Add a find_negative_cycle algo based on Bellman-Ford

[oxarbitrage]

Had been using a custom extension of the bellman_ford algorithm from this library in order to find paths of negative cycles in directed graphs. I decided to give it a shot and try to introduce it as a library algo.

Motivation

• Matlab's shortestpath function do return negative cycles path (even if they do it as an error string).
• There are at least 2 use cases for this where the most obvious one seems to be arbitrage.

Details

The new algorithm is the first of 2 presented on this paper: https://blogs.asarkar.com/assets/docs/algorithms-curated/Negative-Weight%20Cycle%20Algorithms%20-%20Huang.pdf

As the find_negative_cycle algo introduced here is the same as the bellman-ford for the first part i moved steps 1 and 2 form the original into a common function that both algorithms can use.

I am unsure if this PR haves enough quality to be included but i also don't know if it haves the enough use cases and acceptance (#195) to be considered as part of the library so i preferred to post it as it is and see what happens.

If it not get included i hope some people could find it useful.

[ABorgna]

Hi. This algorithm was definitely missing, thanks for the contribution!

Do you think you could add some benchmarks for bellman_ford and find_negative_cycle ?
Something akin to benches/floyd_warshall.rs.

Also, it would be a good idea now to move the two algorithms to a separate algo/bellman_ford.rs.

[oxarbitrage]

@ABorgna how do i run the benchmarks?

$ cargo +nightly bench
   Compiling petgraph v0.5.1 (/home/oxarbitrage/petgraph/find_negative_cycle/petgraph)
error[E0277]: the trait bound `petgraph::prelude::StableGraph<u32, u32>: serde::ser::Serialize` is not satisfied
   --> benches/serialize.rs:41:38
    |
41  |     bench.iter(|| bincode::serialize(&graph).unwrap());
    |                                      ^^^^^^ the trait `serde::ser::Serialize` is not implemented for `petgraph::prelude::StableGraph<u32, u32>`
    | 
   ::: /home/oxarbitrage/.cargo/registry/src/github.com-1ecc6299db9ec823/bincode-1.3.3/src/lib.rs:108:8
    |
108 |     T: serde::Serialize,
    |        ---------------- required by this bound in `bincode::serialize`

error[E0277]: the trait bound `petgraph::prelude::StableGraph<u32, u32>: serde::ser::Serialize` is not satisfied
   --> benches/serialize.rs:47:35
    |
47  |     let data = bincode::serialize(&graph).unwrap();
    |                                   ^^^^^^ the trait `serde::ser::Serialize` is not implemented for `petgraph::prelude::StableGraph<u32, u32>`
    | 
   ::: /home/oxarbitrage/.cargo/registry/src/github.com-1ecc6299db9ec823/bincode-1.3.3/src/lib.rs:108:8
    |
108 |     T: serde::Serialize,
    |        ---------------- required by this bound in `bincode::serialize`

error[E0277]: the trait bound `petgraph::prelude::StableGraph<u32, u32>: serde::de::Deserialize<'_>` is not satisfied
   --> benches/serialize.rs:49:45
    |
49  |         let graph2: StableGraph<u32, u32> = bincode::deserialize(&data).unwrap();
    |                                             ^^^^^^^^^^^^^^^^^^^^ the trait `serde::de::Deserialize<'_>` is not implemented for `petgraph::prelude::StableGraph<u32, u32>`
    | 
   ::: /home/oxarbitrage/.cargo/registry/src/github.com-1ecc6299db9ec823/bincode-1.3.3/src/lib.rs:179:8
    |
179 |     T: serde::de::Deserialize<'a>,
    |        -------------------------- required by this bound in `bincode::deserialize`

error: aborting due to 3 previous errors

For more information about this error, try `rustc --explain E0277`.
error: could not compile `petgraph`

To learn more, run the command again with --verbose.
$ 

[ABorgna]

Seems #395 broke the benchmarks. Let me fix it on master.

[ABorgna]

@oxarbitrage I won't be able to make the fix until later today, but adding the --all-features flag should work.

[ABorgna]

I cherry picked your benchmarks in master, and seems there is a bit of a performance hit with the separation :/

 name                base ns/iter  with_negloop ns/iter  diff ns/iter  diff %  speedup
 bellman_ford_bench  27,127        37,843                      10,716  39.50%   x 0.72

Try #[inline]ing the initialize_relax function.

Btw, I fixed the benchmark compilation in #435.

[oxarbitrage]

Right, the inline seems to work and i was able to see numbers around 37,000 using the old (all in one) and in the new (separated) functions.

The find_negative_cycle_bench seems to be taking a bit longer (i was not able to see numbers below 38,500), probably caused by the linear search, a fix we can try is #434 (comment)

[ABorgna]

Following #434 (comment),
I saw the benchmarks didn't have negative edge weights, so the relaxation step always terminated early in |V| steps and find_negative_cycle never found any.
I changed the benchmarks a bit so now it never terminates early, and the difference between the base bellman_ford implementation became negligible (the new one was 0.5% faster).

Also, 54a3e25 didn't remove the extra node in the path for the case 2 so I fixed it.

[ABorgna]

I think this is ready to merge, if you are happy with the changes.
Thanks again for the work :)

[oxarbitrage]

It looks great, thank you for the last changes :)