<s> """<STR_LIT>""" <EOL> from sys import getrecursionlimit , setrecursionlimit <EOL> def accessibility ( graph ) : <EOL> """<STR_LIT>""" <EOL> recursionlimit = getrecursionlimit ( ) <EOL> setrecursionlimit ( max ( len ( graph . nodes ( ) ) * <NUM_LIT:2> , recursionlimit ) ) <EOL> accessibility = { } <EOL> for each in graph : <EOL> access = { } <EOL> _dfs ( graph , access , <NUM_LIT:1> , each ) <EOL> accessibility [ each ] = list ( access . keys ( ) ) <EOL> setrecursionlimit ( recursionlimit ) <EOL> return accessibility <EOL> def mutual_accessibility ( graph ) : <EOL> """<STR_LIT>""" <EOL> recursionlimit = getrecursionlimit ( ) <EOL> setrecursionlimit ( max ( len ( graph . nodes ( ) ) * <NUM_LIT:2> , recursionlimit ) ) <EOL> mutual_access = { } <EOL> stack = [ ] <EOL> low = { } <EOL> def visit ( node ) : <EOL> if node in low : <EOL> return <EOL> num = len ( low ) <EOL> low [ node ] = num <EOL> stack_pos = len ( stack ) <EOL> stack . append ( node ) <EOL> for successor in graph . neighbors ( node ) : <EOL> visit ( successor ) <EOL> low [ node ] = min ( low [ node ] , low [ successor ] ) <EOL> if num == low [ node ] : <EOL> component = stack [ stack_pos : ] <EOL> del stack [ stack_pos : ] <EOL> component . sort ( ) <EOL> for each in component : <EOL> mutual_access [ each ] = component <EOL> for item in component : <EOL> low [ item ] = len ( graph ) <EOL> for node in graph : <EOL> visit ( node ) <EOL> setrecursionlimit ( recursionlimit ) <EOL> return mutual_access <EOL> def connected_components ( graph ) : <EOL> """<STR_LIT>""" <EOL> recursionlimit = getrecursionlimit ( ) <EOL> setrecursionlimit ( max ( len ( graph . nodes ( ) ) * <NUM_LIT:2> , recursionlimit ) ) <EOL> visited = { } <EOL> count = <NUM_LIT:1> <EOL> for each in graph : <EOL> if ( each not in visited ) : <EOL> _dfs ( graph , visited , count , each ) <EOL> count = count + <NUM_LIT:1> <EOL> setrecursionlimit ( recursionlimit ) <EOL> return visited <EOL> def _dfs ( graph , visited , count , node ) : <EOL> """<STR_LIT>""" <EOL> visited [ node ] = count <EOL> for each in graph [ node ] : <EOL> if ( each not in visited ) : <EOL> _dfs ( graph , visited , count , each ) <EOL> def cut_edges ( graph ) : <EOL> """<STR_LIT>""" <EOL> recursionlimit = getrecursionlimit ( ) <EOL> setrecursionlimit ( max ( len ( graph . nodes ( ) ) * <NUM_LIT:2> , recursionlimit ) ) <EOL> if '<STR_LIT>' == graph . __class__ . __name__ : <EOL> return _cut_hyperedges ( graph ) <EOL> pre = { } <EOL> low = { } <EOL> spanning_tree = { } <EOL> reply = [ ] <EOL> pre [ None ] = <NUM_LIT:0> <EOL> for each in graph : <EOL> if ( each not in pre ) : <EOL> spanning_tree [ each ] = None <EOL> _cut_dfs ( graph , spanning_tree , pre , low , reply , each ) <EOL> setrecursionlimit ( recursionlimit ) <EOL> return reply <EOL> def _cut_hyperedges ( hypergraph ) : <EOL> """<STR_LIT>""" <EOL> edges_ = cut_nodes ( hypergraph . graph ) <EOL> edges = [ ] <EOL> for each in edges_ : <EOL> if ( each [ <NUM_LIT:1> ] == '<STR_LIT:h>' ) : <EOL> edges . append ( each [ <NUM_LIT:0> ] ) <EOL> return edges <EOL> def cut_nodes ( graph ) : <EOL> """<STR_LIT>""" <EOL> recursionlimit = getrecursionlimit ( ) <EOL> setrecursionlimit ( max ( len ( graph . nodes ( ) ) * <NUM_LIT:2> , recursionlimit ) ) <EOL> if '<STR_LIT>' == graph . __class__ . __name__ : <EOL> return _cut_hypernodes ( graph ) <EOL> pre = { } <EOL> low = { } <EOL> reply = { } <EOL> spanning_tree = { } <EOL> pre [ None ] = <NUM_LIT:0> <EOL> for each in graph : <EOL> if ( each not in pre ) : <EOL> spanning_tree [ each ] = None <EOL> _cut_dfs ( graph , spanning_tree , pre , low , [ ] , each ) <EOL> for each in graph : <EOL> if ( spanning_tree [ each ] is not None ) : <EOL> for other in graph [ each ] : <EOL> if ( low [ other ] >= pre [ each ] and spanning_tree [ other ] == each ) : <EOL> reply [ each ] = <NUM_LIT:1> <EOL> else : <EOL> children = <NUM_LIT:0> <EOL> for other in graph : <EOL> if ( spanning_tree [ other ] == each ) : <EOL> children = children + <NUM_LIT:1> <EOL> if ( children >= <NUM_LIT:2> ) : <EOL> reply [ each ] = <NUM_LIT:1> <EOL> setrecursionlimit ( recursionlimit ) <EOL> return list ( reply . keys ( ) ) <EOL> def _cut_hypernodes ( hypergraph ) : <EOL> """<STR_LIT>""" <EOL> nodes_ = cut_nodes ( hypergraph . graph ) <EOL> nodes = [ ] <EOL> for each in nodes_ : <EOL> if ( each [ <NUM_LIT:1> ] == '<STR_LIT:n>' ) : <EOL> nodes . append ( each [ <NUM_LIT:0> ] ) <EOL> return nodes <EOL> def _cut_dfs ( graph , spanning_tree , pre , low , reply , node ) : <EOL> """<STR_LIT>""" <EOL> pre [ node ] = pre [ None ] <EOL> low [ node ] = pre [ None ] <EOL> pre [ None ] = pre [ None ] + <NUM_LIT:1> <EOL> for each in graph [ node ] : <EOL> if ( each not in pre ) : <EOL> spanning_tree [ each ] = node <EOL> _cut_dfs ( graph , spanning_tree , pre , low , reply , each ) <EOL> if ( low [ node ] > low [ each ] ) : <EOL> low [ node ] = low [ each ] <EOL> if ( low [ each ] == pre [ each ] ) : <EOL> reply . append ( ( node , each ) ) <EOL> elif ( low [ node ] > pre [ each ] and spanning_tree [ node ] != each ) : <EOL> low [ node ] = pre [ each ] </s>
