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?

  • \$\begingroup\$ "would result in too many equations": Why? and, more importantly: What's "too many"? \$\endgroup\$ Mar 17 '19 at 9:45

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.)

  • \$\begingroup\$ I tried making modified algorithm for finding all cycles in graph, so I'd find all minimal cycles (loops), which would be much harder algorithmically, but of course you're right, it will be just a DFS. And also I got loop analysis wrong, it's really simple apparently. I have one more problem though - I only have resistances R and single voltage V (in EMF source edge), but the equation system is R*I=V, so to calculate currents I would need voltages in all edges, right? \$\endgroup\$
    – morgul
    Mar 17 '19 at 13:25
  • \$\begingroup\$ you're mixing algorithmically hard and computationally complex up again... \$\endgroup\$ Mar 17 '19 at 16:01
  • \$\begingroup\$ and you said you've been reading literature. If you need to learn what loop analysis does, I'd recommend asking a new question \$\endgroup\$ Mar 17 '19 at 16:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.