python 3.x - Issue with canvas.find_overlapping() -
my program straightforward: user clicks , makes square, if squares user has made squares touch or overlap become red, if not remain clear. question this: how miss using method or using right method program?
edit: program make rectangles no problem: seem unable use canvas.find_overlapping determine if of rectangles connected. missing in code?
from tkinter import * # import tkinter graph import graph def add(event): squares.append([event.x, event.y]) repaint() def repaint(): canvas.delete(all) if len(squares) == 0: return # nothing paint tags = 0 [x, y] in squares: canvas.create_rectangle(x - side, y - side, x + side, y + side, tags = "point") tags += 1 # build edges edges = [] in range(len(squares)): x = canvas.find_overlapping(squares[i][0]-side, squares[i][1]-side, squares[i][0]+side , squares[i][1]+side) print(x) j in range(i + 1, len(squares)): if squares[j] in x: edges.append([i, j]) edges.append([j, i]) graph = graph(squares, edges) tree = graph.dfs(0) isallsquaresconnected = \ len(squares) == tree.getnumberofverticesfound() if isallsquaresconnected: canvas.itemconfigure("point", fill = "red") window = tk() # create window window.title("connectedsquares") # set title width = 250 height = 200 side = 15 canvas = canvas(window, bg = "white", width = width, height = height) canvas.pack() # create 2-d list storing squares squares = [] canvas.bind("<button-1>", add) window.mainloop() # create event loop this graph program mentioned import
from queue import queue class graph: def __init__(self, vertices, edges): self.vertices = vertices self.neighbors = self.getadjacnecylists(edges) # return list of adjacency lists edges def getadjacnecylists(self, edges): neighbors = [] in range(len(self.vertices)): neighbors.append([]) # each element list in range(len(edges)): u = edges[i][0] v = edges[i][1] neighbors[u].append(v) # insert neighbor u return neighbors # return number of vertices in graph def getsize(self): return len(self.vertices) # return vertices in graph def getvertices(self): return self.vertices # return vertex @ specified index def getvertex(self, index): return self.vertices[index] # return index specified vertex def getindex(self, v): return self.vertices.index(v) # return neighbors of vertex specified index def getneighbors(self, index): return self.neighbors[index] # return degree specified vertex def getdegree(self, v): return len(self.neighbors[self.getindex(v)]) # print edges def printedges(self): u in range(0, len(self.neighbors)): print(self.getvertex(u) + " (" + str(u), end = "): ") j in range(len(self.neighbors[u])): print("(" + str(u) + ", " + str(self.neighbors[u][j]), end = ") ") print() # clear graph def clear(self): vertices = [] neighbors = [] # add vertex graph def addvertex(self, vertex): if not (vertex in self.vertices): self.vertices.append(vertex) self.neighbors.append([]) # add new empty adjacency list # add undirected edge graph def addedge(self, u, v): if u in self.vertices , v in self.vertices: indexu = self.getindex(u) indexv = self.getindex(v) if not (indexv in self.neighbors[indexu]): self.neighbors[indexu].append(indexv) # obtain dfs tree starting vertex v # discussed in section 16.6 def dfs(self, v): searchorders = [] parent = len(self.vertices) * [-1] # initialize parent[i] -1 # mark visited vertices isvisited = len(self.vertices) * [false] # recursively search self.dfshelper(v, parent, searchorders, isvisited) # return search tree return tree(v, parent, searchorders, self.vertices) # recursive method dfs search def dfshelper(self, v, parent, searchorders, isvisited): # store visited vertex searchorders.append(v) isvisited[v] = true # vertex v visited in self.neighbors[v]: if not isvisited[i]: parent[i] = v # parent of vertex v # recursive search self.dfshelper(i, parent, searchorders, isvisited) # starting bfs search vertex v # discussed in section 16.7 def bfs(self, v): searchorders = [] parent = len(self.vertices) * [-1] # initialize parent[i] -1 queue = queue() # queue class defined in chapter 12 isvisited = len(self.vertices) * [false] queue.enqueue(v) # enqueue v isvisited[v] = true # mark visited while not queue.isempty(): u = queue.dequeue() # dequeue u searchorders.append(u) # u searched w in self.neighbors[u]: if not isvisited[w]: queue.enqueue(w) # enqueue w parent[w] = u # parent of w u isvisited[w] = true # mark visited return tree(v, parent, searchorders, self.vertices) # tree class discussed in section 16.5 class tree: def __init__(self, root, parent, searchorders, vertices): self.root = root # root of tree # store parent of each vertex in list self.parent = parent # store search order in list self.searchorders = searchorders self.vertices = vertices # vertices of graph # return root of tree def getroot(self): return self.root # return parent of vertex v def getparent(self, index): return self.parent[index] # return array representing search order def getsearchorders(self): return self.searchorders # return number of vertices found def getnumberofverticesfound(self): return len(self.searchorders) # return path of vertices vertex index root def getpath(self, index): path = [] while index != -1: path.append(self.vertices[index]) index = self.parent[index] return path # print path root vertex v def printpath(self, index): path = self.getpath(index) print("a path " + str(self.vertices[self.root]) + " " + str(self.vertices[index]), end = ": ") in range(len(path) - 1, -1, -1): print(path[i], end = " ") # print whole tree def printtree(self): print("root is: " + str(self.vertices[self.root])) print("edges: ", end = "") in range(len(self.parent)): if self.parent[i] != -1: # display edge print("(" + str(self.vertices[self.parent[i]]) + ", " + str(self.vertices[i]), end = ") ") print()
the change had apparently needed determine length of x , if length of x == 1 wouldn't connected.
def repaint(): canvas.delete(all) if len(squares) == 0: return # nothing paint tags = 0 [x, y] in squares: canvas.create_rectangle(x - side, y - side, x + side, y + side, tags = "point") tags += 1 # build edges edges = [] isallsquaresconnected = true in range(len(squares)): x = canvas.find_overlapping(squares[i][0]-side, squares[i][1]-side, squares[i][0]+side , squares[i][1]+side) j in range(i + 1, len(squares)): if len(x) > 1: edges.append([i, j]) edges.append([j, i]) else: isallsquaresconnected = false if isallsquaresconnected: canvas.itemconfigure("point", fill = "red")
Comments
Post a Comment