algorithmsimulationgraph-theoryphysics# Electric circuit with redundancies (power distribution) simulation

I need to simulate at basic level an electric circuit with redundancies, for example like this:

We have two generators, a couple of power distributors and the devices. I am trying to simulate the electric current on each branch, starting from device power requirements (e.g., Device 1 need 5 Ampere, Device 2 15, Device 3 ..., )

My trial was by implementing a simple graph:

- We start from the last-level children and they ask their parent the current they need to work
- Each parent check if it received request from each children, if not just wait
- All other parents sum up the current requested from each child and will ask to its own parent
- Do this until we have no parents anymore Now we distribute the power:
- last set of parents from algorithm above are the power supply (generators in this case)
- each power supply knows how much current it was asked, it simply split it available power (or current) proportionally to each child (it may be enough or even not if overloaded, that's fine)
- each child do the same until we reach the bottom

Now the problem which brought me to a stop: Some devices (power distributors) can take power from multiple parents. In such a case the normal solution would be to split the power request evenly among parents BUT, if one of the parent cannot provide it (smaller generator or supplying to much devices) than the distributor will ask more to the other parent(s). It seems to me impossible to know it in advance if this is the case, since the above algorithm need to be run fully to know if a generator is overloaded or not, and to do that I must select in advance if the distributor will ask to its parents 50/50 or 30/70 or ... .

The only solution I could think of is iterative: applying the algorithm once with a 50/50. If one generator can pro provide just let's say 30% I take note of that and simulate again, asking for 70% to the other one, fine. Maybe not... the other generator now cannot provide enough power to the other distributor so I have to simulate again changing the 50/50 percentage of the other distributor as well. I am afraid this can be overcomplicated and that the algorithm will never converge to a good result. I never faced this kind of problems and after many days sleeping over it I still cannot find the best solution. I would like to avoid bad practices and using good software design. Does anyone has a common solution for this kind of problem to point me to?

Thank you everyone

PS: Language is not a problem (it's an algorithm issue) but if relevant I'm writing it in C++

Solution

This is a flow problem.

Here is the algorithm to calculate the flow problem:

Find a path from a source to a destination, using the Dijkstra algorithm

Find minimum capacity of any link on the path

Reduce capacity of all links on path by minimum capacity

Remove any link that now has zero capacity

Repeat above steps until no more paths can be found.

To make this work you will need to:

set the capacity of an output links from each generator to the maximum power it can generate

connect the generator output link to an additional node that splits the flow to the different devices and distributors that are connected to the generator

set the capacity of the input links to the devices to be the power demand of the devices.

connect an output link from each device to an additional node that acts as a common sink

set the capacity of all links that have not been specified by the above steps to a very large number, greater than any total flow expected, so that they do not limit the flow in any way.

Here is some C++ code that implements this https://github.com/JamesBremner/PathFinder/blob/7b98a412398e1aea8934a8002822e1ccef9b888a/src/GraphTheory.cpp#L755-L859. The documentation for this is at https://github.com/JamesBremner/PathFinder/wiki/Flows and the complete application at https://github.com/JamesBremner/PathFinder

Here is your problem specified in the format expected by the PathFinder application

```
format multiflows
g 1 0
l gen1 gen1split 100
l gen1split dev1 5
l gen1split dist1 1000
l gen1split dist2 1000
l gen2 gen2split 100
l gen2split dist1 1000
l gen2split dist2 1000
l dist1 dev2 15
l dist1 dev3 3
l dist2 dev4 4
l dist2 dev5 5
l dist2 dev6 6
l dev1 sink 1000
l dev2 sink 1000
l dev3 sink 1000
l dev4 sink 1000
l dev5 sink 1000
l dev6 sink 1000
s gen1
s gen2
e sink
```

The code linked to above only works correctly for a single source ( generator ). Here is the code to calculate the flow from multiple sources

```
double multiflows(sGraphData &gd)
{
// total flow on each link from all sources
std::vector<int> vMultiFlow(gd.g.edgeCount());
// flow on each link from current source
std::vector<int> vEdgeFlow(gd.g.edgeCount());
// working copy of graph
sGraphData work = gd;
// loop over sources
for (auto &s : gd.multiStart)
{
// reduce link capacities by flow from previous generator
for (int k = 0; k < vEdgeFlow.size(); k++)
work.edgeWeight[k] -= vEdgeFlow[k];
// calculate flow from this generator
vEdgeFlow.clear();
work.startName = s;
flows(
work,
vEdgeFlow);
// add to total flow
for (int k = 0; k < vEdgeFlow.size(); k++)
vMultiFlow[k] += vEdgeFlow[k];
}
// display total flow through each link
for (int k = 0; k < vMultiFlow.size(); k++)
{
std::cout << gd.g.userName(gd.g.src(k))
<< " -> " << gd.g.userName(gd.g.dest(k))
<< " " << vMultiFlow[k] << "\n";
}
return 0;
}
```

For your problem, the output is

```
gen1 -> gen1split 20
gen1split -> dev1 5
gen1split -> dist1 3
gen1split -> dist2 12
gen2 -> gen2split 18
gen2split -> dist1 15
gen2split -> dist2 3
dist1 -> dev2 15
dist1 -> dev3 3
dist2 -> dev4 4
dist2 -> dev5 5
dist2 -> dev6 6
dev1 -> sink 5
dev2 -> sink 15
dev3 -> sink 3
dev4 -> sink 4
dev5 -> sink 5
dev6 -> sink 6
```

- How to generate uniformly distributed subintervals of an interval?
- Generating random number in a non-power-of-2 range from random bits
- Algorithm - Search and Replace a string
- Looking for a branchless algorithm for converting a specific set of 4-bit integers
- Different results for XIRR between Excel and ExcelFinancialFunctions 3.2.0
- Find four,whose sum equals to target
- A* algorithm can't find the goal in Python
- Efficiently getting all divisors of a given number
- Are there any existed API to split IEnumerable<T> to many Vector<T> in CSharp？
- Generating all divisors of a number given its prime factorization
- Efficient way to insert a number into a sorted array of numbers?
- BFS Maximize Minimum Distance from a Monster along a path
- Is there effective algorithm that will return all different combination?
- Big O of algorithm that steps over array recursively
- Modification of Dijkstra's algorithm to make it work with negative weights and its time complexity
- Traversing/Moving over an unfolded cube
- Fibonacci Recursion using Golden Ratio(Golden Number)
- Karatsuba implementation in C
- Why is O(n) better than O( nlog(n) )?
- What is Sliding Window Algorithm? Examples?
- How to write a function to navigate through a non-binary tree?
- Evenly distribute QDate values into certain number of slots
- Find max product using divide and conqure in O(n) time
- Cache-friendly sqare matrix transposition logic issue
- Why doesn't Dijkstra's algorithm work for negative weight edges?
- Fast Convertion From Adjacency List to Edge List
- I convert ASCII words into numbers but am stuck trying to decode them. How to convert 1=a, 2=b, 28=ab etc? (psudeocode okay)
- Reversing the word order in a string in place
- Trying to make a 2x2 rubik's cube solving algorithm , how do i find the solution path (DFS)?
- question about missing element in array