What algorithm do I use to calculate voltage across a combination circuit?

Question

I'm trying to programmatically calculate voltage changes over a very large circuit.

*This question may seem geared toward electronics, but it's more about applying an algorithm over a set of data.

To keep things simple,
here is a complete circuit, with the voltages already calculated:

I'm originally only given the battery voltage and the resistances:

The issue I have is that voltage is calculated differently among parallel and series circuits.
A somewhat similar question asked on SO.

Some formulas:

When resistors are in parallel:
Rtotal = 1/(1/R1 + 1/R2 + 1/R3 ... + 1/Rn)

When resistors are in series:
Rtotal = R1 + R2 + R3 ... + Rn

Ohm's Law:

V = IR
I = V/R
R = V/I

V is voltage (volts)
I is current (amps)
R is resistance(ohms)

Every tutorial I've found on the internet consists of people conceptually grouping together parallel circuits to get the total resistance, and then using that resistance to calculate the resistance in series.

This is fine for small examples, but it's difficult to derive an algorithm out of it for large scale circuits.

My question:
Given a matrix of all complete paths,
is there a way for me to calculate all the voltage drops?

I currently have the system as a graph data structure.
All of the nodes are represented(and can be looked up by) an id number.

So for the example above, if I run the traversals, I'll get back a list of paths like this:

[[0,1,2,4,0]
,[0,1,3,4,0]]

Each number can be used to derive the actual node and it's corresponding data. What kind of transformations/algorithms do I need to perform on this set of data?

---

It's very likely that portions of the circuit will be compound, and those compound sections may find themselves being in parallel or series with other compound sections.

I think my problem is akin to this:
http://en.wikipedia.org/wiki/Series-parallel_partial_order

Dele

Is your circuit compound of parallel or series? or it can contain bridge circuit? – Waers

You may want to look up Kirchhoff's law: en.wikipedia.org/wiki/Kirchhoff%27s_circuit_laws it can be used to derive a set of linear equations to solve. – Bartko

@PhamTrung Good question. No bridges. Purely parallel and series. – Dele

look here https://mcmap.net/q/1318853/-how-to-implement-kirchoff-rules/2521214 – Deservedly

How big are your large scale circuits? Are you talking thousands, millions or billions of resistors? Have you looked into using recursion to break down your circuit into smaller, more manageable pieces? – Fjeld

Answer 1

Some circuits cannot even be analyzed in terms of series and parallel, for example a circuit which includes the edges of a cube (there's some code at the bottom of that web page that might be helpful; I haven't looked at it). Another example that can't be analyzed into series/parallel is a pentagon/pentagram shape.

A more robust solution than thinking about series and parallel is to use Kirchhoff's laws.

1. You need to make variables for the currents in each linear section of the circuit.
2. Apply Kirchhoff's current law (KCL) to nodes where linear sections meet.
3. Apply Kirchhoff's voltage law (KVL) to as many cycles as you can find.
4. Use Gaussian elimination to solve the resulting linear system of equations.

The tricky part is identifying cycles. In the example you give, there are three cycles: through battery and left resistor, battery and right resistor, and through left and right resistors. For planar circuits it's not too hard to find a complete set of cycles; for three dimensional circuits, it can be hard.

You don't actually need all the cycles. In the above example, two would be enough (corresponding to the two bounded regions into which the circuit divides the plane). Then you have three variables (currents in three linear parts of the circuit) and three equations (sum of currents at the top node where three linear segments meet, and voltage drops around two cycles). That is enough to solve the system for currents by Gaussian elimination, then you can calculate voltages from the currents.

If you throw in too many equations (e.g., currents at both nodes in your example, and voltages over three cycles instead of two), things will still work out: Gaussian elimination will just eliminate the redundancies and you'll still get the unique, correct answer. The real problem is if you have too few equations. For example, if you use KCL on the two nodes in your example and KVL around just one cycle, you'll have three equations, but one is redundant, so you'll only really have two independent equations, which is not enough. So I would say throw in every equation you can find and let Gaussian elimination sort it out.

And hopefully you can restrict to planar circuits, for which it is easy to find a nice set of cycles. Otherwise you'll need a graph cycle enumeration algorithm. I'm sure you can find one if you need it.

Disturb

A few links that can help to understand provided algorithm: circuitanalyser.com/circuit-analysis-theory | youtube.com/watch?v=sqxzQkAdJm0 – Asquith

Answer 2

use a maximum flow algorithm (Dijkstra is your friend).

http://www.cs.princeton.edu/courses/archive/spr04/cos226/lectures/maxflow.4up.pdf

You pretend to be in front of a water flow problem (well, actually it IS a flow problem). You have to compute the flow of water on each segment (the current). Then you can easily compute the voltage drop (water pressure) across every resistor.

Syllable

this is not true, maxflow algorithm is different because there is no voltage drop considered across the vertices so capacities of edges are fixed but in electrical circuit the capacities of edge changes with voltage drop. conductance by itself doesn't define the capacity of a edge but along with voltage drop it can give you exact flow in the edge. Can you give a reduction and prove that it is same as max flow problem? – Lugar

Answer 3

I think the way to go here would be something like this:

1. Sort all your paths into groups of the same length.
2. While there are more than one group, choose the group with the largest length and:
   2a. Find two paths with one item difference.
   2b. "Merge" them into a path with the length smaller by one - the merge is dependent on the actual items that are different.
   2c. Add the new path into the relevant group.
   2d. If there are only paths with more than one item difference, merge the different items so that you have only one different item between the paths.
   2e. When there is only one item left, find an item from a "lower" (= length is smaller) with minimum differences, and merge item to match.
3. When there is one group left with more than one item, keep doing #2 until there is one group left with one item.
4. Calculate the value of that item directly.

This is very initial, but I think the main idea is clear.
Any improvements are welcome.

Mowry