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
|
"""
Copyright 2008 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
"""
##@package grc_gnuradio.utils.expr_utils
#Utility functions to comprehend variable expressions.
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_prepend(expr, vars, prepend):
"""!
Search for vars in the expression and add the prepend.
@param expr an expression string
@param vars a list of variable names
@param prepend the prepend string
@return a new expression with the prepend
"""
expr_splits = expr_split(expr)
for i, es in enumerate(expr_splits):
if es in vars: expr_splits[i] = prepend + 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):
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 AssertionError 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())
assert indep_vars
#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)
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
|
