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