-1
$\begingroup$

Trying to test Johnson’s algorithm with over 100 vertices but it doesn’t work if there is a negative cycle. So I’m trying to write code to construct graphs with some negative weights (about 10% of the edges) that have NO negative cycles (so that I can test the efficiency of Johnson’s algorithm).

I’m having trouble trying to piecemeal together these graphs. So I really should first try to understand what conditions create negative cycles (beyond having at least one negative edge), but having trouble finding any info in the literature.

Any insights or even reference suggestions are appreciated. Thank you!

$\endgroup$
6
  • $\begingroup$ "So I really should first try to understand what conditions create negative cycles" - is that your question essentially? If so, the answer is the definition of the negative cycle - a cycle with negative sum of all weights $\endgroup$
    – Sgg8
    Commented May 11 at 23:47
  • $\begingroup$ That only states what a negative cycle IS. I don’t know what conditions make one. I’m aware that there needs to be at least one negative edge, but that in itself isn’t sufficient to guarantee a negative cycle. $\endgroup$
    – Bark Jr. Jr.
    Commented May 12 at 0:00
  • $\begingroup$ And to be specific, I’m trying to use this knowledge to create a graph that DOESN’T have a negative cycle. So perhaps I should have asked about that more specifically… $\endgroup$
    – Bark Jr. Jr.
    Commented May 12 at 0:13
  • $\begingroup$ Are you looking for an algorithm to generate a graph that has no negative cycle? If so, take a graph with all weights positive. Otherwise, specify the exact problem, please $\endgroup$
    – Sgg8
    Commented May 12 at 15:44
  • $\begingroup$ I stated the exact problem above: I am trying to create a directed graph with negative edges that has no negative cycles. Sorry, I thought I was clear about that, but I suppose the title is written differently (because I wanted to construct the algorithm myself, but at this point, I'll take help with that!). $\endgroup$
    – Bark Jr. Jr.
    Commented May 13 at 16:29

1 Answer 1

Reset to default
1
$\begingroup$

You can, for example, do the following:

  1. Generate a random graph with like $10$-$11$% negative edges.

  2. Find all cycles in your graph. (This is a standard problem, easily googlable).

For each cycle $G_i = (w_i, V_i, E_i)$:

  1. Find $\text{sum}(G_i)= \sum_{e \in E_i} w_i(e)$, which is the sum of weights in a cyle
  2. If $\text{sum}(G_i) < 0$: add $|\text{sum}(G_i)|$ or $|\text{sum}(G_i) + \text{whatever_positive_value_you_want}|$ to the weight of an arbitrary edge on that cycle.

That will fix all the negative cycles. Since the number of negative cycles can be exponential, the algorithm above is asymptotically optimal

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .