<s> """<STR_LIT>""" <EOL> from itertools import chain <EOL> from itertools import combinations <EOL> from itertools import permutations <EOL> from itertools import product <EOL> import networkx as nx <EOL> from networkx import density <EOL> from networkx . exception import NetworkXException <EOL> from networkx . utils import arbitrary_element <EOL> __all__ = [ '<STR_LIT>' , '<STR_LIT>' , <EOL> '<STR_LIT>' , '<STR_LIT>' , '<STR_LIT>' ] <EOL> chaini = chain . from_iterable <EOL> def equivalence_classes ( iterable , relation ) : <EOL> """<STR_LIT>""" <EOL> blocks = [ ] <EOL> for y in iterable : <EOL> for block in blocks : <EOL> x = arbitrary_element ( block ) <EOL> if relation ( x , y ) : <EOL> block . append ( y ) <EOL> break <EOL> else : <EOL> blocks . append ( [ y ] ) <EOL> return { frozenset ( block ) for block in blocks } <EOL> def quotient_graph ( G , partition , edge_relation = None , node_data = None , <EOL> edge_data = None , relabel = False , create_using = None ) : <EOL> """<STR_LIT>""" <EOL> if callable ( partition ) : <EOL> partition = equivalence_classes ( G , partition ) <EOL> if any ( sum ( <NUM_LIT:1> for b in partition if v in b ) != <NUM_LIT:1> for v in G ) : <EOL> raise NetworkXException ( '<STR_LIT>' ) <EOL> H = type ( create_using ) ( ) if create_using is not None else type ( G ) ( ) <EOL> if node_data is None : <EOL> def node_data ( b ) : <EOL> S = G . subgraph ( b ) <EOL> return dict ( graph = S , nnodes = len ( S ) , nedges = S . number_of_edges ( ) , <EOL> density = density ( S ) ) <EOL> partition = [ frozenset ( b ) for b in partition ] <EOL> H . add_nodes_from ( ( b , node_data ( b ) ) for b in partition ) <EOL> if edge_relation is None : <EOL> def edge_relation ( b , c ) : <EOL> return any ( v in G [ u ] for u , v in product ( b , c ) ) <EOL> if edge_data is None : <EOL> def edge_data ( b , c ) : <EOL> edgedata = ( d for u , v , d in G . edges ( b | c , data = True ) <EOL> if ( u in b and v in c ) or ( u in c and v in b ) ) <EOL> return { '<STR_LIT>' : sum ( d . get ( '<STR_LIT>' , <NUM_LIT:1> ) for d in edgedata ) } <EOL> block_pairs = permutations ( H , <NUM_LIT:2> ) if H . is_directed ( ) else combinations ( H , <NUM_LIT:2> ) <EOL> if H . is_multigraph ( ) : <EOL> edges = chaini ( ( ( b , c , G . get_edge_data ( u , v , default = { } ) ) <EOL> for u , v in product ( b , c ) if v in G [ u ] ) <EOL> for b , c in block_pairs if edge_relation ( b , c ) ) <EOL> else : <EOL> edges = ( ( b , c , edge_data ( b , c ) ) for ( b , c ) in block_pairs <EOL> if edge_relation ( b , c ) ) <EOL> H . add_edges_from ( edges ) <EOL> if relabel : <EOL> labels = { b : i for i , b in enumerate ( partition ) } <EOL> H = nx . relabel_nodes ( H , labels ) <EOL> return H <EOL> def contracted_nodes ( G , u , v , self_loops = True ) : <EOL> """<STR_LIT>""" <EOL> H = G . copy ( ) <EOL> if H . is_directed ( ) : <EOL> in_edges = ( ( w , u , d ) for w , x , d in G . in_edges ( v , data = True ) <EOL> if self_loops or w != u ) <EOL> out_edges = ( ( u , w , d ) for x , w , d in G . out_edges ( v , data = True ) <EOL> if self_loops or w != u ) <EOL> new_edges = chain ( in_edges , out_edges ) <EOL> else : <EOL> new_edges = ( ( u , w , d ) for x , w , d in G . edges ( v , data = True ) <EOL> if self_loops or w != u ) <EOL> v_data = H . node [ v ] <EOL> H . remove_node ( v ) <EOL> H . add_edges_from ( new_edges ) <EOL> if '<STR_LIT>' in H . node [ u ] : <EOL> H . node [ u ] [ '<STR_LIT>' ] [ v ] = v_data <EOL> else : <EOL> H . node [ u ] [ '<STR_LIT>' ] = { v : v_data } <EOL> return H <EOL> identified_nodes = contracted_nodes <EOL> def contracted_edge ( G , edge , self_loops = True ) : <EOL> """<STR_LIT>""" <EOL> if not G . has_edge ( * edge ) : <EOL> raise ValueError ( '<STR_LIT>' <EOL> '<STR_LIT>' . format ( edge ) ) <EOL> return contracted_nodes ( G , * edge , self_loops = self_loops ) <EOL> def blockmodel ( G , partition , multigraph = False ) : <EOL> """<STR_LIT>""" <EOL> if multigraph : <EOL> return nx . quotient_graph ( G , partition , <EOL> create_using = nx . MultiGraph ( ) , relabel = True ) <EOL> else : <EOL> return nx . quotient_graph ( G , partition , relabel = True ) </s>
