Unless @TodorSimeonov comes up with something great, I've sort of given up to 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:
Roughly it runs like this:
For the whole set of nodes, find all the disconnected subgraphs, i.e. find all separate networks.
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.
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
- 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.
- 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
- 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.
- 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.
- 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 still much appreciated!
Again, full code can be found here: https://github.com/willemmulder/Energia/blob/master/static/js/core.js