nodes: 0, module; 1, function_definition; 2, function_name:order_upgrades; 3, parameters; 4, block; 5, identifier:self; 6, identifier:upgrades; 7, default_parameter; 8, expression_statement; 9, expression_statement; 10, expression_statement; 11, comment:# Removed already applied upgrades (assumes all dependencies prior to; 12, comment:# this upgrade has been applied).; 13, for_statement; 14, comment:# Check for missing dependencies; 15, for_statement; 16, comment:# Nodes with no incoming edges; 17, expression_statement; 18, expression_statement; 19, while_statement; 20, for_statement; 21, return_statement; 22, identifier:history; 23, None; 24, comment:"""Order upgrades according to their dependencies.
  
          (topological sort using
          Kahn's algorithm - http://en.wikipedia.org/wiki/Topological_sorting).
  
          :param upgrades: Dict of upgrades
          :param history: Dict of applied upgrades
          """; 25, assignment; 26, assignment; 27, identifier:node_id; 28, call; 29, block; 30, pattern_list; 31, call; 32, block; 33, assignment; 34, assignment; 35, identifier:start_nodes; 36, comment:# Append node_n to list (it has no incoming edges); 37, block; 38, pattern_list; 39, call; 40, block; 41, call; 42, identifier:history; 43, boolean_operator; 44, pattern_list; 45, call; 46, attribute; 47, argument_list; 48, expression_statement; 49, while_statement; 50, identifier:node_id; 51, identifier:depends_on; 52, attribute; 53, argument_list; 54, for_statement; 55, identifier:start_nodes; 56, list_comprehension; 57, identifier:topo_order; 58, list; 59, expression_statement; 60, expression_statement; 61, comment:# For each node m with and edge from n to m; 62, for_statement; 63, identifier:node; 64, identifier:edges; 65, attribute; 66, argument_list; 67, if_statement; 68, identifier:map; 69, argument_list; 70, identifier:history; 71, dictionary; 72, identifier:graph_incoming; 73, identifier:graph_outgoing; 74, attribute; 75, argument_list; 76, identifier:six; 77, identifier:iterkeys; 78, identifier:history; 79, assignment; 80, identifier:start_nodes; 81, block; 82, identifier:six; 83, identifier:iteritems; 84, identifier:graph_incoming; 85, identifier:d; 86, identifier:depends_on; 87, block; 88, identifier:x; 89, for_in_clause; 90, if_clause; 91, assignment; 92, call; 93, identifier:node_m; 94, subscript; 95, comment:# Remove the edge n to m; 96, block; 97, identifier:six; 98, identifier:iteritems; 99, identifier:graph_incoming; 100, identifier:edges; 101, block; 102, lambda; 103, identifier:topo_order; 104, identifier:self; 105, identifier:_create_graph; 106, identifier:upgrades; 107, identifier:history; 108, identifier:start_nodes; 109, list; 110, expression_statement; 111, comment:# Remove from direct dependents; 112, try_statement; 113, comment:# Remove all prior dependencies; 114, if_statement; 115, if_statement; 116, identifier:x; 117, call; 118, comparison_operator:len(graph_incoming[x]) == 0; 119, identifier:node_n; 120, call; 121, attribute; 122, argument_list; 123, identifier:graph_outgoing; 124, identifier:node_n; 125, expression_statement; 126, comment:# If m has no incoming edges, add it to start_nodes.; 127, if_statement; 128, raise_statement; 129, lambda_parameters; 130, subscript; 131, identifier:node_id; 132, assignment; 133, block; 134, except_clause; 135, comparison_operator:node in graph_incoming; 136, comment:# Get dependencies, remove node, and recursively; 137, comment:# remove all dependencies.; 138, block; 139, comparison_operator:d not in graph_incoming; 140, block; 141, attribute; 142, argument_list; 143, call; 144, integer:0; 145, attribute; 146, argument_list; 147, identifier:topo_order; 148, identifier:append; 149, identifier:node_n; 150, assignment; 151, not_operator; 152, block; 153, call; 154, identifier:x; 155, identifier:upgrades; 156, identifier:x; 157, identifier:node; 158, call; 159, for_statement; 160, identifier:KeyError; 161, block; 162, identifier:node; 163, identifier:graph_incoming; 164, expression_statement; 165, comment:# Add dependencies to check; 166, for_statement; 167, delete_statement; 168, identifier:d; 169, identifier:graph_incoming; 170, raise_statement; 171, identifier:six; 172, identifier:iterkeys; 173, identifier:graph_incoming; 174, identifier:len; 175, argument_list; 176, identifier:start_nodes; 177, identifier:pop; 178, subscript; 179, list_comprehension; 180, subscript; 181, expression_statement; 182, identifier:RuntimeError; 183, argument_list; 184, attribute; 185, argument_list; 186, identifier:d; 187, subscript; 188, block; 189, expression_statement; 190, assignment; 191, identifier:d; 192, identifier:depends_on; 193, block; 194, subscript; 195, call; 196, subscript; 197, identifier:graph_incoming; 198, identifier:node_m; 199, identifier:x; 200, for_in_clause; 201, if_clause; 202, identifier:graph_incoming; 203, identifier:node_m; 204, call; 205, binary_operator:"The upgrades have at least one cyclic "
                                     "dependency involving %s." % node; 206, identifier:start_nodes; 207, identifier:pop; 208, identifier:graph_outgoing; 209, identifier:node; 210, expression_statement; 211, call; 212, identifier:depends_on; 213, subscript; 214, expression_statement; 215, expression_statement; 216, identifier:graph_incoming; 217, identifier:node; 218, identifier:RuntimeError; 219, argument_list; 220, identifier:graph_incoming; 221, identifier:x; 222, identifier:x; 223, subscript; 224, comparison_operator:x != node_n; 225, attribute; 226, argument_list; 227, concatenated_string; 228, identifier:node; 229, assignment; 230, attribute; 231, argument_list; 232, identifier:graph_incoming; 233, identifier:node; 234, assignment; 235, call; 236, binary_operator:"Upgrade %s depends on an unknown"
                                         " upgrade %s" % (node_id, d); 237, identifier:graph_incoming; 238, identifier:node_m; 239, identifier:x; 240, identifier:node_n; 241, identifier:start_nodes; 242, identifier:append; 243, identifier:node_m; 244, string:"The upgrades have at least one cyclic "; 245, string:"dependency involving %s."; 246, subscript; 247, list_comprehension; 248, identifier:warnings; 249, identifier:warn; 250, binary_operator:"Ghost upgrade %s detected" % node; 251, subscript; 252, list_comprehension; 253, attribute; 254, argument_list; 255, concatenated_string; 256, tuple; 257, identifier:graph_incoming; 258, identifier:d; 259, identifier:x; 260, for_in_clause; 261, if_clause; 262, string:"Ghost upgrade %s detected"; 263, identifier:node; 264, identifier:graph_outgoing; 265, identifier:d; 266, identifier:x; 267, for_in_clause; 268, if_clause; 269, identifier:start_nodes; 270, identifier:append; 271, identifier:d; 272, string:"Upgrade %s depends on an unknown"; 273, string:" upgrade %s"; 274, identifier:node_id; 275, identifier:d; 276, identifier:x; 277, subscript; 278, comparison_operator:x != node; 279, identifier:x; 280, subscript; 281, comparison_operator:x != node; 282, identifier:graph_incoming; 283, identifier:d; 284, identifier:x; 285, identifier:node; 286, identifier:graph_outgoing; 287, identifier:d; 288, identifier:x; 289, identifier:node
code: def order_upgrades(self, upgrades, history=None):
          """Order upgrades according to their dependencies.
  
          (topological sort using
          Kahn's algorithm - http://en.wikipedia.org/wiki/Topological_sorting).
  
          :param upgrades: Dict of upgrades
          :param history: Dict of applied upgrades
          """
          history = history or {}
          graph_incoming, graph_outgoing = self._create_graph(upgrades, history)
  
          # Removed already applied upgrades (assumes all dependencies prior to
          # this upgrade has been applied).
          for node_id in six.iterkeys(history):
              start_nodes = [node_id, ]
              while start_nodes:
                  node = start_nodes.pop()
                  # Remove from direct dependents
                  try:
                      for d in graph_outgoing[node]:
                          graph_incoming[d] = [x for x in graph_incoming[d]
                                               if x != node]
                  except KeyError:
                      warnings.warn("Ghost upgrade %s detected" % node)
  
                  # Remove all prior dependencies
                  if node in graph_incoming:
                      # Get dependencies, remove node, and recursively
                      # remove all dependencies.
                      depends_on = graph_incoming[node]
  
                      # Add dependencies to check
                      for d in depends_on:
                          graph_outgoing[d] = [x for x in graph_outgoing[d]
                                               if x != node]
                          start_nodes.append(d)
  
                      del graph_incoming[node]
  
          # Check for missing dependencies
          for node_id, depends_on in six.iteritems(graph_incoming):
              for d in depends_on:
                  if d not in graph_incoming:
                      raise RuntimeError("Upgrade %s depends on an unknown"
                                         " upgrade %s" % (node_id, d))
  
          # Nodes with no incoming edges
          start_nodes = [x for x in six.iterkeys(graph_incoming)
                         if len(graph_incoming[x]) == 0]
          topo_order = []
  
          while start_nodes:
              # Append node_n to list (it has no incoming edges)
              node_n = start_nodes.pop()
              topo_order.append(node_n)
  
              # For each node m with and edge from n to m
              for node_m in graph_outgoing[node_n]:
                  # Remove the edge n to m
                  graph_incoming[node_m] = [x for x in graph_incoming[node_m]
                                            if x != node_n]
                  # If m has no incoming edges, add it to start_nodes.
                  if not graph_incoming[node_m]:
                      start_nodes.append(node_m)
  
          for node, edges in six.iteritems(graph_incoming):
              if edges:
                  raise RuntimeError("The upgrades have at least one cyclic "
                                     "dependency involving %s." % node)
  
          return map(lambda x: upgrades[x], topo_order)