## Monday, January 7, 2013

### Loop identification

Moving on from branch identification (for the time being at least), I now take on the task of identifying the loops. Which actually is a little tricky.

Anyway, pasting what all the branches that have been identified look like as an matrix on a spreadsheet:

Its a pretty huge spreadsheet, so can only capture a small part of it as a snapshot. But this is just the matrix "branch_map" computed in the previous blog pasted into cells of a spreadsheet.

For any circuit, the number of independent loops is equal to (B-N+1) where B is the number of branches, N is the number of nodes. The length of "node_list" will give us N and the number of elements (non-null) in the upper triangular part of branch_matrix will give us B. This can be found by this simple block of code:
---------------------------------------------------------------------------------------------------------
number_of_branches=0
for c1 in range(len(node_list)):
for c2 in range(c1+1, len(node_list)):
for parallel_branches in branch_map[c1][c2]:
number_of_branches+=1
print number_of_branches
---------------------------------------------------------------------------------------------------------

So we can now set the number of loops we are expecting to find.

A basic starting idea on how to get loops.

1. Take the branch_map matrix and start from the first element in the upper triangular part.
2. The way nodes have been determined, this will be the uppermost row in the connected circuit of the input csv file. Nodes will then be in later columns of the same row and then in later rows. So esentially moving left to right and then down and then again left to right.
3. So by moving to the right from the first element (say element [0, 1] which is [0 5] ;[0 6] ;[0 7] ;[0 8]), we encounter element [0,2] which is [0 5] ;[0 4] ;[0 3] ;[0 2] ;[0 1] ;[1 1] ;[2 1].
4. Element [0,1] contains the branch which connects node [0, 5] to [0, 8]. Element [0,2] contains the branch which connects node [0, 5] to [2,1].
5. Since, we are on row 0 of branch_map, the common element in node 0 which is [0,5].
6. So, if we traverse element [0, 1] in the reverse direction and element [0, 2] in the forwarsd direction, we are moving from right to left and then down.
7. Now, in an attempt to complete the loop, we move down from element [0, 2]. The first non-empty element encountered is [1,2].
8. This is [0 8] ;[1 8] ;[2 8] ;[2 2] ;[2 1].
9. This connects node [2, 1] to [0, 8] through the the "jump1" jump label. And this essentially completes a loop because [0,8] was where we started.

10. Repeating this sequence gives some very good results on other loops.
11. [0 5] ;[0 6] ;[0 7] ;[0 8] in element [0, 1] in reverse direction and move right
[0 5] ;[1 5] ;[2 5] ;[3 5] ;[4 5] ;[5 5] ;[6 5] in forward direction and then move down.
[6 3] ;[6 4] ;[6 5] in the reverse direction and then move left
[6 3] ;[6 2] ;[6 1] ;[6 0] in the forward direction and then move up
[2 1] ;[2 0] ;[3 0] ;[4 0] ;[5 0] ;[6 0] in the reverse direction and then move left
[2 1] ;[2 2] ;[2 8] ;[1 8] ;[0 8] in the forward direction and the loop ends.

So this seems to be an algorithm! Need to code it. But still need to keep thinking about loopholes.