Search code examples
binary-search-treegraph-theory

Matrix Circuit Analysis using Algorithms

spsolve is then - sometimes - unable to find a solution.

Our teacher gave us test cases that we have to satisfy however I passed all of them but seems to fail the hidden test cases.

My code checks for the following: If they share a node and only those two resistors are connected then print SERIES else NEITHER. If their previous resistor is in series, then its is in SERIES (see test case no 2). If the resistor's ends are connected to the same nodes then print Parallel.

Can you suggest some inputs or any possible scenarios that a code wouldn't be able to answer correctly? or maybe a suggestion on what type of algorithm I should use for this problem

As I am performing nodal analysis, a singular matrix is expected since the position of the ground potential is generally not well-defined. However, before the update, a solution was found in 99% of the cases, maybe more. Now, I'm at 10% for large systems at best. I have not changed the algorithm and for a few tests, I have used identical code as before. Here is how I set up my calculation:

I generate a random three-dimensional network of resistors (I realize that I could accidentally create unsolvable networks but the percentages above should not change that drastically). The only SciPy/NumPy functions used here is np.random I create a sparse lil-matrix which I fill with conductance values extracted from my resistor network. I also create a solution vector which is not sparse. I convert the conductance matrix to csr-format and use the spsolve method. This is where my code lately fails.

Solution

  • Electron travel between Vdd and ground. The Dijkstra algorithm ( google it ) finds these routes. If two resisters are on the same route, they are in series.

    Setup

    • LOOP over every pair of resisters
      • IF the ends of the two resistor are connected to the same nodes - mark as parallel
    • Create adjacency list for resisters, combining parallels together into one edge.

    To check if R1 and R2 are in series:

    • IF R1 and R2 are marked parallel return PARALLEL
    • Use Dijkstra to find all routes from Vdd to R1
    • IF no route return NO
    • Use Dijkstra to find all route from R1 to GND
    • IF no route return NO
    • IF R2 itself, or as part of a parallel, on any routes found return SERIES

    Note that this will return YES for R3 and R4 in sample input 1. I do not understand why R3 and R4 are not in series - electricity will flow through R3 and then R4 to reach ground.

    Obviously, I do not understand your definition of "in series". Please provide this definition. In particular:

    R1 Vdd a
R2 a b
R3 a b
R4 b GND

    Are R1 and R4 in series or not?