from java.lang import Integer
def find_all_paths(start, end, path=[]):
    path = path + [start]
    if start == end:
        return [path]
    if start not in g.nodes:
        return []
    paths = []
    adj = start.getNeighbors()
    for node in adj:
        if node not in path:
            newpaths = find_all_paths(node, end, path)
            for newpath in newpaths:
                paths.append(newpath)
    return paths

def find_shortest_path(start, end, path=[]):
    path = path + [start]
    if start == end:
        return path
    if start not in g.nodes:
        return None
    shortest = None
    adj = start.getNeighbors()
    for node in adj:
        if node not in path:
            newpath = find_shortest_path(node, end, path)
            if newpath:
                if not shortest or len(newpath) < len(shortest):
                    shortest = newpath
    return shortest

def findDiameter():
    diameter = 0
    result = []
    for node in g.nodes:
        for nodeTwo in g.nodes:
            path = node.unweightedShortestPath(nodeTwo)
            length = len(path)
            if(length > diameter):
                diameter = length
                result = path

    return result

def dfs(u):
  stack = [] 
  if(Node.getField("visited") == None):
      addNodeField("visited",Types.BOOLEAN,0) # add visited field if necessary
  else:
      for node in g.nodes:
          node.visited = 1
  stack.append(u) # append to back works as push
  while len(stack) > 0: 
    v = stack.pop() 
    v.visited = true
    adj = v.getNeighbors()
    for w in adj:
      if not w.visited:
        stack.append(w)
        
def bfs(u):
  queue = []
  maxDist = len(g.nodes)   # no path can be longer than the number of vertices
  if(Node.getField("dist") == None):
      addNodeField("dist",Types.INTEGER,Integer(maxDist + 1))
  else:
      for node in g.nodes:
          node.dist = maxDist +1
  queue.append(u)
  u.dist = 0
  while len(queue) > 0:
    v = queue.pop(0)       # pop item from front of queue (dequeue)
    adj = v.getNeighbors()
    for w in adj:
        if(len(v->w) > 0 or len(v-w) >0):
            if(w.dist == maxDist +1):
                queue.append(w)
                w.dist = v.dist + 1