Algorithm for getting currents and voltages from resistances in circuit as graph

Question

For my CS project I have to write simple circuit simulator, where I get list of edges of circuit as (a,R,b), where a and b are nodes at the end of the edge and R is it's resistance (it has a resistor R), and one pair (a,b) where the electromotive force E is put. I am also forbidden from using nodal analysis method.

I've tried reading "Computer methods for circuit analysis and design" by Vlach and Singhal, and also I've tried using loop analysis. The problem with loop analysis is that getting list of all loops for any graph (they can be arbitrarily huge, e. g. 1, 2, 4 thousand edges) is algorithmically very hard.

I also have to avoid getting overdetermined system of linear equations, so if I understand correctly I have to use both Kirchhoff's laws. Using them just as-is would generate too many equations though.

So to sum up: Ss there an algorithm that can produce equation system (not under- or overdetermined) for calculating currents and/or voltages in circuit without knowing it's shape beforehand, only resistances on it's edges and single EMF source?

Answer 1

Go for the loop analysis. It seems like you've done a bit of promising work on that.

You bring the "hugeness" of the problem as counterargument to that solution, but honestly:

You're overestimating complexity. We're talking about modern computers here – 4000 of anything is hardly "huge". And electrical circuits typically don't contain too many complete graphs of K>3, so the loop count usually doesn't explode. Still, your concern is valid; this problem can explode in a pathological circuit.

But, you might have gotten your loop analysis theory wrong:

You shouldn't even try to find all loops – you need to cover every component at least once in a loop, but as soon as you've done that, you're done.

So, a simple loop listing algorithm would take your graph,

• take an arbitrary first edge,
• find a small loop including that. Note it down in your loop list data structure.
• For all nodes in that loop, check whether the adjacent edges are already part of loops, if not, repeat the second&third step.

It turns into a pretty simple depth-first search over your tree. After that, you typically have either a loop-indexed list of edges, or a vertices-indexed list of loops, and you do your loop analysis based on either. It boils down to solving a system of linear equations – which a) can be solved without about any linear algebra library (LAPACK, if you're doing this in a programming language that I'd assume you do this, if you're worrying about computational performance rather than just getting it to work), or: Gauss Elimination (with pivotization) is actually something you should implement at least once in your life ;)

(And here's where I contradict your "algorithmically very hard" statement: the algorithms for all this are amazingly simple. Don't confuse algorithmically hard with computationally intense.)