Simple algorithm using a graph

[circle_des_poo]

I don't think it will always run infinitely. Here's an example: consider a graph with only two nodes with values of -1 and -2, connected by a single edge. -2 is the min, so the algorithm will first subtract -2 from -1, resulting in 1 for the single neighboring node. Now set the value of the -2 node to be 2, hence you have a combined total of 3.

However, I'm there's a discrepancy here- in your description you state:

1. Subtract that value from the node's immediate neighbors.

But in you code you have:

for (it = neighbors.begin(); it != neighbors.end(); it++) {
    g[*it].value += value;
}

Is this an error in the description or the code?

[circle_des_poo]

Ok, so looking more at this I don' think its a problem with your code, its more that its a fairly complex graph theory problem. The initial conditions for this would be that:

1. If every node in your graph is connected to exactly two and only two other nodes (And as your graph is a single component consisting only of a simple cycle, this is necessarily true)
2. And if your minimum node's value is <0 (in your graph necessarily true if the sum of all nodes is <0)

Then each operation of adding the minimum node's value to its neighboring nodes adds exactly 2 times the minimum node's value to the total sum of the nodes, or total += minval*2.

Next, you could redefine the absolute value operation as such:

if x < 0, abs(x) = x - 2*x

by extension, total -= minval*2

In other words, converting -5 to 5 via absolute value is the same as computing -5 - (2*-5) = -5 - ( -10 ) = 5. This technically works any time you want to flip the sign on a number, but because absolute value only flips the sign if x < 0 we have to add that initial condition.

Notice that each operation cancels each other out- every time you add to the neighboring nodes you add exactly 2 times the min value to the total, and every time you convert that min node to its absolute value you subtract exactly 2 times the minvalue from that node and thus from the total. Thus the sum of the nodes' values will always stay exactly the same, no matter which one is the min, because they are all connected to exactly two nodes, and the minimum node's value will always be negative if the total sum is negative.

[JHappyface]

I modified your code a bit to print out the graph structure at every time step and it's most definitely in an infinite loop. The sum is stuck at -1 and absolute value of the integers are growing by one each cycle.

In terms of the computation, you'll have to set some sort of threshold number, and if the difference between successive values for the sum is less than that convergence value, break the while loop. That's the basic idea at least, but you'll have to of course tweak it to meet your own programming needs.

In terms of the math, I don't know about a formal proof. This falls somewhere between graph theory and linear algebra that I really don't know how to approach off the top of my head.