Build an evaluator for nontrivial resistance diagrams

Question

There is already a problem on here about calculating the total resistance of a resistor diagram. However, that problem deals only with series-parallel diagrams, which are trivially reducible. Here I present the question that includes nontrivial bridges and the like, and uses a slightly more convenient representation.

Your task is to build a program that, given a graph where each edge has a value representing the resistance of a resistor between the vertices of that edge, will calculate the resistance between two specified vertices.

Your program will take input in two parts:

• The resistor graph. This can be in one of two forms, depending on which one is more convenient:

  • An N-by-N adjacency matrix, where N is the number of points in the resistor graph. The mth entry of the nth row is the resistance of the resistor between points m and n, in ohms. (The mth entry of the nth row and the nth entry of the mth row will always be equal.) The way this adjacency matrix is represented in data is your choice.

  • A number N, denoting the number of vertices in the graph, followed by a list of entries, each entry containing three numbers: p1, p2, and r, which are the numbers of the two points and the resistance of the resistor placed between those points. There will never be more than one resistor connecting two points. Again, the way this list is represented in data is your choice.

• Two numbers v1 and v2, representing the vertices between which the resistance is to be calculated.

All resistors will have a resistance of a positive integer of ohms. A value of 0 will refer to a resistor-less wire (i.e. zero resistance), and a value of -1 or infinity (you can choose which one to accept) will refer to the absence of a wire (i.e. infinite resistance).

Your program will return R, the resistance between v1 and v2 in ohms, as a floating-point number (to at least four significant digits). If the resistance is infinite, return either -1 or your language's representation of infinity.

Your solution must not make use of any libraries that are specifically built for solving linear equations or calculating the resistance of a resistor diagram.

Since any winning criteria I could come up with will take too long to judge properly (except for "first submitted code that actually works", but that one is unacceptable for obvious reasons), this will also be code golf. The shortest code in any language that can do the above will win. However, if you have an idea for a different winning criterion, I would be glad to hear it.

---

Example inputs

1. Series diagram

The following matrix:

-1  2 -1 -1
 2 -1  3 -1
-1  3 -1  4
-1 -1  4 -1

is a diagram representing resistors of 2 ohms, 3 ohms, and 4 ohms, put in series in that order. An input of 1 3 as the vertices would return 5.0, and an input of 1 4 would return 9.0.

2. Parallel diagram

The following matrix:

-1  0  0  0 -1
 0 -1 -1 -1  2
 0 -1 -1 -1  3
 0 -1 -1 -1  4
-1  2  3  4 -1

is a diagram representing resistors of 2 ohms, 3 ohms, and 4 ohms, put in parallel in that order. An input of 1 5 as the vertices would return 0.9230769230769231.

3. Infinite-resistance diagram

The following matrix:

-1  2 -1 -1
 2 -1 -1 -1
-1 -1 -1  4
-1 -1  4 -1

is a diagram representing two disconnected graphs of resistors. The input 1 2 would return 2.0, but the input 1 4 would return -1 or infinity, as there is no path between the vertices.

4. Zero-resistance diagram

The following matrix:

-1  0  0  0 -1
 0 -1 -1 -1  2
 0 -1 -1 -1  0
 0 -1 -1 -1  4
-1  2  0  4 -1

is a diagram representing resistors of 2 ohms and 4 ohms, and a plain wire, put in parallel. An input of 1 5 as the vertices would return 0.0, as there is a wire with zero resistance running from point 1 to point 5 via point 3.

5. Bridge

The following matrix:

-1  2  1 -1
 2 -1  3  5
 1  3 -1  4
-1  5  4 -1

represents the smallest diagram of resistors that cannot be represented as a series-parallel diagram for a specific set of points, namely 1 and 4. An input of 1 4 has a result of 2.9.

6. Cube

The following matrix:

-1  1  1 -1  1 -1 -1 -1
 1 -1 -1  1 -1  1 -1 -1
 1 -1 -1  1 -1 -1  1 -1
-1  1  1 -1 -1 -1 -1  1
 1 -1 -1 -1 -1  1  1 -1
-1  1 -1 -1  1 -1 -1  1
-1 -1  1 -1  1 -1 -1  1
-1 -1 -1  1 -1  1  1 -1

is a diagram representing a cube of one-ohm resistors. According to Wikipedia, the input 1 8 will return 0.8333333333333333.

Answer 1

J, 50 characters

(3 :'0 a}1 b}y+1e_5*c=:+/(-/~y)%r+1e_4')^:_[0
%a{c

Assumes the input is already stored in a set of global variables as:

• r is a 2D matrix of single-precision numbers
• a, b are 0-based indices of the two nodes

Usage:

r=:   _ 2 _ _
r=:r,.2 _ 3 _
r=:r,._ 3 _ 4
r=:r,._ _ 4 _

a=:0
b=:3

(3 :'0 a}1 b}y+1e_4*c=:+/(-/~y)%r+1e_3')^:_<./r
%a{c

Explanation:

• (3 :'...')^:_=/r - Repeat the explicit verb passed as a string until it converges (infinite power), starting with the scalar zero. It becomes a 1D array after the first iteration.
  • r+1e_4 - Add 100 μΩ parasitic resistance to each pair of resistor leads. We don't like wires. Lower values increase precision, but also limit the time step. If there are no wires, parasitic resistance is not needed.
  • (-/~y)% - Create the table of self-differences of the node voltage list (the table of voltage differences) (The table of self-differences of a scalar is a scalar zero). Divide this by the resistances. You get a list of resistor currents.
  • c=:+/ - Compute the sum of each column - the current flowing into each node - and tuck that away into a global variable.
  • y+1e_5* - Multiply that by the time step and add that to the node voltage of each node. The time step (divided by the parasitic capacitance of each node) must be lower than the lowest resistance, otherwise the simulation will not converge. Lower value = slower convergence. Without wires, we can increase this value to 1/2 and save three chars (and also speed up the convergence immensely). With wires, this won't converge at 1/2 Ω.
  • 0 a}1 b} - Pin the probe voltages to 0 volts and 1 volt respectively.
• %a{c - Take the current flowing into the ground, and return its inverse.