# Evaluating longest path

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

-

## 1 Answer

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

-
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