patternpythonMinor

Evaluating longest path

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

longestpathevaluating

Problem

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", "bl

Solution

Comments on your code

-
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?

-
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 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()

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  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()

Code Snippets

c = ["red", "orange",  "purple", "cyan", "green", "grey", "lightgreen", "yellow", "blue"]

_colors = "red orange purple cyan green grey lightgreen yellow blue".split()

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()

Context

StackExchange Code Review Q#21014, answer score: 3

Revisions (0)

No revisions yet.