Here is a program which keeps track of the longest path in a graph. I think it can be written much better.from Tkinter import *'''This program tries to compute the longest path (largest number ofconsecutive edges) currently in the graph at any point.The edges will be labelled as roads, connecting 2 nodes. Theseedges are undirected.The nodes will not be constrained here, so any start- or end-pointof an edge will be called a node.Some nodes will occassionally be called settlements, but itdoesn't mean anything special here.'''class A():    '''The main class, groups all functions.'''    def create_roads(self):        '''Create the roads that will later be added.'''        # first settlement        s0 = (100, 100)        # second settlement        s1 = (100, 300)        self._road_index = 0        self._roads = [           # G1           # one way from s0           (s0, (150, 100)),           # other way from s0           (s0, (50, 100)),           # extend from 150           #((150, 100), (200, 100)),           # branch at 150           ((150, 100), (200, 150)),           # extend branch           #((200, 150), (250, 150)),           # extend other side           ((50, 100), (100, 150)),           # discontinuous site (G2)           #(s1, (150, 250)),           # extend G2           ((150, 250), (100, 200)),           ((100, 200), (50, 150)),           # branch off G2           ((150, 250), (200, 250)),           ((200, 250), (250, 200)),           # join G2 to G1 at endpoints           ((50, 150), (100, 150)),           # join G2 to G1 at middle           ((250, 200), (200, 150)),           # another branch off G2           ((200, 250), (250, 250))        ]    def draw_paths(self, canvas):        '''Draw all the paths as a series of roads.        Each path is represented by a different color.'''        i = 0        c = [red, orange,  purple, cyan, green, grey, lightgreen, yellow, blue]        spacing = 3        for path in self._paths:            i += 1            for road_i in range(len(path) - 1):                startpt = (path[road_i][0], path[road_i][1] + i * spacing)                endpt = (path[road_i + 1][0], path[road_i + 1][1] + i * spacing)                self.draw_road(startpt, endpt, canvas, c[i % len(c)])        print **** Drawing ****        for p in self._paths:            print p        print **** End drawing ****    def draw_road(self, v1, v2, canvas, c=red):        '''Draw a road between v1 and v2.'''        t = road if c == red else path        canvas.create_line(v1[0], v1[1], v2[0], v2[1], fill=c, width=1.5, tags=t)    def draw_node(self, v, canvas):        '''Draw a node at v.'''        r = 10        canvas.create_oval(v[0] + r, v[1] + r, v[0] - r, v[1] - r, fill=black)    def draw(self, canvas):        '''Draw the path-node system - i.e. the graph.'''        for v1, v2 in self._roads:            self.draw_road(v1, v2, canvas)            self.draw_node(v1, canvas)            self.draw_node(v2, canvas)        self.draw_paths(canvas)    def add_next_path(self, canvas):        '''Show the addition of another path.'''        if self._road_index == len(self._roads):            print No        else:            for item in canvas.find_withtag(path):                canvas.delete(item)            self.add_road(*self._roads[self._road_index])            self.draw(canvas)            self._road_index += 1    def add_path_buttons(self, canvas):        '''Add a button to control addition of new paths.'''        f = lambda : self.add_next_path(canvas)        self._path_button = Button(            self._root,            text=Add path,            command=f        )        # more or less arbitrary placement        canvas.create_window(100, 500, window=self._path_button, anchor=S)    def print_debug(self, msg):        '''If the debug flag is on, print the message.'''        if self._debug:            print msg    def __init__(self, root, debug=True):        '''Create a new app.'''        # save variables        self._root = root        self._debug = debug        self._path_end = {} # maps endpoints (second coordinate) to path        self._path_start = {} # maps startpoints (first coordinate) to path        self._paths = [] # list of all paths        self._cycles = [] # the list of all paths that are cycles ; currently not used        self.create_roads()        # everything will be drawn on the canvas        c = Canvas(self._root, width=600, height=600)        c.pack()        self.add_path_buttons(c) # buttons are hooked to the canvas        self.draw(c) # draw everything except the buttons    def branch(self, branchpt, new_node, path):        '''New road is added - road = (branchpt, new_node)        path - the existing path, intersecting with road        branchpt - the intersection of road and path        new_node - the other node in road        '''        if path.count(branchpt) == 0:            #TODO this should never happen            return        elif path.count(branchpt) == 2:            # means cycle, so gets extra tricky ; not sure what to do here            pass        i = path.index(branchpt)        if i == 0: # insert road at beginning            if path[0] in self._path_start and len(self._path_start[path[0]]) > 0:                self._path_start[path[0]].remove(path) # remove old starting point                if len(self._path_start[path[0]]) == 0:                    del(self._path_start[path[0]])            else:                # should never be the case, because self._path_start should always be synced                pass            path.insert(0, new_node) # alter the road            # add new starting point            if new_node not in self._path_start:                self._path_start[new_node] = []            self._path_start[new_node].append(path)        elif i == len(path) - 1: # means road added at the end            self._path_end[path[-1]].remove(path) # remove old ending point            # update            if len(self._path_end[path[-1]]) == 0:                del(self._path_end[path[-1]])            path.append(new_node) # update existing list            # update end point            if new_node not in self._path_end:                self._path_end[new_node] = []            self._path_end[new_node].append(path)        else: # somewhere in the middle            # first path goes from new_node through branchpt to path[-1]            p1 = [new_node] + path[i : ]            # second path goes from path[0] through branchpt to new_node            p2 = path[: i + 1] + [new_node]            # in this case, the original path stays            if path[0] == path[-1]:                # in the case of a cycle                self._new_paths.append(p1 + p2[1:-1])            else:                # simple branching                self._new_paths.append(p1)                self._new_paths.append(p2)    def update(self):        '''Update the memory with self._new_paths added.'''        while len(self._new_paths) > 0:            path = self._new_paths.pop()            print Adding path {}.format(path)            startpt = path[0]            endpt = path[-1]            if startpt not in self._path_start:                self._path_start[startpt] = []            if endpt not in self._path_end:                self._path_end[endpt] = []            self._path_start[startpt].append(path)            self._path_end[endpt].append(path)            self._paths.append(path)            if path[0] == path[-1]:                # if I created a new cycle, update cycle list.                self._cycles.append(path)    def add_road(self, a, b):        '''Add a road (a, b)        a and b are arbitrarily arranged endpoints representing nodes.        Only branch on one node per path so can consistently merge at the end.'''        self.print_debug('#' * 50) # dilineate between subsequent iterations        self._new_paths = []        added_a = added_b = False        for path in self._paths:            if a in path and not added_b:                # console output                self.print_debug(==> {}.format((a, b)))                self.print_debug(hit on {}.format(path))                # branch there, signal modified                self.branch(a, b, path)                added_a = True            elif b in path and not added_a:                # console output                print ==> {}.format((a, b))                print hit on {}.format(path)                # branch there, signal modified                self.branch(b, a, path)                added_b = True        if not added_a and not added_b:            self.print_debug(new disjoint: {}.format([a, b])) # helpful console message            self._new_paths.append([a, b]) # added it as a disjoint part to the graph        if len(self._new_paths) > 0:            self.update()        if added_a:            self.merge(b) # because a is the point connected        elif added_b:            self.merge(a) # because b is the point connected    def can_merge(self, path_1, path_2, mergept):        '''Checks if 2 paths can merge with each other.        Very basic check.'''        try:            i_1 = path_1.index(mergept)            i_2 = path_2.index(mergept)        except ValueError:            # mergept not found in one of the lists            return False        if i_1 == len(path_1) - 1:            path_1 = list(reversed(path_1))        if i_2 == len(path_2) - 1:            path_2 = list(reversed(path_2))        return path_1[0] == path_2[0] and path_1[1] != path_2[1]    def merge(self, mergept):        '''mergept is the point of the merge.        All roads with an endpoint here are subjects.            - we can combine any 2 roads that start from / end at b        '''        if mergept not in self._path_end:            self._path_end[mergept] = []        if mergept not in self._path_start:            self._path_start[mergept] = []        # every road that starts and ends at mergept        merge_list = self._path_end[mergept] + self._path_start[mergept]        merged = set([])        if len(merge_list) < 2:            return # cannot merge a single path        else:            self.print_debug(**** Starting merger ****)        for pi1, path_1 in enumerate(merge_list):            for pi2, path_2 in enumerate(merge_list):                # join these 2 paths under the right conditions                if self.can_merge(path_1, path_2, mergept) and (pi2, pi1) not in merged:                    merged.add((pi1, pi2))                    self.print_debug(Merging {} and {}.format(path_1, path_2))                    i_1 = path_1.index(mergept)                    i_2 = path_2.index(mergept)                    if i_1 == 0:                        path_1 = list(reversed(path_1))                    if i_2 == len(path_2) - 1:                        path_2 = list(reversed(path_2))                    p = path_1 + path_2[1:]                    self.print_debug(Added newly merged path {}.format(p))                    self._new_paths.append(p)        if len(merged) > 0:            # delete every path in merge_list            for p in merge_list:                self._path_start[p[0]].remove(p)                self._path_end[p[-1]].remove(p)                self._paths.remove(p)            self.update()        self.print_debug(**** End Merger ****)        # do this at the end as cleanup        if mergept in self._path_end and len(self._path_end[mergept]) == 0:            del(self._path_end[mergept])        if mergept in self._path_start and len(self._path_start[mergept]) == 0:            del(self._path_start[mergept])if __name__ == __main__:    root = Tk()    a = A(root)    root.mainloop()
Evaluating longest path
python;graph;tk
1. Comments on your codeI didn't understand everything that the code was trying to do. What's the difference between a road and a path? What's going on with all that merging and branching? Is it important, or is it just part of your longest-path-finding algorithm, and could be removed or replaced if you got a better algorithm?Putting all your functions in the same class is usually a sign that the class is doing too many things. Another sign of this is that you haven't managed to find a good name for the class. An easy way to refactor this program would be to have separate classes for the graph and the display.There are several standard ways to represent a graph, and in all of them, the nodes appear as elements in the data structure. But in your representation, nodes only appear in the form of the coordinates of endpoints of edges. This means, for example, that you end up drawing each node multiple times (once for each edge that it is incident to). This representation also makes it hard for you to find connections in the graph.Switching to a better representation, for example the adjacency list representation, would be a good idea.It's a good idea for your classes to inherit from object so that they are portable between Python 2 and Python 3.Why not make canvas an instance member so that you don't have to pass it around?Code likec = [red, orange,  purple, cyan, green, grey, lightgreen, yellow, blue]which is the same every time a method is called, could be moved out of the method into the class. Perhaps like this:_colors = red orange purple cyan green grey lightgreen yellow blue.split()2. Revised codeThe code below has separate classes for representing the graph and displaying it.  (Since I didn't understand what all that merging and branching code was for, I didn't try to improve it. If it was important, you'll have to figure out how to restore it and make it use the revised data structures.)The longest path is computed with a simple depth-first search over all paths in the graph. This takes time that's exponential in the size of the graph, but since the longest path problem is NP-hard, that's unfortunately the performance you have to live with. (If you were willing to accept a reasonably long path, but not necessarily the longest, then there would be ways to speed this up.)from collections import defaultdictfrom itertools import permutationsfrom Tkinter import *class Graph(object):    An undirected graph.    def __init__(self):        # Map from node to set of neighbours.        self.g = defaultdict(set)    def add_node(self, v):        Add a node `v`.        self.g[v].update()    def add_edge(self, v, w):        Add an undirected edge between `v` and `w`.        self.g[v].add(w)        self.g[w].add(v)    def iter_nodes(self):        Return an iterator over the nodes of the graph.        return iter(self.g)    def iter_edges(self):        Return an iterator over the edges of the graph.        for v in self.g:            for w in self.g[v]:                if v < w:                    yield v, w    def longest_path(self):        Return the longest path in the graph.        longest = []        visited = set()        path = []        def search(v):            visited.add(v)            path.append(v)            if len(path) > len(longest):                longest[:] = path[:]            for w in self.g[v]:                if w not in visited:                    search(w)            path.pop()            visited.remove(v)        for v in self.g:            search(v)        return longestclass GraphDisplay(object):    def __init__(self, root, graph, debug=True):        self._root = root        self._debug = debug        self._graph = graph        self._longest_path = graph.longest_path()        self._canvas = Canvas(self._root, width=600, height=600)        self._canvas.pack()        self.draw()    def draw_edge(self, v, w, fill='red'):        self._canvas.create_line(v[0], v[1], w[0], w[1], fill=fill, width=1.5)    def draw_node(self, v, r = 10, fill='black'):        self._canvas.create_oval(v[0] + r, v[1] + r, v[0] - r, v[1] - r,                                 fill=fill)    def draw(self):        for v, w in self._graph.iter_edges():            self.draw_edge(v, w)        for v, w in zip(self._longest_path, self._longest_path[1:]):            self.draw_edge(v, w, fill='green')        for v in self._graph.iter_nodes():            self.draw_node(v)def example_graph():    edges = [       ((100, 100), (150, 100)),       ((100, 100), ( 50, 100)),       ((150, 100), (200, 150)),       (( 50, 100), (100, 150)),       ((150, 250), (100, 200)),       ((100, 200), ( 50, 150)),       ((150, 250), (200, 250)),       ((200, 250), (250, 200)),       (( 50, 150), (100, 150)),       ((250, 200), (200, 150)),       ((200, 250), (250, 250)),    ]    g = Graph()    for v, w in edges:        g.add_edge(v, w)    return gif __name__ == __main__:    root = Tk()    GraphDisplay(root, example_graph())    root.mainloop()