from graph import Graph
def longestTreePath(g:Graph, root=None, parent=None):
'''Assumes g is a non-empty tree graph.
Initially called with parent None to do the
whole tree, when an initial root can be specified,
or first listed graph vertex is used.
In recursive calls need both subtree root vertex and
parent (excluded neighbor) specified.
Returns a 2-tuple of lengths inside the specified subtree:
length of the longest path,
length of the longest path ending at sub-tree'root
'''
if root is None:
root = g.vertices[0] #arbitrarily make first vetrex root
toRoot = [] # lengths of paths to root through neighbors
long = 0 # length of lonest internal path so far
for e in g.edges[root]:
if e.end == parent:
continue
insub, depth = longestTreePath(g, e.end, root)
long = max(insub, long) # longest full path in subtree
toRoot.append(depth + 1) #max length to e.end + edge to root
if len(toRoot) == 0:
return (0, 0)
if len(toRoot) == 1:
return (max(long, toRoot[0]), toRoot[0])
toRoot.sort() # two longest at end, Python index -1, -2
return (max(long, toRoot[-1] + toRoot[-2]), toRoot[-1])
def show(s, root=None):
print('initial string:', s)
g = Graph.fromStr(s, True)
if root is None:
root = g.vertices[0]
print('Graph made fully bi-directional:\n', g)
long, depth = longestTreePath(g, root)
print('longest path', long)
print('depth using root', root, 'is', depth)
show('A:ZBCD D:EFGH G:IJK J:LM H:NP P:Q')
show('A:BCD D:EFGH G:IJK J:LM H:NP P:Q','B')
show('A:BCD D:EFGH G:IJK J:LM H:NP P:Q','D')