Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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 of
consecutive edges) currently in the graph at any point.

The edges will be labelled as roads, connecting 2 nodes. These
edges are undirected.

The nodes will not be constrained here, so any start- or end-point
of an edge will be called a node.

Some nodes will occassionally be called settlements, but it
doesn'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()
share|improve this question

1 Answer 1

up vote 3 down vote accepted

1. Comments on your code

  1. I 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?

  2. 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.

  3. 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.

  4. It's a good idea for your classes to inherit from object so that they are portable between Python 2 and Python 3.

  5. Why not make canvas an instance member so that you don't have to pass it around?

  6. Code like

    c = ["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 code

The 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 defaultdict
from itertools import permutations
from 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 longest

class 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 g

if __name__ == "__main__":
    root = Tk()
    GraphDisplay(root, example_graph())
    root.mainloop()
share|improve this answer
    
A path is a sequence of nodes, not necessarily 2. Thus it differs from an edge by being "longer". I agree with your other criticisms. I think an adjacency list is a good idea, as is moving the drawing portion to a different class, and storing the nodes. –  BlackSheep Jan 29 '13 at 13:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.