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, whereN
is the number of points in the resistor graph. Them
th entry of then
th row is the resistance of the resistor between pointsm
andn
, in ohms. (Them
th entry of then
th row and then
th entry of them
th 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
, andr
, 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
andv2
, 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
.