tarjan's strongly connected componen

tarjan.py

class Tarjan(object):
  def __init__(self, edges):
    tmp_vs = []
    self.edges = edges
    vertice_dict = {}
    for edge in edges:
      if edge[0] not in vertice_dict.keys():
        vertice_dict[edge[0]] = {"id": edge[0]}
      if edge[1] not in vertice_dict.keys():
        vertice_dict[edge[1]] = {"id": edge[1]}
    self.vertices = vertice_dict

  def determine_strongly_connected(self):
    self.stack = []
    self.scc = []
    self.current_depth = 0
    vertice_keys = self.vertices.keys()
    for key in self.vertices.keys():
      if "depth" not in self.vertices[key]:
        self.strongconnect(self.vertices[key])

  def strongconnect(self, vertex):
    vertex["depth"] = self.current_depth
    vertex["low_link"] = self.current_depth
    self.current_depth += 1
    self.stack.append(vertex)
    vertex["onStack"] = True
    edges_for_vertex = self.get_edges_for_vertex(vertex)
    for edge in edges_for_vertex:
      if not "depth" in edge:
        self.strongconnect(edge)
        edge = self.vertices[edge["id"]]
        vertex["low_link"] = min(vertex["low_link"], edge["low_link"])
      elif edge["onStack"]:
        vertex["low_link"] = min(vertex["low_link"], edge["depth"])
    if vertex["low_link"] == vertex["depth"]:
      connected_component=[]
      w = None
      while True:
        successor = self.stack.pop()
        connected_component.append(successor)
        if successor == vertex: break
      self.scc.append(connected_component)
    else:
      print "not root: %s" % vertex

  def get_edges_for_vertex(self, vertex):
    edges = []
    for edge in self.edges:
      v = self.vertices[edge[0]]
      w = self.vertices[edge[1]]
      if vertex["id"] == v["id"]:
        edges.append(w)
    return edges

test_data = [[1,0],[0,2],[2,1],[0,3],[3,4]]
t = Tarjan(test_data)

t.determine_strongly_connected()
assert len(t.scc) == 3

# test_data2 = [[14,11],[11,12],[12,13],[12,14],[13,14],[6,13],[6,5],[5,6],[5,12],[3,6],[5,16]]
#
# expected output according to http://www.columbia.edu/~cs2035/courses/csor4231.F11/scc.pdf
# [[{'depth': 5, 'id': 12, 'low_link': 2, 'onStack': True},
#   {'depth': 4, 'id': 11, 'low_link': 2, 'onStack': True},
#   {'depth': 3, 'id': 14, 'low_link': 2, 'onStack': True},
#   {'depth': 2, 'id': 13, 'low_link': 2, 'onStack': True}],
#  [{'depth': 7, 'id': 16, 'low_link': 7, 'onStack': True}],
#  [{'depth': 6, 'id': 5, 'low_link': 1, 'onStack': True},
#   {'depth': 1, 'id': 6, 'low_link': 1, 'onStack': True}],
#  [{'depth': 0, 'id': 3, 'low_link': 0, 'onStack': True}]]