1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
|
"""
Copyright 2008-2011 Free Software Foundation, Inc.
This file is part of GNU Radio
GNU Radio Companion is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.
GNU Radio Companion is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
"""
import string
VAR_CHARS = string.letters + string.digits + '_'
class graph(object):
"""
Simple graph structure held in a dictionary.
"""
def __init__(self): self._graph = dict()
def __str__(self): return str(self._graph)
def add_node(self, node_key):
if self._graph.has_key(node_key): return
self._graph[node_key] = set()
def remove_node(self, node_key):
if not self._graph.has_key(node_key): return
for edges in self._graph.values():
if node_key in edges: edges.remove(node_key)
self._graph.pop(node_key)
def add_edge(self, src_node_key, dest_node_key):
self._graph[src_node_key].add(dest_node_key)
def remove_edge(self, src_node_key, dest_node_key):
self._graph[src_node_key].remove(dest_node_key)
def get_nodes(self): return self._graph.keys()
def get_edges(self, node_key): return self._graph[node_key]
def expr_split(expr):
"""
Split up an expression by non alphanumeric characters, including underscore.
Leave strings in-tact.
#TODO ignore escaped quotes, use raw strings.
@param expr an expression string
@return a list of string tokens that form expr
"""
toks = list()
tok = ''
quote = ''
for char in expr:
if quote or char in VAR_CHARS:
if char == quote: quote = ''
tok += char
elif char in ("'", '"'):
toks.append(tok)
tok = char
quote = char
else:
toks.append(tok)
toks.append(char)
tok = ''
toks.append(tok)
return filter(lambda t: t, toks)
def expr_replace(expr, replace_dict):
"""
Search for vars in the expression and add the prepend.
@param expr an expression string
@param replace_dict a dict of find:replace
@return a new expression with the prepend
"""
expr_splits = expr_split(expr)
for i, es in enumerate(expr_splits):
if es in replace_dict.keys():
expr_splits[i] = replace_dict[es]
return ''.join(expr_splits)
def get_variable_dependencies(expr, vars):
"""
Return a set of variables used in this expression.
@param expr an expression string
@param vars a list of variable names
@return a subset of vars used in the expression
"""
expr_toks = expr_split(expr)
return set(filter(lambda v: v in expr_toks, vars))
def get_graph(exprs):
"""
Get a graph representing the variable dependencies
@param exprs a mapping of variable name to expression
@return a graph of variable deps
"""
vars = exprs.keys()
#get dependencies for each expression, load into graph
var_graph = graph()
for var in vars: var_graph.add_node(var)
for var, expr in exprs.iteritems():
for dep in get_variable_dependencies(expr, vars):
if dep != var: var_graph.add_edge(dep, var)
return var_graph
def sort_variables(exprs):
"""
Get a list of variables in order of dependencies.
@param exprs a mapping of variable name to expression
@return a list of variable names
@throws Exception circular dependencies
"""
var_graph = get_graph(exprs)
sorted_vars = list()
#determine dependency order
while var_graph.get_nodes():
#get a list of nodes with no edges
indep_vars = filter(lambda var: not var_graph.get_edges(var), var_graph.get_nodes())
if not indep_vars: raise Exception('circular dependency caught in sort_variables')
#add the indep vars to the end of the list
sorted_vars.extend(sorted(indep_vars))
#remove each edge-less node from the graph
for var in indep_vars: var_graph.remove_node(var)
return reversed(sorted_vars)
def sort_objects(objects, get_id, get_expr):
"""
Sort a list of objects according to their expressions.
@param objects the list of objects to sort
@param get_id the function to extract an id from the object
@param get_expr the function to extract an expression from the object
@return a list of sorted objects
"""
id2obj = dict([(get_id(obj), obj) for obj in objects])
#map obj id to expression code
id2expr = dict([(get_id(obj), get_expr(obj)) for obj in objects])
#sort according to dependency
sorted_ids = sort_variables(id2expr)
#return list of sorted objects
return [id2obj[id] for id in sorted_ids]
if __name__ == '__main__':
for i in sort_variables({'x':'1', 'y':'x+1', 'a':'x+y', 'b':'y+1', 'c':'a+b+x+y'}): print i
|
