Here is the code. Click on "View Raw" if you need to see the entire code.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #! /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. | |
| def scrub_elements(x, row, col): | |
| if x[row][col]: | |
| if "\n" in x[row][col]: | |
| x[row][col]=x[row][col][:-1] | |
| if x[row][col]: | |
| while (x[row][col][0]=='"' or x[row][col][0]=="'"): | |
| x[row][col]=x[row][col][1:] | |
| while (x[row][col][-1]=='"' or x[row][col][-1]=="'"): | |
| x[row][col]=x[row][col][:-1] | |
| for c1 in range(0, conn_rows): | |
| for c2 in range(0, conn_columns): | |
| scrub_elements(conn_matrix, c1, c2) | |
| # List of jumps labels | |
| jump_list=[] | |
| # Structure of jump_list | |
| # row, column, jump_label, direction | |
| # Check is it a jump, an element | |
| # or simply no connection | |
| def jump_sanity(x, x_jump, row, column): | |
| x_elem = x[row][column] | |
| if (x_elem ==''): | |
| del x_jump["exist"] | |
| del x_jump["jump"] | |
| elif (len(x_elem)>3): | |
| if (x_elem.lower()[0:4] == "jump"): | |
| del x_jump["exist"] | |
| else: | |
| del x_jump["jump"] | |
| else: | |
| del x_jump["jump"] | |
| # Check for jump label sanity and | |
| # add a list of elements where jumps exist. | |
| # Basically examines whether element (c1, c2) | |
| # is a jump and what are the elements | |
| # around it. | |
| def jump_checking(x_matrix, x_jump, row, col, no_rows, no_cols): | |
| # Current element | |
| curr_element = {"exist":0, "jump":1} | |
| # Determine if it is a jump label | |
| jump_sanity(x_matrix, curr_element, row, col) | |
| if ("jump" in curr_element): | |
| # If so, what is the element in the same column | |
| # and next row | |
| if (row<no_rows-1): | |
| next_row_element = {"exist":0, "jump":1} | |
| jump_sanity(x_matrix, next_row_element, row+1, col) | |
| else: | |
| next_row_element = {} | |
| # If so, what is the element in the same column | |
| # and previous row | |
| if (row>0): | |
| prev_row_element = {"exist":0, "jump":1} | |
| jump_sanity(x_matrix, prev_row_element, row-1, col) | |
| else: | |
| prev_row_element = {} | |
| # If so, what is the element in the same row | |
| # and next column | |
| if (col<no_cols-1): | |
| next_col_element = {"exist":0, "jump":1} | |
| jump_sanity(x_matrix, next_col_element, row, col+1) | |
| else: | |
| next_col_element = {} | |
| # If so, what is the element in the same row | |
| # and previous column | |
| if (col>0): | |
| prev_col_element = {"exist":0, "jump":1} | |
| jump_sanity(x_matrix, prev_col_element, row, col-1) | |
| else: | |
| prev_col_element = {} | |
| 21# Check if two jumps are next to each other | |
| 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" %(row, col) | |
| # Jump must have only one element adjacent to it. | |
| 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" %(row, col) | |
| else: | |
| x_jump.append([row, col, x_matrix[row][col], "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" %(row, col) | |
| else: | |
| x_jump.append([row, col, x_matrix[row][col], "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" %(row, col) | |
| else: | |
| x_jump.append([row, col, x_matrix[row][col], "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" %(row, col) | |
| else: | |
| x_jump.append([row, col, x_matrix[row][col], "left"]) | |
| for c1 in range(0, conn_rows): | |
| for c2 in range(0, conn_columns): | |
| jump_checking(conn_matrix, jump_list, c1, c2, conn_rows, conn_columns) | |
| # Create a dictionary of jumps - | |
| # for each jump label - there is a list with two elements. | |
| jump_matrix={} | |
| # Structure of jump_matrix | |
| # label: [[[row, col], "dir"], [[row, col], "dir"]] | |
| 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]: | |
| frst_jmp = jump_list[c1] | |
| scd_jmp = jump_list[c2] | |
| jump_matrix[frst_jmp[2]]=[[[frst_jmp[0], frst_jmp[1]], frst_jmp[3]],\ | |
| [[scd_jmp[0], scd_jmp[1]], scd_jmp[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. | |
| def node_checking(x_mat, x_list, row, col, x_row, x_col): | |
| if ((row==0 and col==0) or (row==x_row-1 and col==x_col-1) or \ | |
| (row==0 and col==x_col-1) or (row==x_row-1 and col==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 (row==0): | |
| # If it is the first row, | |
| # check if the element in the next and | |
| # previous columns and same row are connected. | |
| if not (x_mat[row][col+1]=='' or x_mat[row][col-1]==''): | |
| # Then check if the element in next row and | |
| # same column is connected. Look for a T junction. | |
| if not (x_mat[row+1][col]==''): | |
| x_list.append([row, col]) | |
| if (row==x_row-1): | |
| # If it is the last row, | |
| # check if the elements in the next and | |
| # previous columns and same row are connected. | |
| if not (x_mat[row][col+1]=='' or x_mat[row][col-1]==''): | |
| if not (x_mat[row-1][col]==''): | |
| # Then check if element in the previous row and | |
| # same column is connected. Look for a T junction. | |
| x_list.append([row, col]) | |
| if (col==0): | |
| # If it is the first column, | |
| # check if the element in the next column and | |
| # same row is connected. | |
| if not (x_mat[row][col+1]==''): | |
| # Then check if the elements in next and | |
| # previous row and same column are connected. | |
| # Look for a T junction. | |
| if not (x_mat[row+1][col]=='' or x_mat[row-1][col]==''): | |
| x_list.append([row, col]) | |
| if (col==x_col-1): | |
| # If it is the last column, | |
| # check if the element in the previous column and | |
| # same row is connected. | |
| if not (x_mat[row][col-1]==''): | |
| # Then check if the elements in next and | |
| # previous row and same column are connected. | |
| # Look for a T junction. | |
| if not (x_mat[row+1][col]=='' or x_mat[row-1][col]==''): | |
| x_list.append([row, col]) | |
| if (row>0 and row<x_row-1 and col>0 and col<x_col-1): | |
| # If the element is not on the outer boundary | |
| if (x_mat[row][col+1]!='' and x_mat[row][col-1]!=''): | |
| # Check if the elements in next and | |
| # previous columns and same row are connected | |
| if (x_mat[row+1][col]!='' or x_mat[row-1][col]!=''): | |
| # Then check if elements in either the next and | |
| # previous row and same column are connected | |
| x_list.append([row, col]) | |
| elif (x_mat[row+1][col]!='' and x_mat[row-1][col]!=''): | |
| if (x_mat[row][col+1]!='' or x_mat[row][col-1]!=''): | |
| x_list.append([row, col]) | |
| node_list=[] | |
| # Structure of node_list | |
| # [row, column] | |
| for c1 in range(0, conn_rows): | |
| for c2 in range(0, conn_columns): | |
| curr_element = {"exist":0, "jump":1} | |
| jump_sanity(conn_matrix, curr_element, c1, c2) | |
| if ("exist" in curr_element): | |
| node_checking(conn_matrix, node_list, c1, c2, conn_rows, conn_columns) | |
| 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) | |
| def jump_node_check(x_mat, x_list, jdir, row): | |
| n_row=x_list[c1][0] | |
| n_col=x_list[c1][1] | |
| if (jdir=="up"): | |
| if (len(x_mat[n_row-1][n_col])>3): | |
| if (x_mat[n_row-1][n_col].lower()[0:4]=="jump"): | |
| print "Error. Jump can't be next to a node. \ | |
| Check jump at row %d column %d." %(n_row-1, n_col) | |
| if (jdir=="down"): | |
| if (len(x_mat[n_row+1][n_col])>3): | |
| if (x_mat[n_row+1][n_col].lower()[0:4]=="jump"): | |
| print "Error. Jump can't be next to a node. \ | |
| Check jump at row %d column %d." %(n_row+1, n_col) | |
| if (jdir=="left"): | |
| if (len(x_mat[n_row][n_col-1])>3): | |
| if (x_mat[n_row][n_col-1].lower()[0:4]=="jump"): | |
| print "Error. Jump can't be next to a node. \ | |
| Check jump at row %d column %d." %(n_row, n_col-1) | |
| if (jdir=="right"): | |
| if (len(x_mat[n_row][n_col+1])>3): | |
| if (x_mat[n_row][n_col+1].lower()[0:4]=="jump"): | |
| print "Error. Jump can't be next to a node. \ | |
| Check jump at row %d column %d." %(n_row, n_col+1) | |
| # 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(): | |
| jump_node_check(conn_matrix, node_list, jump_check_dir, c1) | |
| # 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. | |
| def jump_move(x_mat, x_jump, x_element, pos): | |
| jump_trace=x_mat[x_element[0]][x_element[1]] | |
| if (x_jump[jump_trace][pos][1] == "left"): | |
| nxt_row=x_jump[jump_trace][pos][0][0] | |
| nxt_col=x_jump[jump_trace][pos][0][1] - 1 | |
| jmp_exec="left" | |
| elif (x_jump[jump_trace][pos][1] == "right"): | |
| nxt_row=x_jump[jump_trace][pos][0][0] | |
| nxt_col=x_jump[jump_trace][pos][0][1] + 1 | |
| jmp_exec="right" | |
| elif (x_jump[jump_trace][pos][1] == "up"): | |
| nxt_row=x_jump[jump_trace][pos][0][0] - 1 | |
| nxt_col=x_jump[jump_trace][pos][0][1] | |
| jmp_exec="up" | |
| elif (x_jump[jump_trace][pos][1] == "down"): | |
| nxt_row=x_jump[jump_trace][pos][0][0] + 1 | |
| nxt_col=x_jump[jump_trace][pos][0][1] | |
| jmp_exec="down" | |
| return [jmp_exec, nxt_row, nxt_col] | |
| def branch_jump(x_mat, x_jump, x_element): | |
| # 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. | |
| nxt_row=x_element[0] | |
| nxt_col=x_element[1] | |
| jump_exec="" | |
| if (len(x_mat[nxt_row][nxt_col])>3): | |
| if (x_mat[nxt_row][nxt_col].lower()[0:4] == "jump"): | |
| jump_trace=x_mat[nxt_row][nxt_col] | |
| if (x_jump[jump_trace][0][0] == [nxt_row, nxt_col]): | |
| jump_exec, nxt_row, nxt_col = \ | |
| jump_move(x_mat, x_jump, x_element, 1) | |
| elif (x_jump[jump_trace][1][0] == [nxt_row, nxt_col]): | |
| jump_exec, nxt_row, nxt_col = \ | |
| jump_move(x_mat, x_jump, x_element, 0) | |
| return [jump_exec, nxt_row, nxt_col] | |
| # Advancing one element in a branch | |
| # Checking for jump direction | |
| # to make sure we don't go back | |
| def branch_advance(x_mat, x_iter, nxt_elem, jmp_exec, x_rows, x_cols): | |
| nxt_row=nxt_elem[0] | |
| nxt_col=nxt_elem[1] | |
| # This temporary variable is to ensure, | |
| # two advancements don't take place in one loop. | |
| branch_proceed=0 | |
| if ((nxt_col>0) and branch_proceed==0): | |
| # We are trying to go left, so check if we didn't jump right. | |
| if (x_mat[nxt_row][nxt_col-1] != '' and jmp_exec!="right"): | |
| # Next check is if we are going backwards. | |
| if not ([nxt_row, nxt_col-1] in x_iter): | |
| nxt_col=nxt_col-1 | |
| branch_proceed=1 | |
| # Set jump to null after a movement. We can't go back anyway. | |
| jmp_exec="" | |
| if ((nxt_row>0) and branch_proceed==0): | |
| # We are trying to go up, so check if we didn't jump down. | |
| if (x_mat[nxt_row-1][nxt_col] != '' and jmp_exec!="down"): | |
| if not ([nxt_row-1, nxt_col] in x_iter): | |
| nxt_row=nxt_row-1 | |
| branch_proceed=1 | |
| # Set jump to null after a movement. We can't go back anyway. | |
| jmp_exec="" | |
| if ((nxt_col<x_cols-1) and branch_proceed==0): | |
| # We are trying to go right, so check if we didn't jump left. | |
| if (x_mat[nxt_row][nxt_col+1] != '' and jmp_exec!="left"): | |
| if not ([nxt_row, nxt_col+1] in x_iter): | |
| nxt_col=nxt_col+1 | |
| branch_proceed=1 | |
| # Set jump to null after a movement. We can't go back anyway. | |
| jmp_exec="" | |
| if ((nxt_row<x_rows-1) and branch_proceed==0): | |
| # We are trying to go down, so check if we didn't jump up. | |
| if (x_mat[nxt_row+1][nxt_col] != '' and jmp_exec!="up"): | |
| if not ([nxt_row+1, nxt_col] in x_iter): | |
| nxt_row=nxt_row+1 | |
| branch_proceed=1 | |
| # Set jump to null after a movement. We can't go back anyway. | |
| jmp_exec="" | |
| return [jmp_exec, nxt_row, nxt_col] | |
| 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. | |
| next_element = [next_node_row, next_node_column] | |
| jump_executed, next_node_row, next_node_column = \ | |
| branch_jump(conn_matrix, jump_matrix, next_element) | |
| branch_iter.append([next_node_row, next_node_column]) | |
| next_element = [next_node_row, next_node_column] | |
| jump_executed, next_node_row, next_node_column = \ | |
| branch_advance(conn_matrix, branch_iter, next_element, \ | |
| jump_executed, conn_rows, conn_columns) | |
| # 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]) | |
| next_elem_index=node_list.index([next_node_row, next_node_column]) | |
| branch_map[c1][next_elem_index].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) | |
| def find_loop(br_map, lp_list, lp_iter, br_map_rows, br_map_cols, elem, lp_count): | |
| # If an element exists, add it to loop iterator | |
| # Decrease the number of times that row can be visited. | |
| row=elem[0] | |
| col=elem[1] | |
| lp_iter.append([row, col]) | |
| br_map_rows[row]-=1 | |
| # Move down from that element | |
| loop_dir="down" | |
| # Update the loop row and column counter to that element | |
| loop_row=row | |
| loop_column=col | |
| print lp_iter | |
| print row, col | |
| print br_map_rows | |
| print br_map_cols | |
| 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(br_map[row][col])-1): | |
| lp_list.append([[row, col], [row, col]]) | |
| lp_count+=1 | |
| # Not using this block but I'll keep it anyway | |
| if (loop_dir == "right" and br_map_rows[loop_row]>0): | |
| c3=loop_column+1 | |
| while (c3<number_of_nodes): | |
| if br_map[loop_row][c3]: | |
| lp_iter.append([loop_row, c3]) | |
| last_elem_frst=br_map[lp_iter[0][0]][lp_iter[0][1]][0][-1] | |
| frst_elem_curr=br_map[loop_row][c3][0][0] | |
| last_elem_curr=br_map[loop_row][c3][0][-1] | |
| if (frst_elem_curr==last_elem_frst or \ | |
| last_elem_curr==last_elem_frst): | |
| loop_dir="end" | |
| br_map_rows[loop_row]-=1 | |
| else: | |
| loop_column=c3 | |
| loop_dir="down" | |
| br_map_rows[loop_row]-=1 | |
| break | |
| else: | |
| c3=c3+1 | |
| else: | |
| loop_dir="end" | |
| lp_iter=[] | |
| br_map_rows[loop_row]-=1 | |
| print lp_iter | |
| print loop_dir | |
| print br_map_rows | |
| print br_map_cols | |
| # Will be executed if we are moving down | |
| # and there are elements in that column | |
| if (loop_dir == "down" and br_map_cols[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 br_map[c3][loop_column]: | |
| # If so, add that element. | |
| lp_iter.append([c3, loop_column]) | |
| last_elem_frst=br_map[lp_iter[0][0]][lp_iter[0][1]][0][-1] | |
| frst_elem_curr=br_map[c3][loop_column][0][0] | |
| last_elem_curr=br_map[c3][loop_column][0][-1] | |
| # 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 (frst_elem_curr==last_elem_frst or \ | |
| last_elem_curr==last_elem_frst): | |
| # If so, loop has ended | |
| loop_dir="end" | |
| # Decrement the column counter | |
| # There is one element less in that column | |
| br_map_cols[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 | |
| br_map_cols[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" | |
| lp_iter=[] | |
| # The column counter still decrements | |
| # so that we don't come here again. | |
| br_map_cols[loop_column]-=1 | |
| print lp_iter | |
| print loop_dir | |
| print br_map_rows | |
| print br_map_cols | |
| # Will be executed if we are moving left | |
| # and there are elements in that row | |
| if (loop_dir == "left" and br_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 br_map[loop_row][c3]: | |
| # If so, add that element. | |
| lp_iter.append([loop_row, c3]) | |
| last_elem_frst=br_map[lp_iter[0][0]][lp_iter[0][1]][0][-1] | |
| frst_elem_curr=br_map[loop_row][c3][0][0] | |
| last_elem_curr=br_map[loop_row][c3][0][-1] | |
| # 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 (frst_elem_curr==last_elem_frst or \ | |
| last_elem_curr==last_elem_frst): | |
| # If so, loop has ended | |
| loop_dir="end" | |
| # Decrement the row counter | |
| # There is one element less in that row | |
| br_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 | |
| br_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" | |
| lp_iter=[] | |
| # The column counter still decrements | |
| # so that we don't come here again. | |
| br_map_rows[loop_row]-=1 | |
| print lp_iter | |
| print loop_dir | |
| print br_map_rows | |
| print br_map_cols | |
| # Will be executed if we are moving up | |
| # and there are elements in that column | |
| if (loop_dir == "up" and br_map_cols[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 br_map[c3][loop_column]: | |
| # If so, add that element. | |
| lp_iter.append([c3, loop_column]) | |
| last_elem_frst=br_map[lp_iter[0][0]][lp_iter[0][1]][0][-1] | |
| frst_elem_curr=br_map[c3][loop_column][0][0] | |
| last_elem_curr=br_map[c3][loop_column][0][-1] | |
| # 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 (frst_elem_curr==last_elem_frst or \ | |
| last_elem_curr==last_elem_frst): | |
| # If so, loop has ended | |
| loop_dir="end" | |
| # Decrement the column counter | |
| # There is one element less in that column | |
| br_map_cols[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 | |
| br_map_cols[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" | |
| lp_iter=[] | |
| # The column counter still decrements | |
| # so that we don't come here again. | |
| br_map_cols[loop_column]-=1 | |
| print lp_iter | |
| print loop_dir | |
| print br_map_rows | |
| print br_map_cols | |
| # End of while loop | |
| # "end" encountered | |
| if lp_iter: | |
| lp_count+=1 | |
| lp_list.append(lp_iter) | |
| lp_iter=[] | |
| return lp_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 | |
| 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]: | |
| loop_count=find_loop(branch_map, loop_list, loop_iter, \ | |
| branch_map_rows, branch_map_columns, [c1, c4], loop_count) | |
| print loop_count | |
| print loop_list |
No comments:
Post a Comment