nodes: 0, module; 1, function_definition; 2, function_name:_cuthill_mckee; 3, parameters; 4, block; 5, identifier:vertices; 6, identifier:vertices_neighbours; 7, expression_statement; 8, expression_statement; 9, expression_statement; 10, expression_statement; 11, expression_statement; 12, expression_statement; 13, while_statement; 14, return_statement; 15, comment:"""Yield the Cuthill-McKee order for a connected, undirected graph.
  
      `Wikipedia
      <https://en.wikipedia.org/wiki/Cuthill%E2%80%93McKee_algorithm>`_ provides
      a good introduction to the Cuthill-McKee algorithm. The RCM algorithm
      attempts to order vertices in a graph such that their adjacency matrix's
      bandwidth is reduced. In brief the RCM algorithm is a breadth-first search
      with the following tweaks:
  
      * The search starts from the vertex with the lowest degree.
      * Vertices discovered in each layer of the search are sorted by ascending
        order of their degree in the output.
  
      .. warning::
  
          This function must not be called on a disconnected or empty graph.
  
      Returns
      -------
      [vertex, ...]
      """; 16, assignment; 17, assignment; 18, assignment; 19, assignment; 20, assignment; 21, comparison_operator:len(cm_order) < len(vertices); 22, block; 23, identifier:cm_order; 24, identifier:vertices_degrees; 25, dictionary_comprehension; 26, identifier:peripheral_vertex; 27, call; 28, identifier:visited; 29, call; 30, identifier:cm_order; 31, list; 32, identifier:previous_layer; 33, call; 34, call; 35, call; 36, expression_statement; 37, for_statement; 38, expression_statement; 39, expression_statement; 40, expression_statement; 41, expression_statement; 42, pair; 43, for_in_clause; 44, identifier:min; 45, argument_list; 46, identifier:set; 47, argument_list; 48, identifier:peripheral_vertex; 49, identifier:set; 50, argument_list; 51, identifier:len; 52, argument_list; 53, identifier:len; 54, argument_list; 55, assignment; 56, identifier:vertex; 57, identifier:previous_layer; 58, block; 59, call; 60, call; 61, call; 62, assignment; 63, identifier:v; 64, call; 65, identifier:v; 66, identifier:vertices; 67, identifier:vertices; 68, keyword_argument; 69, list; 70, list; 71, identifier:cm_order; 72, identifier:vertices; 73, identifier:adjacent; 74, call; 75, expression_statement; 76, attribute; 77, argument_list; 78, attribute; 79, argument_list; 80, attribute; 81, argument_list; 82, identifier:previous_layer; 83, identifier:adjacent; 84, identifier:sum; 85, argument_list; 86, identifier:key; 87, parenthesized_expression; 88, identifier:peripheral_vertex; 89, identifier:peripheral_vertex; 90, identifier:set; 91, argument_list; 92, call; 93, identifier:adjacent; 94, identifier:difference_update; 95, identifier:visited; 96, identifier:visited; 97, identifier:update; 98, identifier:adjacent; 99, identifier:cm_order; 100, identifier:extend; 101, call; 102, call; 103, lambda; 104, attribute; 105, argument_list; 106, identifier:sorted; 107, argument_list; 108, identifier:itervalues; 109, argument_list; 110, lambda_parameters; 111, subscript; 112, identifier:adjacent; 113, identifier:update; 114, subscript; 115, identifier:adjacent; 116, keyword_argument; 117, subscript; 118, identifier:v; 119, identifier:vertices_degrees; 120, identifier:v; 121, identifier:vertices_neighbours; 122, identifier:vertex; 123, identifier:key; 124, parenthesized_expression; 125, identifier:vertices_neighbours; 126, identifier:v; 127, lambda; 128, lambda_parameters; 129, subscript; 130, identifier:v; 131, identifier:vertices_degrees; 132, identifier:v
code: def _cuthill_mckee(vertices, vertices_neighbours):
      """Yield the Cuthill-McKee order for a connected, undirected graph.
  
      `Wikipedia
      <https://en.wikipedia.org/wiki/Cuthill%E2%80%93McKee_algorithm>`_ provides
      a good introduction to the Cuthill-McKee algorithm. The RCM algorithm
      attempts to order vertices in a graph such that their adjacency matrix's
      bandwidth is reduced. In brief the RCM algorithm is a breadth-first search
      with the following tweaks:
  
      * The search starts from the vertex with the lowest degree.
      * Vertices discovered in each layer of the search are sorted by ascending
        order of their degree in the output.
  
      .. warning::
  
          This function must not be called on a disconnected or empty graph.
  
      Returns
      -------
      [vertex, ...]
      """
      vertices_degrees = {v: sum(itervalues(vertices_neighbours[v]))
                          for v in vertices}
  
      peripheral_vertex = min(vertices, key=(lambda v: vertices_degrees[v]))
  
      visited = set([peripheral_vertex])
      cm_order = [peripheral_vertex]
      previous_layer = set([peripheral_vertex])
      while len(cm_order) < len(vertices):
          adjacent = set()
          for vertex in previous_layer:
              adjacent.update(vertices_neighbours[vertex])
          adjacent.difference_update(visited)
  
          visited.update(adjacent)
          cm_order.extend(sorted(adjacent, key=(lambda v: vertices_degrees[v])))
          previous_layer = adjacent
  
      return cm_order