Loop identification - II

This part actually turned out a whole lot trickier than I thought it would. I figured the best way to go about is by a two step process: first identify the route every loop must take and then actually build the loop.

So, this is the first part - identifying the loop.

To begin with, here is the entire code (including node and branch identification):

	#! /usr/bin/env python
	import sys, math, matrix
	new_file = open("testckt2.csv","r")
	# This matrix will read the .csv file
	# The .csv file will contain the string "wire" where a zero impedance direct connection exists.
	# Where no connection nor device (resitor, inductor etc) exists, a '' will be found.
	# The devices will be strings. Maybe later will be actual object constructor calls.
	conn_matrix=[]
	for line in new_file:
	conn_matrix.append(line.split(","))
	conn_rows=len(conn_matrix)
	conn_columns=len(conn_matrix[0])
	# Remove any leading or trailing quotes and also carriage returns (\n) that may have been added while generating the csv file.
	for c1 in range(0, conn_rows):
	for c2 in range(0, conn_columns):
	if conn_matrix[c1][c2]:
	if "\n" in conn_matrix[c1][c2]:
	conn_matrix[c1][c2]=conn_matrix[c1][c2][:-1]
	if conn_matrix[c1][c2]:
	while (conn_matrix[c1][c2][0]=='"' or conn_matrix[c1][c2][0]=="'"):
	conn_matrix[c1][c2]=conn_matrix[c1][c2][1:]
	while (conn_matrix[c1][c2][-1]=='"' or conn_matrix[c1][c2][-1]=="'"):
	conn_matrix[c1][c2]=conn_matrix[c1][c2][:-1]
	jump_list=[]
	# Check for jump label sanity and add a list of elements where jumps exist.
	for c1 in range(0, conn_rows):
	for c2 in range(0, conn_columns):
	curr_element = {"exist":0, "jump":1}
	if (conn_matrix[c1][c2]==''):
	del curr_element["exist"]
	del curr_element["jump"]
	elif (len(conn_matrix[c1][c2])>3):
	if (conn_matrix[c1][c2].lower()[0:4] == "jump"):
	del curr_element["exist"]
	else:
	del curr_element["jump"]
	else:
	del curr_element["jump"]
	if ("jump" in curr_element):
	if (c1<conn_rows-1):
	next_row_element = {"exist":0, "jump":1}
	if (conn_matrix[c1+1][c2]==''):
	del next_row_element["exist"]
	del next_row_element["jump"]
	elif (len(conn_matrix[c1+1][c2])>3):
	if (conn_matrix[c1+1][c2].lower()[0:4] == "jump"):
	del next_row_element["exist"]
	else:
	del next_row_element["jump"]
	else:
	del next_row_element["jump"]
	else:
	next_row_element = {}
	if (c1>0):
	prev_row_element = {"exist":0, "jump":1}
	if (conn_matrix[c1-1][c2]==''):
	del prev_row_element["exist"]
	del prev_row_element["jump"]
	elif (len(conn_matrix[c1-1][c2])>3):
	if (conn_matrix[c1-1][c2].lower()[0:4] == "jump"):
	del prev_row_element["exist"]
	else:
	del prev_row_element["jump"]
	else:
	del prev_row_element["jump"]
	else:
	prev_row_element = {}
	if (c2<conn_columns-1):
	next_col_element = {"exist":0, "jump":1}
	if (conn_matrix[c1][c2+1]==''):
	del next_col_element["exist"]
	del next_col_element["jump"]
	elif (len(conn_matrix[c1][c2+1])>3):
	if (conn_matrix[c1][c2+1].lower()[0:4] == "jump"):
	del next_col_element["exist"]
	else:
	del next_col_element["jump"]
	else:
	del next_col_element["jump"]
	else:
	next_col_element = {}
	if (c2>0):
	prev_col_element = {"exist":0, "jump":1}
	if (conn_matrix[c1][c2-1]==''):
	del prev_col_element["exist"]
	del prev_col_element["jump"]
	elif (len(conn_matrix[c1][c2-1])>3):
	if (conn_matrix[c1][c2-1].lower()[0:4] == "jump"):
	del prev_col_element["exist"]
	else:
	del prev_col_element["jump"]
	else:
	del prev_col_element["jump"]
	else:
	prev_col_element = {}
	if ("jump" in next_row_element or "jump" in next_col_element or "jump" in prev_row_element or "jump" in prev_col_element):
	print "Two jumps can't be adjacent to each other."
	print "Check jump at row %d, column %d" %(c1, c2)
	if ("exist" in next_row_element):
	if ("exist" in next_col_element or "exist" in prev_row_element or "exist" in prev_col_element):
	print "Jump has to be the extreme connector on a branch segment."
	print "Check jump at row %d, column %d" %(c1, c2)
	else:
	jump_list.append([c1, c2, conn_matrix[c1][c2], "down"])
	elif ("exist" in next_col_element):
	if ("exist" in next_row_element or "exist" in prev_row_element or "exist" in prev_col_element):
	print "Jump has to be the extreme connector on a branch segment."
	print "Check jump at row %d, column %d" %(c1, c2)
	else:
	jump_list.append([c1, c2, conn_matrix[c1][c2], "right"])
	elif ("exist" in prev_row_element):
	if ("exist" in next_row_element or "exist" in next_col_element or "exist" in prev_col_element):
	print "Jump has to be the extreme connector on a branch segment."
	print "Check jump at row %d, column %d" %(c1, c2)
	else:
	jump_list.append([c1, c2, conn_matrix[c1][c2], "up"])
	elif ("exist" in prev_col_element):
	if ("exist" in next_row_element or "exist" in next_col_element or "exist" in prev_row_element):
	print "Jump has to be the extreme connector on a branch segment."
	print "Check jump at row %d, column %d" %(c1, c2)
	else:
	jump_list.append([c1, c2, conn_matrix[c1][c2], "left"])
	# Create a dictionary of jumps - for each jump label - there is a list with two elements.
	jump_matrix={}
	for c1 in range(len(jump_list)):
	jump_count=1
	for c2 in range(len(jump_list)):
	if not c1==c2:
	if jump_list[c1][2]==jump_list[c2][2]:
	jump_matrix[jump_list[c1][2]]=[[[jump_list[c1][0], jump_list[c1][1]], jump_list[c1][3]], [[jump_list[c2][0], jump_list[c2][1]], jump_list[c2][3]]]
	jump_count=jump_count+1
	if (jump_count<2):
	print "Error. Corresponding jump label for %s does not exist" %(jump_list[c1][2])
	elif (jump_count>2):
	print "Error. More than two jump labels for %s present" %(jump_list[c1][2])
	del jump_matrix[jump_list[c1][2]]
	# A node is defined as a junction of 3 or more branches.
	node_list=[]
	for c1 in range(0, conn_rows):
	for c2 in range(0, conn_columns):
	curr_element = {"exist":0, "jump":1}
	if (conn_matrix[c1][c2]==''):
	del curr_element["exist"]
	del curr_element["jump"]
	elif (len(conn_matrix[c1][c2])>3):
	if (conn_matrix[c1][c2].lower()[0:4] == "jump"):
	del curr_element["exist"]
	else:
	del curr_element["jump"]
	if ("exist" in curr_element):
	if ((c1==0 and c2==0) or (c1==conn_rows-1 and c2==conn_columns-1) or (c1==0 and c2==conn_columns-1) or (c1==conn_rows-1 and c2==0)):
	# If its a corner point it can't be a node. This prevents array index going out of range.
	pass
	# The next cases, can't be outer edges or corner points.
	else:
	if (c1==0):
	# If it is the first row,
	# check if the element in the next and previous columns and same row are connected.
	if not (conn_matrix[c1][c2+1]=='' or conn_matrix[c1][c2-1]==''):
	# Then check if the element in next row and same column is connected. Look for a T junction.
	if not (conn_matrix[c1+1][c2]==''):
	node_list.append([c1, c2])
	if (c1==conn_rows-1):
	# If it is the last row,
	# check if the elements in the next and previous columns and same row are connected.
	if not (conn_matrix[c1][c2+1]=='' or conn_matrix[c1][c2-1]==''):
	if not (conn_matrix[c1-1][c2]==''):
	# Then check if element in the previous row and same column is connected. Look for a T junction.
	node_list.append([c1, c2])
	if (c2==0):
	# If it is the first column,
	# check if the element in the next column and same row is connected.
	if not (conn_matrix[c1][c2+1]==''):
	# Then check if the elements in next and previous row and same column are connected. Look for a T junction.
	if not (conn_matrix[c1+1][c2]=='' or conn_matrix[c1-1][c2]==''):
	node_list.append([c1, c2])
	if (c2==conn_columns-1):
	# If it is the last column,
	# check if the element in the previous column and same row is connected.
	if not (conn_matrix[c1][c2-1]==''):
	# Then check if the elements in next and previous row and same column are connected. Look for a T junction.
	if not (conn_matrix[c1+1][c2]=='' or conn_matrix[c1-1][c2]==''):
	node_list.append([c1, c2])
	if (c1>0 and c1<conn_rows-1 and c2>0 and c2<conn_columns-1):
	# If the element is not on the outer boundary
	if (conn_matrix[c1][c2+1]!='' and conn_matrix[c1][c2-1]!=''):
	# Check if the elements in next and previous columns and same row are connected
	if (conn_matrix[c1+1][c2]!='' or conn_matrix[c1-1][c2]!=''):
	# Then check if elements in either the next and previous row and same column are connected
	node_list.append([c1, c2])
	elif (conn_matrix[c1+1][c2]!='' and conn_matrix[c1-1][c2]!=''):
	if (conn_matrix[c1][c2+1]!='' or conn_matrix[c1][c2-1]!=''):
	node_list.append([c1, c2])
	else:
	pass
	# This list contains all the nodes that are T or + junctions.
	#print "*"*60
	#print node_list
	#print "*"*60
	# Map of branches between nodes in node_list
	branch_map=[]
	# Creating an square of the dimension of node_list.
	# Each element will be a list of the series connection of branches between the nodes.
	for c1 in range(len(node_list)):
	branch_rows=[]
	for c2 in range(len(node_list)):
	branch_rows.append([])
	branch_map.append(branch_rows)
	# Generate a search rule for each node.
	# The concept is to start at a node and search until another node is reached.
	node_iter_rule=[]
	for c1 in range(len(node_list)):
	node_row=node_list[c1][0]
	node_column=node_list[c1][1]
	iter_rule={"left":0, "down":1, "right":2, "up":3}
	# For nodes in the outer edges, the rules going outwards will be removed.
	if (node_row==0):
	del(iter_rule["up"])
	if (node_row==conn_rows-1):
	del(iter_rule["down"])
	if (node_column==0):
	del(iter_rule["left"])
	if (node_column==conn_columns-1):
	del(iter_rule["right"])
	# Depending on the non-existence of elements in a direction, those rules will be removed.
	if (node_row>0) and (node_row<conn_rows-1) and (node_column>0) and (node_column<conn_columns-1):
	if (conn_matrix[node_row-1][node_column]==''):
	del(iter_rule["up"])
	if (conn_matrix[node_row+1][node_column]==''):
	del(iter_rule["down"])
	if (conn_matrix[node_row][node_column+1]==''):
	del(iter_rule["right"])
	if (conn_matrix[node_row][node_column-1]==''):
	del(iter_rule["left"])
	node_iter_rule.append(iter_rule)
	# Check if a jump is not next to a node.
	for c1 in range(len(node_list)):
	for jump_check_dir in node_iter_rule[c1].keys():
	if (jump_check_dir=="up"):
	if (len(conn_matrix[node_list[c1][0]-1][node_list[c1][1]])>3):
	if (conn_matrix[node_list[c1][0]-1][node_list[c1][1]].lower()[0:4]=="jump"):
	print "Error. Jump can't be next to a node. Check jump at row %d column %d." %(node_list[c1][0]-1, node_list[c1][1])
	if (jump_check_dir=="down"):
	if (len(conn_matrix[node_list[c1][0]+1][node_list[c1][1]])>3):
	if (conn_matrix[node_list[c1][0]+1][node_list[c1][1]].lower()[0:4]=="jump"):
	print "Error. Jump can't be next to a node. Check jump at row %d column %d." %(node_list[c1][0]+1, node_list[c1][1])
	if (jump_check_dir=="left"):
	if (len(conn_matrix[node_list[c1][0]][node_list[c1][1]-1])>3):
	if (conn_matrix[node_list[c1][0]][node_list[c1][1]-1].lower()[0:4]=="jump"):
	print "Error. Jump can't be next to a node. Check jump at row %d column %d." %(node_list[c1][0], node_list[c1][1]-1)
	if (jump_check_dir=="right"):
	if (len(conn_matrix[node_list[c1][0]][node_list[c1][1]+1])>3):
	if (conn_matrix[node_list[c1][0]][node_list[c1][1]+1].lower()[0:4]=="jump"):
	print "Error. Jump can't be next to a node. Check jump at row %d column %d." %(node_list[c1][0], node_list[c1][1]+1)
	# For each node in node_list perform the search operation.
	# Each node has a list of possible search rules.
	# Perform a search for each rule.
	# From the starting node, advance in the direction of the rule.
	# After advancing, check if the next element is a node.
	# If it is a node, stop.
	# If it is not a node, there can be only two directions of movement.
	# Move in a direction and check is an element exists.
	# If it exists, check if it is not already an element encountered - shouldn't be moving backwards.
	# If a new element is encountered, update the element is branch iter and continue.
	for c1 in range(len(node_list)):
	node_row=node_list[c1][0]
	node_column=node_list[c1][1]
	for branch_dir in node_iter_rule[c1].keys():
	branch_iter=[]
	branch_iter.append([node_row, node_column])
	# Initial advancement.
	if (branch_dir=="left"):
	if (node_column>0):
	next_node_row=node_row
	next_node_column=node_column-1
	if (branch_dir=="down"):
	if (node_row<conn_rows-1):
	next_node_row=node_row+1
	next_node_column=node_column
	if (branch_dir=="right"):
	if (node_column<conn_columns-1):
	next_node_row=node_row
	next_node_column=node_column+1
	if (branch_dir=="up"):
	if (node_row>0):
	next_node_row=node_row-1
	next_node_column=node_column
	# This variable is used when jumps are encountered.
	jump_executed=""
	# Termination condition - next element is a node.
	while not ([next_node_row, next_node_column] in node_list):
	# If a jump is encountered.
	# Look for the label in the jump_matrix dictionary
	# Check which element has been encountered.
	# Check the co-ordinates of the other element and the sense of movement.
	# Depending on the sense of movement, update the new co-ordinates with respect
	# to the other element
	# Add a flag to show which direction movement has taken place
	# To ensure that we don't go back from the next element after the jump.
	if (len(conn_matrix[next_node_row][next_node_column])>3):
	if (conn_matrix[next_node_row][next_node_column].lower()[0:4] == "jump"):
	jump_trace=conn_matrix[next_node_row][next_node_column]
	if (jump_matrix[jump_trace][0][0] == [next_node_row, next_node_column]):
	if (jump_matrix[jump_trace][1][1] == "left"):
	next_node_row=jump_matrix[jump_trace][1][0][0]
	next_node_column=jump_matrix[jump_trace][1][0][1] - 1
	jump_executed="left"
	elif (jump_matrix[jump_trace][1][1] == "right"):
	next_node_row=jump_matrix[jump_trace][1][0][0]
	next_node_column=jump_matrix[jump_trace][1][0][1] + 1
	jump_executed="right"
	elif (jump_matrix[jump_trace][1][1] == "up"):
	next_node_row=jump_matrix[jump_trace][1][0][0] - 1
	next_node_column=jump_matrix[jump_trace][1][0][1]
	jump_executed="up"
	elif (jump_matrix[jump_trace][1][1] == "down"):
	next_node_row=jump_matrix[jump_trace][1][0][0] + 1
	next_node_column=jump_matrix[jump_trace][1][0][1]
	jump_executed="down"
	elif (jump_matrix[jump_trace][1][0] == [next_node_row, next_node_column]):
	if (jump_matrix[jump_trace][0][1] == "left"):
	next_node_row=jump_matrix[jump_trace][0][0][0]
	next_node_column=jump_matrix[jump_trace][0][0][1] - 1
	jump_executed="left"
	elif (jump_matrix[jump_trace][0][1] == "right"):
	next_node_row=jump_matrix[jump_trace][0][0][0]
	next_node_column=jump_matrix[jump_trace][0][0][1] + 1
	jump_executed="right"
	elif (jump_matrix[jump_trace][0][1] == "up"):
	next_node_row=jump_matrix[jump_trace][0][0][0] - 1
	next_node_column=jump_matrix[jump_trace][0][0][1]
	jump_executed="up"
	elif (jump_matrix[jump_trace][0][1] == "down"):
	next_node_row=jump_matrix[jump_trace][0][0][0] + 1
	next_node_column=jump_matrix[jump_trace][0][0][1]
	jump_executed="down"
	branch_iter.append([next_node_row, next_node_column])
	# This temporary variable is to ensure, two advancements don't take place in one loop.
	branch_proceed=0
	if ((next_node_column>0) and branch_proceed==0):
	# We are trying to go left, so check if we didn't jump right.
	if (conn_matrix[next_node_row][next_node_column-1] != '' and jump_executed!="right"):
	# Next check is if we are going backwards.
	if not ([next_node_row, next_node_column-1] in branch_iter):
	next_node_column=next_node_column-1
	branch_proceed=1
	# Set jump to null after a movement. We can't go back anyway.
	jump_executed=""
	if ((next_node_row>0) and branch_proceed==0):
	# We are trying to go up, so check if we didn't jump down.
	if (conn_matrix[next_node_row-1][next_node_column] != '' and jump_executed!="down"):
	if not ([next_node_row-1, next_node_column] in branch_iter):
	next_node_row=next_node_row-1
	branch_proceed=1
	# Set jump to null after a movement. We can't go back anyway.
	jump_executed=""
	if ((next_node_column<conn_columns-1) and branch_proceed==0):
	# We are trying to go right, so check if we didn't jump left.
	if (conn_matrix[next_node_row][next_node_column+1] != '' and jump_executed!="left"):
	if not ([next_node_row, next_node_column+1] in branch_iter):
	next_node_column=next_node_column+1
	branch_proceed=1
	# Set jump to null after a movement. We can't go back anyway.
	jump_executed=""
	if ((next_node_row<conn_rows-1) and branch_proceed==0):
	# We are trying to go down, so check if we didn't jump up.
	if (conn_matrix[next_node_row+1][next_node_column] != '' and jump_executed!="up"):
	if not ([next_node_row+1, next_node_column] in branch_iter):
	next_node_row=next_node_row+1
	branch_proceed=1
	# Set jump to null after a movement. We can't go back anyway.
	jump_executed=""
	# If no advancement is possible, it means circuit is broken.
	# Can improve on this error message later.
	if ([next_node_row, next_node_column] in branch_iter):
	print "Error. Circuit broken! Close all branches. Check at row %d column %d" %(next_node_row, next_node_column)
	break
	else:
	branch_iter.append([next_node_row, next_node_column])
	branch_map[c1][node_list.index([next_node_row, next_node_column])].append(branch_iter)
	nw_look=open("nw_check.csv","w")
	for c1 in range(len(node_list)):
	for c2 in range(len(node_list)-1):
	if (branch_map[c1][c2]):
	for c3 in range(len(branch_map[c1][c2])):
	nw_look.write("(")
	for c4 in range(len(branch_map[c1][c2][c3])):
	nw_look.write("[%d %d] ;" %(branch_map[c1][c2][c3][c4][0], branch_map[c1][c2][c3][c4][1]))
	nw_look.write(")")
	nw_look.write(", ")
	else:
	nw_look.write("[], ")
	if (branch_map[c1][c2+1]):
	for c3 in range(len(branch_map[c1][c2+1])):
	nw_look.write("(")
	for c4 in range(len(branch_map[c1][c2+1][c3])):
	nw_look.write("[%d %d] ;" %(branch_map[c1][c2+1][c3][c4][0], branch_map[c1][c2+1][c3][c4][1]))
	nw_look.write(")")
	nw_look.write("\n")
	else:
	nw_look.write("[] \n")
	##for c1 in range(len(node_list)):
	## for c2 in range(len(node_list)-1):
	## nw_look.write("%s ;" %(branch_map[c1][c2]))
	## nw_look.write("%s \n" %(branch_map[c1][c2+1]))
	nw_look.close()
	number_of_nodes=len(node_list)
	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
	# Determining the loops
	loop_list=[]
	loop_count = 0
	# Number of non-null elements (branches) on every row and column of branch_map
	branch_map_rows=[]
	branch_map_columns=[]
	for c1 in range(len(node_list)):
	branch_rows_count=0
	branch_columns_count=0
	for c2 in range(len(node_list)):
	if branch_map[c1][c2]:
	branch_rows_count+=1
	if branch_map[c2][c1]:
	branch_columns_count+=1
	branch_map_rows.append(branch_rows_count)
	branch_map_columns.append(branch_columns_count)
	# Pick a row
	for c1 in range(number_of_nodes-1):
	# Diagonal elements are null
	# So choose the column next to diagonal
	c2=c1+1
	#check if it exists
	while not branch_map[c1][c2]:
	# If not move to next column
	c2=c2+1
	# Check if the column is within dimensions
	if (c2>=number_of_nodes):
	# If not, break out and move to next row
	break
	else:
	# Starting branch found
	# Check is there are parallel branches between the nodes
	for c3 in range(len(branch_map[c1][c2])-1):
	loop_list.append([[c1, c2], [c1, c2]])
	loop_count+=1
	# Reduce the number of elements in the rows from zero up to the current row
	# checking for elements to the left of the starting element
	# The idea is that you can't go right in the loop.
	for row_count in range(c1, number_of_nodes):
	for col_count in range(c2):
	if branch_map[row_count][col_count]:
	if (branch_map_rows[row_count]>1):
	branch_map_rows[row_count]-=1
	# Set the loop row and column count
	loop_row=c1
	loop_column=c2
	print "*"*70
	print c1, c2
	print branch_map_rows
	print branch_map_columns
	# Move right along the row of branch_map until the end.
	for c4 in range(c2+1, number_of_nodes):
	# Initialize the loop iterator list with the first element.
	loop_iter=[]
	loop_iter.append([c1, c2])
	# check if there is an element in that row
	if branch_map[c1][c4]:
	# If an element exists, add it to loop iterator
	# Decrease the number of times that row can be visited.
	loop_iter.append([c1, c4])
	branch_map_rows[loop_row]-=1
	# Move down from that element
	loop_dir="down"
	# Update the loop row and column counter to that element
	loop_row=c1
	loop_column=c4
	print loop_iter
	print c1, c4
	print branch_map_rows
	print branch_map_columns
	print loop_dir
	# The termination condition is that the loop should have "ended"
	while (loop_dir != "end"):
	# Check for parallel branches again.
	for c3 in range(len(branch_map[c1][c4])-1):
	loop_list.append([[c1, c4], [c1, c4]])
	loop_count+=1
	# Not using this block but I'll keep it anyway
	if (loop_dir == "right" and branch_map_rows[loop_row]>0):
	c3=loop_column+1
	while (c3<number_of_nodes):
	if branch_map[loop_row][c3]:
	loop_iter.append([loop_row, c3])
	if (branch_map[loop_row][c3][0][0] == branch_map[loop_iter[0][0]][loop_iter[0][1]][0][-1] or \
	branch_map[loop_row][c3][0][-1] == branch_map[loop_iter[0][0]][loop_iter[0][1]][0][-1]):
	loop_dir="end"
	branch_map_rows[loop_row]-=1
	else:
	loop_column=c3
	loop_dir="down"
	branch_map_rows[loop_row]-=1
	break
	else:
	c3=c3+1
	else:
	loop_dir="end"
	loop_iter=[]
	branch_map_rows[loop_row]-=1
	print loop_iter
	print loop_dir
	print branch_map_rows
	print branch_map_columns
	# Will be executed if we are moving down
	# and there are elements in that column
	if (loop_dir == "down" and branch_map_columns[loop_column]>0):
	# Start from the next row in that column
	c3=loop_row+1
	# check if it is within the dimensions
	while (c3<number_of_nodes):
	# Check if an element exists there
	if branch_map[c3][loop_column]:
	# If so, add that element.
	loop_iter.append([c3, loop_column])
	# Check if that is the last element
	# Check if one of the extreme nodes in that branch is the same as the starting nodes in the loop iterator.
	if (branch_map[c3][loop_column][0][0] == branch_map[loop_iter[0][0]][loop_iter[0][1]][0][-1] or \
	branch_map[c3][loop_column][0][-1] == branch_map[loop_iter[0][0]][loop_iter[0][1]][0][-1]):
	# If so, loop has ended
	loop_dir="end"
	# Decrement the column counter
	# There is one element less in that column
	branch_map_columns[loop_column]-=1
	else:
	# If not, we move to the left
	# Update the loop row counter
	loop_row=c3
	loop_dir="left"
	# Decrement the column counter
	branch_map_columns[loop_column]-=1
	break
	else:
	# If no element is as the spot, check the next row in the that column
	c3=c3+1
	else:
	# If the end of the matrix has reached without finding an element
	# this means that a loop can't be formed
	# End the loop and make the iterator null
	loop_dir="end"
	loop_iter=[]
	# The column counter still decrements so that we don't come here again.
	branch_map_columns[loop_column]-=1
	print loop_iter
	print loop_dir
	print branch_map_rows
	print branch_map_columns
	# Will be executed if we are moving left
	# and there are elements in that row
	if (loop_dir == "left" and branch_map_rows[loop_row]>0):
	# Start from the previous column in that row
	c3=loop_column-1
	# check if it is within the dimensions
	while (c3>=0):
	# Check if an element exists there
	if branch_map[loop_row][c3]:
	# If so, add that element.
	loop_iter.append([loop_row, c3])
	# Check if that is the last element
	# Check if one of the extreme nodes in that branch is the same as the starting nodes in the loop iterator.
	if (branch_map[loop_row][c3][0][0] == branch_map[loop_iter[0][0]][loop_iter[0][1]][0][-1] or \
	branch_map[loop_row][c3][0][-1] == branch_map[loop_iter[0][0]][loop_iter[0][1]][0][-1]):
	# If so, loop has ended
	loop_dir="end"
	# Decrement the row counter
	# There is one element less in that row
	branch_map_rows[loop_row]-=1
	else:
	# If not, we move up
	# Update the loop column counter
	loop_column=c3
	loop_dir="up"
	# Decrement the column counter
	branch_map_rows[loop_row]-=1
	break
	else:
	# If no element is as the spot, check the previous column in the that row
	c3=c3-1
	else:
	# If the end of the matrix has reached without finding an element
	# this means that a loop can't be formed
	# End the loop and make the iterator null
	loop_dir="end"
	loop_iter=[]
	# The column counter still decrements so that we don't come here again.
	branch_map_rows[loop_row]-=1
	print loop_iter
	print loop_dir
	print branch_map_rows
	print branch_map_columns
	# Will be executed if we are moving up
	# and there are elements in that column
	if (loop_dir == "up" and branch_map_columns[loop_column]>0):
	# Start from the previous row in that column
	c3=loop_row-1
	# check if it is within the dimensions
	while (c3>=0):
	# Check if an element exists there
	if branch_map[c3][loop_column]:
	# If so, add that element.
	loop_iter.append([c3, loop_column])
	# Check if that is the last element
	# Check if one of the extreme nodes in that branch is the same as the starting nodes in the loop iterator.
	if (branch_map[c3][loop_column][0][0] == branch_map[loop_iter[0][0]][loop_iter[0][1]][0][-1] or \
	branch_map[c3][loop_column][0][-1] == branch_map[loop_iter[0][0]][loop_iter[0][1]][0][-1]):
	# If so, loop has ended
	loop_dir="end"
	# Decrement the column counter
	# There is one element less in that column
	branch_map_columns[loop_column]-=1
	else:
	# If not, we move to the left
	# Update the loop row counter
	loop_row=c3
	loop_dir="left"
	# Decrement the column counter
	branch_map_columns[loop_column]-=1
	break
	else:
	# If no element is as the spot, check the previous row in the that column
	c3=c3-1
	else:
	# If the end of the matrix has reached without finding an element
	# this means that a loop can't be formed
	# End the loop and make the iterator null
	loop_dir="end"
	loop_iter=[]
	# The column counter still decrements so that we don't come here again.
	branch_map_columns[loop_column]-=1
	print loop_iter
	print loop_dir
	print branch_map_rows
	print branch_map_columns
	if loop_iter:
	loop_count+=1
	loop_list.append(loop_iter)
	loop_iter=[]
	print loop_count
	print loop_list

view raw node_br_loop.py hosted with ❤ by GitHub

The loop identification part is:

	# Determining the loops
	loop_list=[]
	loop_count = 0
	# Number of non-null elements (branches) on every row and column of branch_map
	branch_map_rows=[]
	branch_map_columns=[]
	for c1 in range(len(node_list)):
	branch_rows_count=0
	branch_columns_count=0
	for c2 in range(len(node_list)):
	if branch_map[c1][c2]:
	branch_rows_count+=1
	if branch_map[c2][c1]:
	branch_columns_count+=1
	branch_map_rows.append(branch_rows_count)
	branch_map_columns.append(branch_columns_count)
	# Pick a row
	for c1 in range(number_of_nodes-1):
	# Diagonal elements are null
	# So choose the column next to diagonal
	c2=c1+1
	#check if it exists
	while not branch_map[c1][c2]:
	# If not move to next column
	c2=c2+1
	# Check if the column is within dimensions
	if (c2>=number_of_nodes):
	# If not, break out and move to next row
	break
	else:
	# Starting branch found
	# Check is there are parallel branches between the nodes
	for c3 in range(len(branch_map[c1][c2])-1):
	loop_list.append([[c1, c2], [c1, c2]])
	loop_count+=1
	# Reduce the number of elements in the rows from zero up to the current row
	# checking for elements to the left of the starting element
	# The idea is that you can't go right in the loop.
	for row_count in range(c1, number_of_nodes):
	for col_count in range(c2):
	if branch_map[row_count][col_count]:
	if (branch_map_rows[row_count]>1):
	branch_map_rows[row_count]-=1
	# Set the loop row and column count
	loop_row=c1
	loop_column=c2
	print "*"*70
	print c1, c2
	print branch_map_rows
	print branch_map_columns
	# Move right along the row of branch_map until the end.
	for c4 in range(c2+1, number_of_nodes):
	# Initialize the loop iterator list with the first element.
	loop_iter=[]
	loop_iter.append([c1, c2])
	# check if there is an element in that row
	if branch_map[c1][c4]:
	# If an element exists, add it to loop iterator
	# Decrease the number of times that row can be visited.
	loop_iter.append([c1, c4])
	branch_map_rows[loop_row]-=1
	# Move down from that element
	loop_dir="down"
	# Update the loop row and column counter to that element
	loop_row=c1
	loop_column=c4
	print loop_iter
	print c1, c4
	print branch_map_rows
	print branch_map_columns
	print loop_dir
	# The termination condition is that the loop should have "ended"
	while (loop_dir != "end"):
	# Check for parallel branches again.
	for c3 in range(len(branch_map[c1][c4])-1):
	loop_list.append([[c1, c4], [c1, c4]])
	loop_count+=1
	# Not using this block but I'll keep it anyway
	if (loop_dir == "right" and branch_map_rows[loop_row]>0):
	c3=loop_column+1
	while (c3<number_of_nodes):
	if branch_map[loop_row][c3]:
	loop_iter.append([loop_row, c3])
	if (branch_map[loop_row][c3][0][0] == branch_map[loop_iter[0][0]][loop_iter[0][1]][0][-1] or \
	branch_map[loop_row][c3][0][-1] == branch_map[loop_iter[0][0]][loop_iter[0][1]][0][-1]):
	loop_dir="end"
	branch_map_rows[loop_row]-=1
	else:
	loop_column=c3
	loop_dir="down"
	branch_map_rows[loop_row]-=1
	break
	else:
	c3=c3+1
	else:
	loop_dir="end"
	loop_iter=[]
	branch_map_rows[loop_row]-=1
	print loop_iter
	print loop_dir
	print branch_map_rows
	print branch_map_columns
	# Will be executed if we are moving down
	# and there are elements in that column
	if (loop_dir == "down" and branch_map_columns[loop_column]>0):
	# Start from the next row in that column
	c3=loop_row+1
	# check if it is within the dimensions
	while (c3<number_of_nodes):
	# Check if an element exists there
	if branch_map[c3][loop_column]:
	# If so, add that element.
	loop_iter.append([c3, loop_column])
	# Check if that is the last element
	# Check if one of the extreme nodes in that branch is the same as the starting nodes in the loop iterator.
	if (branch_map[c3][loop_column][0][0] == branch_map[loop_iter[0][0]][loop_iter[0][1]][0][-1] or \
	branch_map[c3][loop_column][0][-1] == branch_map[loop_iter[0][0]][loop_iter[0][1]][0][-1]):
	# If so, loop has ended
	loop_dir="end"
	# Decrement the column counter
	# There is one element less in that column
	branch_map_columns[loop_column]-=1
	else:
	# If not, we move to the left
	# Update the loop row counter
	loop_row=c3
	loop_dir="left"
	# Decrement the column counter
	branch_map_columns[loop_column]-=1
	break
	else:
	# If no element is as the spot, check the next row in the that column
	c3=c3+1
	else:
	# If the end of the matrix has reached without finding an element
	# this means that a loop can't be formed
	# End the loop and make the iterator null
	loop_dir="end"
	loop_iter=[]
	# The column counter still decrements so that we don't come here again.
	branch_map_columns[loop_column]-=1
	print loop_iter
	print loop_dir
	print branch_map_rows
	print branch_map_columns
	# Will be executed if we are moving left
	# and there are elements in that row
	if (loop_dir == "left" and branch_map_rows[loop_row]>0):
	# Start from the previous column in that row
	c3=loop_column-1
	# check if it is within the dimensions
	while (c3>=0):
	# Check if an element exists there
	if branch_map[loop_row][c3]:
	# If so, add that element.
	loop_iter.append([loop_row, c3])
	# Check if that is the last element
	# Check if one of the extreme nodes in that branch is the same as the starting nodes in the loop iterator.
	if (branch_map[loop_row][c3][0][0] == branch_map[loop_iter[0][0]][loop_iter[0][1]][0][-1] or \
	branch_map[loop_row][c3][0][-1] == branch_map[loop_iter[0][0]][loop_iter[0][1]][0][-1]):
	# If so, loop has ended
	loop_dir="end"
	# Decrement the row counter
	# There is one element less in that row
	branch_map_rows[loop_row]-=1
	else:
	# If not, we move up
	# Update the loop column counter
	loop_column=c3
	loop_dir="up"
	# Decrement the column counter
	branch_map_rows[loop_row]-=1
	break
	else:
	# If no element is as the spot, check the previous column in the that row
	c3=c3-1
	else:
	# If the end of the matrix has reached without finding an element
	# this means that a loop can't be formed
	# End the loop and make the iterator null
	loop_dir="end"
	loop_iter=[]
	# The column counter still decrements so that we don't come here again.
	branch_map_rows[loop_row]-=1
	print loop_iter
	print loop_dir
	print branch_map_rows
	print branch_map_columns
	# Will be executed if we are moving up
	# and there are elements in that column
	if (loop_dir == "up" and branch_map_columns[loop_column]>0):
	# Start from the previous row in that column
	c3=loop_row-1
	# check if it is within the dimensions
	while (c3>=0):
	# Check if an element exists there
	if branch_map[c3][loop_column]:
	# If so, add that element.
	loop_iter.append([c3, loop_column])
	# Check if that is the last element
	# Check if one of the extreme nodes in that branch is the same as the starting nodes in the loop iterator.
	if (branch_map[c3][loop_column][0][0] == branch_map[loop_iter[0][0]][loop_iter[0][1]][0][-1] or \
	branch_map[c3][loop_column][0][-1] == branch_map[loop_iter[0][0]][loop_iter[0][1]][0][-1]):
	# If so, loop has ended
	loop_dir="end"
	# Decrement the column counter
	# There is one element less in that column
	branch_map_columns[loop_column]-=1
	else:
	# If not, we move to the left
	# Update the loop row counter
	loop_row=c3
	loop_dir="left"
	# Decrement the column counter
	branch_map_columns[loop_column]-=1
	break
	else:
	# If no element is as the spot, check the previous row in the that column
	c3=c3-1
	else:
	# If the end of the matrix has reached without finding an element
	# this means that a loop can't be formed
	# End the loop and make the iterator null
	loop_dir="end"
	loop_iter=[]
	# The column counter still decrements so that we don't come here again.
	branch_map_columns[loop_column]-=1
	print loop_iter
	print loop_dir
	print branch_map_rows
	print branch_map_columns
	if loop_iter:
	loop_count+=1
	loop_list.append(loop_iter)
	loop_iter=[]
	print loop_count
	print loop_list

view raw loop.py hosted with ❤ by GitHub

This works for a couple of circuits. But I'll have to test it for all kinds of circuits (or layouts rather) before moving to the next step.

Some things that I assumed:

1. The branch_map matrix is symmetrical (at least in branch information if not exactly). So this means branches will be picked up sooner or later if a reasonably detailed search method is used.

2. To elaborate on what a "reseaonably detailed" search method is.

3. I start from an element in the row which is the first after the null diagonal element. So this is the first branch. I touch EVERY element in this first row. This means, I take a turn (turning down) at all the other nodes (columns) that this node (row) is connected.

4. I then move left from the first element in the column where I turned. The other nodes in that column are not touched. Will this affect later? Will have to think about it.

5. Similarly, the other searches will also turn a the first node they find.


This is the output from the latest circuit that I pasted. It works for a few simple other ones, but will have to test specifically if the code will break at those assumptions.

	**********************************************************************
	0 1
	[3, 2, 2, 3, 3, 3, 3, 3, 2, 3]
	[3, 3, 3, 3, 3, 4, 3, 3, 2, 3]
	[[0, 1], [0, 2]]
	0 2
	[2, 2, 2, 3, 3, 3, 3, 3, 2, 3]
	[3, 3, 3, 3, 3, 4, 3, 3, 2, 3]
	down
	[[0, 1], [0, 2], [1, 2]]
	end
	[2, 2, 2, 3, 3, 3, 3, 3, 2, 3]
	[3, 3, 2, 3, 3, 4, 3, 3, 2, 3]
	[[0, 1], [0, 5]]
	0 5
	[1, 2, 2, 3, 3, 3, 3, 3, 2, 3]
	[3, 3, 2, 3, 3, 4, 3, 3, 2, 3]
	down
	[[0, 1], [0, 5], [4, 5]]
	left
	[1, 2, 2, 3, 3, 3, 3, 3, 2, 3]
	[3, 3, 2, 3, 3, 3, 3, 3, 2, 3]
	[[0, 1], [0, 5], [4, 5], [4, 3]]
	up
	[1, 2, 2, 3, 2, 3, 3, 3, 2, 3]
	[3, 3, 2, 3, 3, 3, 3, 3, 2, 3]
	[[0, 1], [0, 5], [4, 5], [4, 3], [2, 3]]
	left
	[1, 2, 2, 3, 2, 3, 3, 3, 2, 3]
	[3, 3, 2, 2, 3, 3, 3, 3, 2, 3]
	[[0, 1], [0, 5], [4, 5], [4, 3], [2, 3], [2, 1]]
	end
	[1, 2, 1, 3, 2, 3, 3, 3, 2, 3]
	[3, 3, 2, 2, 3, 3, 3, 3, 2, 3]
	**********************************************************************
	1 2
	[1, 1, 1, 3, 2, 2, 3, 2, 2, 3]
	[3, 3, 2, 2, 3, 3, 3, 3, 2, 3]
	[[1, 2], [1, 7]]
	1 7
	[1, 0, 1, 3, 2, 2, 3, 2, 2, 3]
	[3, 3, 2, 2, 3, 3, 3, 3, 2, 3]
	down
	[[1, 2], [1, 7], [6, 7]]
	left
	[1, 0, 1, 3, 2, 2, 3, 2, 2, 3]
	[3, 3, 2, 2, 3, 3, 3, 2, 2, 3]
	[[1, 2], [1, 7], [6, 7], [6, 5]]
	up
	[1, 0, 1, 3, 2, 2, 2, 2, 2, 3]
	[3, 3, 2, 2, 3, 3, 3, 2, 2, 3]
	[[1, 2], [1, 7], [6, 7], [6, 5], [4, 5]]
	left
	[1, 0, 1, 3, 2, 2, 2, 2, 2, 3]
	[3, 3, 2, 2, 3, 2, 3, 2, 2, 3]
	[[1, 2], [1, 7], [6, 7], [6, 5], [4, 5], [4, 3]]
	up
	[1, 0, 1, 3, 1, 2, 2, 2, 2, 3]
	[3, 3, 2, 2, 3, 2, 3, 2, 2, 3]
	[[1, 2], [1, 7], [6, 7], [6, 5], [4, 5], [4, 3], [2, 3]]
	end
	[1, 0, 1, 3, 1, 2, 2, 2, 2, 3]
	[3, 3, 2, 1, 3, 2, 3, 2, 2, 3]
	**********************************************************************
	2 3
	[1, 0, 1, 2, 1, 1, 2, 1, 2, 3]
	[3, 3, 2, 1, 3, 2, 3, 2, 2, 3]
	**********************************************************************
	3 4
	[1, 0, 1, 1, 1, 1, 2, 1, 2, 2]
	[3, 3, 2, 1, 3, 2, 3, 2, 2, 3]
	[[3, 4], [3, 9]]
	3 9
	[1, 0, 1, 0, 1, 1, 2, 1, 2, 2]
	[3, 3, 2, 1, 3, 2, 3, 2, 2, 3]
	down
	[[3, 4], [3, 9], [5, 9]]
	left
	[1, 0, 1, 0, 1, 1, 2, 1, 2, 2]
	[3, 3, 2, 1, 3, 2, 3, 2, 2, 2]
	[[3, 4], [3, 9], [5, 9], [5, 6]]
	up
	[1, 0, 1, 0, 1, 0, 2, 1, 2, 2]
	[3, 3, 2, 1, 3, 2, 3, 2, 2, 2]
	[[3, 4], [3, 9], [5, 9], [5, 6], [4, 6]]
	end
	[1, 0, 1, 0, 1, 0, 2, 1, 2, 2]
	[3, 3, 2, 1, 3, 2, 2, 2, 2, 2]
	**********************************************************************
	4 5
	[1, 0, 1, 0, 1, 0, 1, 1, 2, 1]
	[3, 3, 2, 1, 3, 2, 2, 2, 2, 2]
	[[4, 5], [4, 6]]
	4 6
	[1, 0, 1, 0, 0, 0, 1, 1, 2, 1]
	[3, 3, 2, 1, 3, 2, 2, 2, 2, 2]
	down
	[[4, 5], [4, 6], [5, 6]]
	end
	[1, 0, 1, 0, 0, 0, 1, 1, 2, 1]
	[3, 3, 2, 1, 3, 2, 1, 2, 2, 2]
	**********************************************************************
	5 6
	[1, 0, 1, 0, 0, 0, 1, 1, 2, 1]
	[3, 3, 2, 1, 3, 2, 1, 2, 2, 2]
	[[5, 6], [5, 9]]
	5 9
	[1, 0, 1, 0, 0, -1, 1, 1, 2, 1]
	[3, 3, 2, 1, 3, 2, 1, 2, 2, 2]
	down
	[[5, 6], [5, 9], [8, 9]]
	left
	[1, 0, 1, 0, 0, -1, 1, 1, 2, 1]
	[3, 3, 2, 1, 3, 2, 1, 2, 2, 1]
	[[5, 6], [5, 9], [8, 9], [8, 7]]
	up
	[1, 0, 1, 0, 0, -1, 1, 1, 1, 1]
	[3, 3, 2, 1, 3, 2, 1, 2, 2, 1]
	[[5, 6], [5, 9], [8, 9], [8, 7], [6, 7]]
	end
	[1, 0, 1, 0, 0, -1, 1, 1, 1, 1]
	[3, 3, 2, 1, 3, 2, 1, 1, 2, 1]
	**********************************************************************
	6 7
	[1, 0, 1, 0, 0, -1, 1, 1, 1, 1]
	[3, 3, 2, 1, 3, 2, 1, 1, 2, 1]
	**********************************************************************
	7 8
	[1, 0, 1, 0, 0, -1, 1, 1, 1, 1]
	[3, 3, 2, 1, 3, 2, 1, 1, 2, 1]
	**********************************************************************
	8 9
	[1, 0, 1, 0, 0, -1, 1, 1, 1, 1]
	[3, 3, 2, 1, 3, 2, 1, 1, 2, 1]
	7
	[[[0, 1], [0, 2], [1, 2]], [[0, 1], [0, 5], [4, 5], [4, 3], [2, 3], [2, 1]], [[1, 2], [1, 7], [6, 7], [6, 5], [4, 5], [4, 3], [2, 3]], [[3, 4], [3, 9], [5, 9], [5, 6], [4, 6]], [[4, 5], [4, 6], [5, 6]], [[5, 6], [5, 9], [8, 9], [8, 7], [6, 7]], [[8, 9], [8, 9]]]

view raw loop_result.txt hosted with ❤ by GitHub