## Wednesday, January 2, 2013

### Branch identification

The previous program was to find the number of nodes in the circuit. A node was defined as a junction of three or four nodes. The next step is to be able to identify the branches between these nodes.

The method I have used is a search routine that starts from a node and continues until another node has reached. This is because of one major constraint imposed on the spreadsheet. Connections have to be made either vertical or horizontal and can't be made diagonal. So if you need a diagonal connection you have to go along a column and then a row.

So when starting from a node, there are certain search directions depending on the number of branches at that node - if is a +, all four search directions (up, down, right and left) are possible while if it is a T junction, three search directions may be possible (for example, up, right and left).

If the next element in the search direction is not a node, there can be two directions of searching - forward or backward. To ensure forward search, check if the new element has already been encountered. If so, that is the wrong direction.

If the next element is a node, stop the search.

If it is not a node, but another new element, continue as above.

Another test circuit has been taken:

Anyway, here is the code:

And this is the result:
---------------------------------------------------------------------------------------------------------
************************************************************
[[0, 4], [0, 6], [2, 1], [2, 4], [5, 0], [5, 4], [5, 8], [7, 8], [8, 4]]
************************************************************
************************************************************
************************************************************
************************************************************
down
[[0, 4], [1, 4], [2, 4]]
**********************************************************************
right
[[0, 4], [0, 5], [0, 6]]
**********************************************************************
left
[[0, 4], [0, 3], [0, 2], [0, 1], [1, 1], [2, 1]]
**********************************************************************
down
[[0, 6], [1, 6], [2, 6], [2, 5], [2, 4]]
**********************************************************************
right
[[0, 6], [0, 7], [0, 8], [1, 8], [2, 8], [3, 8], [4, 8], [5, 8]]
**********************************************************************
left
[[0, 6], [0, 5], [0, 4]]
**********************************************************************
right
[[2, 1], [2, 2], [2, 3], [2, 4]]
**********************************************************************
up
[[2, 1], [1, 1], [0, 1], [0, 2], [0, 3], [0, 4]]
**********************************************************************
left
[[2, 1], [2, 0], [3, 0], [4, 0], [5, 0]]
**********************************************************************
down
[[2, 4], [3, 4], [4, 4], [5, 4]]
**********************************************************************
right
[[2, 4], [2, 5], [2, 6], [1, 6], [0, 6]]
**********************************************************************
up
[[2, 4], [1, 4], [0, 4]]
**********************************************************************
left
[[2, 4], [2, 3], [2, 2], [2, 1]]
**********************************************************************
down
[[5, 0], [6, 0], [7, 0], [8, 0], [8, 1], [8, 2], [8, 3], [8, 4]]
**********************************************************************
right
[[5, 0], [5, 1], [5, 2], [5, 3], [5, 4]]
**********************************************************************
up
[[5, 0], [4, 0], [3, 0], [2, 0], [2, 1]]
**********************************************************************
down
[[5, 4], [6, 4], [7, 4], [8, 4]]
**********************************************************************
right
[[5, 4], [5, 5], [5, 6], [5, 7], [5, 8]]
**********************************************************************
up
[[5, 4], [4, 4], [3, 4], [2, 4]]
**********************************************************************
left
[[5, 4], [5, 3], [5, 2], [5, 1], [5, 0]]
**********************************************************************
down
[[5, 8], [6, 8], [7, 8]]
**********************************************************************
up
[[5, 8], [4, 8], [3, 8], [2, 8], [1, 8], [0, 8], [0, 7], [0, 6]]
**********************************************************************
left
[[5, 8], [5, 7], [5, 6], [5, 5], [5, 4]]
**********************************************************************
down
[[7, 8], [8, 8], [9, 8], [10, 8], [10, 7], [10, 6], [10, 5], [10, 4], [9, 4], [8, 4]]
**********************************************************************
up
[[7, 8], [6, 8], [5, 8]]
**********************************************************************
left
[[7, 8], [7, 7], [7, 6], [8, 6], [8, 5], [8, 4]]
**********************************************************************
down
[[8, 4], [9, 4], [10, 4], [10, 5], [10, 6], [10, 7], [10, 8], [9, 8], [8, 8], [7, 8]]
**********************************************************************
right
[[8, 4], [8, 5], [8, 6], [7, 6], [7, 7], [7, 8]]
**********************************************************************
up
[[8, 4], [7, 4], [6, 4], [5, 4]]
**********************************************************************
left
[[8, 4], [8, 3], [8, 2], [8, 1], [8, 0], [7, 0], [6, 0], [5, 0]]
**********************************************************************

---------------------------------------------------------------------------------------------------------

Which is the correct result.

1. One thing I could do to speed up the result is take advantage of the symmetry of the matrix. If node 1 is connected to node 3, node 3 is connected to node 1. No need to do the search again. So I need to to do the search for node i and node k if k>i. Then just take the lower triangular part to be equal to the upper triangular part.

2. The diagonal elements are null. What will happen if there is a self loop - a loop originating and terminating at a node? But will something like that happen in practical electrical circuits?

More issues will be examined with other circuits. Probably will be at least two more versions of this code.

Here, I need to stop and comment about Python. The fact that an embedded objects are possible and that too of any dimension is fantastic. In the above code, we have an array with the elements being lists of lists! And add to that, the lists are not of the same length. Anything goes! Makes like a whole lot simpler.