#!/usr/bin/python3
from pygraph import *
from pygraph.readwrite import markup
from sys import argv
gr = markup.read(open(argv[1]).read())

# Return maximum depth of n, from root
def depth(root, n):
  if root + "_depth" in gr.node_attributes(n):
    # dependency loop :/ Avoid looping
    return 0
  gr.add_node_attribute(n, root + "_depth")
  d = -1
  for n2 in gr.neighbors(n):
    subdepth = depth(root, n2)
    if subdepth > d:
      d = subdepth
  return d + 1

# Return the number of nodes below n, from root, and an example of path with most nodes
def patriarchy(root, n):
  if root + "_patriarchy" in gr.node_attributes(n):
    # dependency loop :/ Avoid looping
    return (1, [n])
  gr.add_node_attribute(n, root + "_patriarchy")
  p = 1
  maxpat = 0
  subpath = [ ]
  for n2 in gr.neighbors(n):
    pat, spath = patriarchy(root, n2)
    if pat > maxpat:
      maxpat = pat
      subpath = spath
    p += pat
  return p, ([ n ] + subpath)

# Compute an example path below n, from root, with longest depth
def path(root, n):
  if root + "_path" in gr.node_attributes(n):
    # dependency loop :/ Avoid looping
    return (0, [n])
  gr.add_node_attribute(n, root + "_path")
  d = -1
  p = [ n ]
  for n2 in gr.neighbors(n):
    (subdepth, subpath) = path(root, n2)
    if subdepth > d:
      d = subdepth
      p = [ n ] + subpath
  return (d + 1, p)

for i in gr.nodes():
  if (u'red', '') in gr.node_attributes(i) \
  or (u'OrangeRed', '') in gr.node_attributes(i) \
  or (u'black', '') in gr.node_attributes(i) \
  or (u'yellow', '') in gr.node_attributes(i) \
  or (u'magenta', '') in gr.node_attributes(i) \
  or (u'cyan', '') in gr.node_attributes(i) \
  or (u'orange', '') in gr.node_attributes(i) \
  or (u'purple', '') in gr.node_attributes(i) \
  or (u'lightgrey', '') in gr.node_attributes(i) \
  or (u'burlywood', '') in gr.node_attributes(i) \
  or (u'palegreen', '') in gr.node_attributes(i) \
  or (u'green', '') in gr.node_attributes(i) \
    :
    pat,path = patriarchy(i, i)
    print(pat, "	", depth(i, i), "	", i, "		", path)