<s> """<STR_LIT>""" <EOL> from collections import deque <EOL> from operator import itemgetter <EOL> import networkx as nx <EOL> from . . utils import arbitrary_element <EOL> __author__ = """<STR_LIT:\n>""" . join ( [ '<STR_LIT>' ] ) <EOL> __all__ = [ '<STR_LIT>' , <EOL> '<STR_LIT>' ] <EOL> def cuthill_mckee_ordering ( G , heuristic = None ) : <EOL> """<STR_LIT>""" <EOL> for c in nx . connected_components ( G ) : <EOL> for n in connected_cuthill_mckee_ordering ( G . subgraph ( c ) , heuristic ) : <EOL> yield n <EOL> def reverse_cuthill_mckee_ordering ( G , heuristic = None ) : <EOL> """<STR_LIT>""" <EOL> return reversed ( list ( cuthill_mckee_ordering ( G , heuristic = heuristic ) ) ) <EOL> def connected_cuthill_mckee_ordering ( G , heuristic = None ) : <EOL> if heuristic is None : <EOL> start = pseudo_peripheral_node ( G ) <EOL> else : <EOL> start = heuristic ( G ) <EOL> visited = { start } <EOL> queue = deque ( [ start ] ) <EOL> while queue : <EOL> parent = queue . popleft ( ) <EOL> yield parent <EOL> nd = sorted ( list ( G . degree ( set ( G [ parent ] ) - visited ) ) , <EOL> key = itemgetter ( <NUM_LIT:1> ) ) <EOL> children = [ n for n , d in nd ] <EOL> visited . update ( children ) <EOL> queue . extend ( children ) <EOL> def pseudo_peripheral_node ( G ) : <EOL> u = arbitrary_element ( G ) <EOL> lp = <NUM_LIT:0> <EOL> v = u <EOL> while True : <EOL> spl = dict ( nx . shortest_path_length ( G , v ) ) <EOL> l = max ( spl . values ( ) ) <EOL> if l <= lp : <EOL> break <EOL> lp = l <EOL> farthest = ( n for n , dist in spl . items ( ) if dist == l ) <EOL> v , deg = min ( G . degree ( farthest ) , key = itemgetter ( <NUM_LIT:1> ) ) <EOL> return v </s>
