Loop identification - XIII

The concept involved in determining loops.

1. branch_map is the array that contains every branch as a list of elements between nodes. The diagonal elements are null because it is assumed that self-loops do not exist. The non-diagonal elements are branched between nodes. So branch_map[i][j] is the branch between node i and node j.

2. branch_map can have multiple lists because there can be parallel branches between two nodes.

3. Every row must have at least three elements because that is how a node is defined - a node is an element from which three or four branches connect it to another node.

4. The number of independent loops = Branches - Nodes +1.

So this is how I find the loops:

1. Pick the first non-null element in the first row.
2. The first loop in progress will be this element.
3. The direction of searching will be horizontal or "horiz". This means we search in the same row for other branches. All searches will be from the first column to last column of a row.
4. For every element in the row, check for parallel branches and add them to loop_list.
5. If not a parallel branch, check if that element or the inverse of it (i.e if [i, j] is the element, [j, i] will also be the same) has been encountered before. If so, then loop is not valid and stop updating that particular list. If not a repeat, append that element to the list.
6. For every element found, create a new list and add it to the elements already in the list. This means, the lists will keep growing in number and size.
7. Check is the loop has ended. This means, are one of the end nodes of the latest branch the same as the end node of the first branch in the loop.
8. If so, take this list and check if the nodes in the branches of the list have been encountered before. That is make a copy of node_list (loop_nodes) and keep deleting the nodes which are found. So it a node in the list exists in loop_nodes, this means the node has not been encountered. A loop which passes through a new nodes is definitely an independent loop, so add this loop to the main loop_list.
9. If the loop does not pass through a new node, it could still be an independent loop. So check if the loop is the same as the loops already found and in loop_list.
10. If so, this means the loop is different from the loops in loop_list. So this may or may not be an independent loop. Add it to loop_list anyway.
11. This completed once cycle. Change the direction of search to vertical or "vert".
12. Check if loop_nodes is null or if number of loops found is less than B-N+1. If either or both are true, continue checking.
13. Take the last element of every loop in progress and look in the columns of those elements starting from first row to last row. Repeat 4-10. Change direction of search again.


The problem is that this method often throws up a number of loops greater than B-N+1 which means some of them will be redundant. This is particularly the case when tightly interconnected circuits are examined. The examples in the next post will make things clear.