<s> import re <EOL> import json <EOL> from quepy . dsl import IsRelatedTo <EOL> from quepy . expression import isnode <EOL> from quepy . encodingpolicy import encoding_flexible_conversion <EOL> def choose_start_node ( e ) : <EOL> """<STR_LIT>""" <EOL> for node in e . iter_nodes ( ) : <EOL> if list ( e . iter_edges ( node ) ) : <EOL> return node <EOL> return node <EOL> def safely_to_unicode ( x ) : <EOL> """<STR_LIT>""" <EOL> if isinstance ( x , unicode ) : <EOL> return x <EOL> if isinstance ( x , str ) : <EOL> return encoding_flexible_conversion ( x ) <EOL> if isinstance ( x , IsRelatedTo ) : <EOL> return u"<STR_LIT>" <EOL> return unicode ( x ) <EOL> def to_bidirected_graph ( e ) : <EOL> """<STR_LIT>""" <EOL> graph = { node : [ ] for node in e . iter_nodes ( ) } <EOL> for node in e . iter_nodes ( ) : <EOL> for relation , other in e . iter_edges ( node ) : <EOL> relation = safely_to_unicode ( relation ) <EOL> if isnode ( other ) : <EOL> graph [ other ] . append ( ( u"<STR_LIT:!>" + relation , node ) ) <EOL> else : <EOL> other = safely_to_unicode ( other ) <EOL> graph [ node ] . append ( ( relation , other ) ) <EOL> assert all ( isnode ( x ) for x in graph ) and len ( e ) == len ( graph ) <EOL> return graph <EOL> def post_order_depth_first ( graph , start ) : <EOL> """<STR_LIT>""" <EOL> q = [ start ] <EOL> seen = set ( ) <EOL> i = <NUM_LIT:0> <EOL> while i != len ( graph ) : <EOL> node = q [ i ] <EOL> seen . add ( node ) <EOL> i += <NUM_LIT:1> <EOL> for _ , other in graph [ node ] : <EOL> if isnode ( other ) and other not in seen : <EOL> q . append ( other ) <EOL> assert len ( q ) == len ( graph ) <EOL> q . reverse ( ) <EOL> return q <EOL> def paths_from_root ( graph , start ) : <EOL> """<STR_LIT>""" <EOL> paths = { start : [ ] } <EOL> q = [ start ] <EOL> seen = set ( ) <EOL> while q : <EOL> node = q . pop ( ) <EOL> seen . add ( node ) <EOL> for relation , child in graph [ node ] : <EOL> if isnode ( child ) and child not in seen : <EOL> q . append ( child ) <EOL> paths [ child ] = paths [ node ] + [ relation ] <EOL> return paths <EOL> def generate_mql ( e ) : <EOL> """<STR_LIT>""" <EOL> start = choose_start_node ( e ) <EOL> graph = to_bidirected_graph ( e ) <EOL> generated = { } <EOL> for node in post_order_depth_first ( graph , start ) : <EOL> d = { } <EOL> for relation , other in graph [ node ] : <EOL> if isnode ( other ) : <EOL> try : <EOL> other = generated [ other ] <EOL> except KeyError : <EOL> continue <EOL> d [ relation ] = other <EOL> generated [ node ] = [ d ] <EOL> mql_query = json . dumps ( generated [ start ] , sort_keys = True , <EOL> indent = <NUM_LIT:2> , separators = ( '<STR_LIT:U+002C>' , '<STR_LIT>' ) ) <EOL> mql_query = _tidy ( mql_query ) <EOL> target = paths_from_root ( graph , start ) [ e . get_head ( ) ] <EOL> return target , mql_query <EOL> def _tidy ( mql ) : <EOL> """<STR_LIT>""" <EOL> def replacement_function ( match ) : <EOL> text = match . group ( <NUM_LIT:0> ) <EOL> if text . startswith ( "<STR_LIT:[>" ) and text . endswith ( "<STR_LIT:]>" ) : <EOL> return "<STR_LIT>" <EOL> elif text . startswith ( "<STR_LIT:[>" ) : <EOL> return "<STR_LIT>" <EOL> indent = <NUM_LIT:0> <EOL> match = re . search ( "<STR_LIT>" , text ) <EOL> if match : <EOL> indent = len ( match . group ( <NUM_LIT:1> ) ) <EOL> return "<STR_LIT:U+0020>" * indent + "<STR_LIT>" <EOL> return re . sub ( "<STR_LIT>" , <EOL> replacement_function , mql ) </s>
