Talk:Resistor mesh

From Rosetta Code

After finishing this task you can move on to this. --Mwn3d 15:59, 21 August 2011 (UTC)

Heh that would have been easy had it not included the squirrel. By the way, do you know what's up with the SVG display? I've been trying to get it to work with no success. --Ledrug 16:26, 21 August 2011 (UTC)
FWIW I have had problems in the past with SVG files that contain text elements not displaying properly. A workaround is to convert the text to curves. It is apparently a problem with the sites SVG renderer. --Thundergnat 19:58, 21 August 2011 (UTC)
Eh that worked, great. --Ledrug 22:51, 21 August 2011 (UTC)
The arena in that link looks like somewhere where you'd plug in the special component from Explorers. Ah, an opportunity for a clever pop-culture reference missed… –Donal Fellows 19:37, 21 August 2011 (UTC)

Link to a solution[edit]

Anyone? --Paddy3118 06:34, 28 August 2011 (UTC)

Link to a what? A number? --Ledrug 03:22, 29 August 2011 (UTC)

I was hoping for something other than 42 ;-) Maybe a link to something with an algorithm and its explanation? Thanks. --Paddy3118 07:26, 29 August 2011 (UTC)

A long, long time ago, I took the class that taught how to do this. I don't really remember, now. Not the most helpful of links; it teaches more theory than solving this task ought to require. --Michael Mol 11:44, 29 August 2011 (UTC)
The general idea is this: given a circuit and some input, what's the response of the system? For this particular problem, the input is two voltage values on nodes A and B, and the response is the voltage values on every other node. By Ohm's law, if two neighoring nodes have voltages and , then the current flowing from i to j is where R is the resistance (=1 here). Given a set of voltages on the nodes, you can calculate net current flow out of each node; to be a valid solution, the total current out of each node must be zero unless the node is an electrode (i.e. given a fixed voltage as part of boundary condition). The C code gives A 1 volt and B -1 volt, calculates what voltage each other node has, then calculates the current I flowing out of A and into B (they must be equal); the resistance is again given by Ohm's law: R = 2/I.
Of course the interesting part is how to get the voltage values, and there are multiple ways to do it. The C code just give the circuit some arbitrary values initially, then at each iteration calculates how much voltage difference is needed on each node to locally sastisfy the current flow constraint on that node, and adds it onto the voltage. For this task it converges and pretty quickly at that. --Ledrug 15:45, 29 August 2011 (UTC)
Given the problem size, even Gauss pivoting will do. Now, for a larger circuit, you would simply use a sparse symmetric solver, and there are many good ones already written. Maybe conjugate gradient would be a nice starting point. See also Maxima solution for an exact value. At least it will help checking other methods ;-) Capra Hircus 11:11, 28 August 2012 (UTC)
The exact solver gives 455859137025721/283319837425200, or approximately 1.60899124 Ohm. I now added this problem to examples page. The solver uses repetitive star-mesh transform, and it can list all steps that it took. In this case it takes over a 1000 steps - certainly not something you'd want to do by hand. --Kirr (talk) 11:45, 14 November 2016 (UTC)
That exact result matches the result indicated by three implementations here (J, Maxima, Python), so presumably your implementation is correct. That said, I see a problems with your solver that incline me to remove your link from this talk page: Your implementation is hosted server side, which means your code is not comparable with the implementations here (which defeats the purpose of this site). I think, if you want us to leave this link here, you should at least provide the implementation details of the solver part of your system which corresponds to this task. (The graphical representation part and web interface parts are not related to this task, however, so - in the context of this particular link - I don't see that we should care about them here.) --Rdm (talk) 15:25, 14 November 2016 (UTC)
Well, the OP was asking for a solution, so I thought I could contribute. Other than the exact answer, my tool prints a step by step solution, which, although bulky, should be easy to understand. As far as I can see, this method is not used by any implementation here, so perhaps it could be of some interest, even if just for comparison and reference. As for implementation, I'm happy to provide any details. It's really simple: Any two-terminal resistor network can be simplified to equivalent single resistor using star-mesh transform. Each transform eliminates one node, so the network gradually shrinks, until only terminal nodes remain. A star-mesh transform may add some resistors in parallel with already existing ones - such parallel resistors should be merged before doing the next star-mesh transform. One possibly interesting part here is representation of resistances. In my case I use GMP's rationals in order to do exact calculation. You're correct to point out that my source is not open at the moment. I actually intend to open the source at some point, but I want to do some tuning and clean up before that. (My current source is not really good for didactic use anyway: It's C, tuned for performance, verbose, and full of interface and debugging code - not a compact textbook example to learn from). However the method that I use is so trivial that I believe anyone with minimal knowledge of programming should be able to re-implement it without much trouble. I made it as a toy after nerd-sniping myself, and I am happy to share and discuss this topic with anyone interested. However feel free to remove the link and this discussion if you don't see it as a positive contribution to this topic, page, or the whole site. Also please let me know if I need to post more about implementation, I'll be glad to discuss in any detail. --Kirr (talk) 01:36, 15 November 2016 (UTC)