What algorithm can I use to distribute energy between connected nodes?

Question

I'm creating a game where every user has a network of connected nodes that each have a specific amount of energy. The nodes will try to distribute energy evenly amongst themselves. If a node has more energy than the average, it should deliver to the network. If a node has less than the average, it should receive from the network. An example network would be this, where + means more than average and - means less than average:

Now the one question I've been trying to solve for a while now: how can I calculate the cumulative amount of energy that flows through every edge until all nodes have the same amount of energy? For example we know that the node in the top left will in the end distribute 7 energy to the network, but will it give 5 down and 2 to the right? Or something else?

Is there any algorithm we could use to solve that problem? Could we potentially represent this problem as an electric circuit and solve it like that?

Answer 1

There are many ways we could choose which paths the energy will take, so here are a couple of starting points we could try.

1. Spanning Tree

This approach is inspired by dielectric breakdown, the phenomenon where a large potential difference across an insulator will drill a branching tree of conductive channels through it - lightning is the most familiar example.

We start by giving each edge a score based on the energy difference between its endpoints - we can consider this a measure of how "ionized" this edge is, and how eagerly energy will flow along it.

Next we run a minimum spanning tree algorithm on our graph, using the negative absolute value of this ionization score as our edge weight. Prim's algorithm or Kruskal's will both do great. This gives us a subset of our edges forming a tree that touches every node, which will become our energy distribution network.

Now you can pick a root of the tree arbitrarily, and work through the edges starting from the leaf nodes. Total-up the deviation from the average energy value in each subtree. The amount flowing down (leafward) along the subtree's incoming edge must be the negative of this value.

eg. if I have a leaf node with -1 energy difference from the average, then 1 unit of energy must flow down the edge leading to it.

If its parent has +2 deviation and a second child node with +1 deviation, then the parent's incoming edge must carry 2 energy back toward the root: -1 * (-1 + 2 + 1) = -2

2. System of Equations

Treating the amount of energy carried along each (oriented) edge as a variable, we can construct a system of linear equations, with one equation per node:

  [Node's deviation from average]
+ [sum of incoming edge variables]
- [sum of outgoing edge variables]
= 0

Here's how that system of equations might look for the example graph:

This system will usually be under-determined, since you'll have more edges (variables) than nodes (equations/constraints), meaning you'll have multiple solutions to choose from - unless of course your graph is a tree, in which case we can use the rule above to find the single unique solution.

The nice thing about this approach is it makes the problem pretty generic - something you can chuck at a general linear system solver library (or integer programming solver, if you want to enforce a constraint that each edge carry a whole number of charges).

By playing with the solver objective function, you can search the solution space for options that spread the load as evenly as possible over all paths, as opposed to the spanning tree approach which necessarily concentrates the flow along a minimal transport network.

Answer 2

It looks like I cannot determine the exact solution directly. What I created in the end is an iterative algorithm that approximates a natural distribution.

Code can be found here:

• Core algorithm: https://github.com/willemmulder/Energia/blob/master/static/js/core.js
• Running example: https://willemmulder.github.io/Energia/energyDistribution.html

---

Roughly it runs like this:

Step 1

For the whole set of nodes, find all the disconnected subgraphs, i.e. find all separate networks.

Step 2

For every separate network, calculate the average energy position. In the example that average energy position is 0. Then calculate what every node should be delivering to the network or receiving from the network. Those are the +7, -2 etc that we see in the example image.

Step 3

We prepare a list of nodes that we want to process. This list initially contains all the nodes that want to distribute any energy to the network.

Then, the algorithm runs for a specific number of rounds. Every round

1. It will loop over the prepared list and distribute any 'surplus' energy to the connected nodes. These connected nodes store the incoming energy into an 'incoming energy' bucket just for now.
2. The algorithm loops over all nodes and adds all incoming energy for that node together and sets that as the surplus energy to distribute next round.

So after e.g. 50 rounds, the energy from a specific node has hopped over 50 nodes and distributed itself to quite a big network.

To keep things efficient, I use a few tricks

1. If there is less than 1 energy to distribute for a node, it will remove itself from the list of nodes that we want to process. This because we don't want to distribute ever smaller amounts of energy around the network. A node will be added back to the list again if any incoming energy for that node moves it surplus energy > 1.
2. If a node has only 1 connected node, then we know exactly how much energy will transfer between them. For example node A has +3 and connects only to node B. Then we know that A will transfer all that energy to node B, no matter what. So we confirm that energy distribution between those nodes and remove node A from the list to be processed. Even better, if that one connection becomes confirmed, that might mean that node B might be left with only one connection to a node C, which can then be confirmed as well, etc.
3. If the list of nodes to be processed is 0, then obviously break.

The algorithm seems fast enough right now (1-2 ms for a few not-so-complicated networks).

Any suggestions much appreciated!

Again, full code can be found here: https://github.com/willemmulder/Energia/blob/master/static/js/core.js