-
Notifications
You must be signed in to change notification settings - Fork 326
/
graph_utils.py
320 lines (248 loc) · 8.89 KB
/
graph_utils.py
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
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
"""
Functions for manipulating dot-based resolve graphs.
"""
from __future__ import print_function
import re
import os.path
import subprocess
import sys
import tempfile
from ast import literal_eval
from rez.config import config
from rez.vendor.pydot import pydot
from rez.utils.system import popen
from rez.utils.formatting import PackageRequest
from rez.exceptions import PackageRequestError
from rez.vendor.pygraph.readwrite.dot import read as read_dot
from rez.vendor.pygraph.algorithms.accessibility import accessibility
from rez.vendor.pygraph.classes.digraph import digraph
def read_graph_from_string(txt):
"""Read a graph from a string, either in dot format, or our own
compressed format.
Returns:
`pygraph.digraph`: Graph object.
"""
if not txt.startswith('{'):
return read_dot(txt) # standard dot format
def conv(value):
if isinstance(value, basestring):
return '"' + value + '"'
else:
return value
# our compacted format
doc = literal_eval(txt)
g = digraph()
for attrs, values in doc.get("nodes", []):
attrs = [(k, conv(v)) for k, v in attrs]
for value in values:
if isinstance(value, basestring):
node_name = value
attrs_ = attrs
else:
node_name, label = value
attrs_ = attrs + [("label", conv(label))]
g.add_node(node_name, attrs=attrs_)
for attrs, values in doc.get("edges", []):
attrs_ = [(k, conv(v)) for k, v in attrs]
for value in values:
if len(value) == 3:
edge = value[:2]
label = value[-1]
else:
edge = value
label = ''
g.add_edge(edge, label=label, attrs=attrs_)
return g
def write_compacted(g):
"""Write a graph in our own compacted format.
Returns:
str.
"""
d_nodes = {}
d_edges = {}
def conv(value):
if isinstance(value, basestring):
return value.strip('"')
else:
return value
for node in g.nodes():
label = None
attrs = []
for k, v in sorted(g.node_attributes(node)):
v_ = conv(v)
if k == "label":
label = v_
else:
attrs.append((k, v_))
value = (node, label) if label else node
d_nodes.setdefault(tuple(attrs), []).append(value)
for edge in g.edges():
attrs = [(k, conv(v)) for k, v in sorted(g.edge_attributes(edge))]
label = str(g.edge_label(edge))
value = tuple(list(edge) + [label]) if label else edge
d_edges.setdefault(tuple(attrs), []).append(tuple(value))
doc = dict(nodes=d_nodes.items(), edges=d_edges.items())
contents = str(doc)
return contents
def write_dot(g):
"""Replacement for pygraph.readwrite.dot.write, which is dog slow.
Note:
This isn't a general replacement. It will work for the graphs that
Rez generates, but there are no guarantees beyond that.
Args:
g (`pygraph.digraph`): Input graph.
Returns:
str: Graph in dot format.
"""
lines = ["digraph g {"]
def attrs_txt(items):
if items:
txt = ", ".join(('%s="%s"' % (k, str(v).strip('"')))
for k, v in items)
return '[' + txt + ']'
else:
return ''
for node in g.nodes():
atxt = attrs_txt(g.node_attributes(node))
txt = "%s %s;" % (node, atxt)
lines.append(txt)
for e in g.edges():
edge_from, edge_to = e
attrs = g.edge_attributes(e)
label = str(g.edge_label(e))
if label:
attrs.append(("label", label))
atxt = attrs_txt(attrs)
txt = "%s -> %s %s;" % (edge_from, edge_to, atxt)
lines.append(txt)
lines.append("}")
return '\n'.join(lines)
def prune_graph(graph_str, package_name):
"""Prune a package graph so it only contains nodes accessible from the
given package.
Args:
graph_str (str): Dot-language graph string.
package_name (str): Name of package of interest.
Returns:
Pruned graph, as a string.
"""
# find nodes of interest
g = read_dot(graph_str)
nodes = set()
for node, attrs in g.node_attr.iteritems():
attr = [x for x in attrs if x[0] == "label"]
if attr:
label = attr[0][1]
try:
req_str = _request_from_label(label)
request = PackageRequest(req_str)
except PackageRequestError:
continue
if request.name == package_name:
nodes.add(node)
if not nodes:
raise ValueError("The package %r does not appear in the graph."
% package_name)
# find nodes upstream from these nodes
g_rev = g.reverse()
accessible_nodes = set()
access = accessibility(g_rev)
for node in nodes:
nodes_ = access.get(node, [])
accessible_nodes |= set(nodes_)
# remove inaccessible nodes
inaccessible_nodes = set(g.nodes()) - accessible_nodes
for node in inaccessible_nodes:
g.del_node(node)
return write_dot(g)
def save_graph(graph_str, dest_file, fmt=None, image_ratio=None):
"""Render a graph to an image file.
Args:
graph_str (str): Dot-language graph string.
dest_file (str): Filepath to save the graph to.
fmt (str): Format, eg "png", "jpg".
image_ratio (float): Image ratio.
Returns:
String representing format that was written, such as 'png'.
"""
# Disconnected edges can result in multiple graphs. We should never see
# this - it's a bug in graph generation if we do.
#
graphs = pydot.graph_from_dot_data(graph_str)
if not graphs:
raise RuntimeError("No graph generated")
if len(graphs) > 1:
path, ext = os.path.splitext(dest_file)
dest_files = []
for i, g in enumerate(graphs):
try:
dest_file_ = "%s.%d%s" % (path, i + 1, ext)
save_graph_object(g, dest_file_, fmt, image_ratio)
dest_files.append(dest_file_)
except:
pass
raise RuntimeError(
"More than one graph was generated; this probably indicates a bug "
"in graph generation. Graphs were written to %r" % dest_files
)
# write the graph
return save_graph_object(graphs[0], dest_file, fmt, image_ratio)
def save_graph_object(g, dest_file, fmt=None, image_ratio=None):
"""Like `save_graph`, but takes a pydot Dot object.
"""
# determine the dest format
if fmt is None:
fmt = os.path.splitext(dest_file)[1].lower().strip('.') or "png"
if hasattr(g, "write_" + fmt):
write_fn = getattr(g, "write_" + fmt)
else:
raise RuntimeError("Unsupported graph format: '%s'" % fmt)
if image_ratio:
g.set_ratio(str(image_ratio))
write_fn(dest_file)
return fmt
def view_graph(graph_str, dest_file=None):
"""View a dot graph in an image viewer."""
from rez.system import system
from rez.config import config
if (system.platform == "linux") and (not os.getenv("DISPLAY")):
print("Unable to open display.", file=sys.stderr)
sys.exit(1)
dest_file = _write_graph(graph_str, dest_file=dest_file)
# view graph
viewed = False
prog = config.image_viewer or 'browser'
print("loading image viewer (%s)..." % prog)
if config.image_viewer:
proc = popen([config.image_viewer, dest_file])
proc.wait()
viewed = not bool(proc.returncode)
if not viewed:
import webbrowser
webbrowser.open_new("file://" + dest_file)
def _write_graph(graph_str, dest_file=None):
if not dest_file:
tmpf = tempfile.mkstemp(prefix='resolve-dot-',
suffix='.' + config.dot_image_format)
os.close(tmpf[0])
dest_file = tmpf[1]
print("rendering image to " + dest_file + "...")
save_graph(graph_str, dest_file)
return dest_file
# converts string like '"PyQt-4.8.0[1]"' to 'PyQt-4.8.0'
def _request_from_label(label):
return label.strip('"').strip("'").rsplit('[', 1)[0]
# Copyright 2013-2016 Allan Johns.
#
# This library is free software: you can redistribute it and/or
# modify it under the terms of the GNU Lesser General Public
# License as published by the Free Software Foundation, either
# version 3 of the License, or (at your option) any later version.
#
# This library 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
# Lesser General Public License for more details.
#
# You should have received a copy of the GNU Lesser General Public
# License along with this library. If not, see <http://www.gnu.org/licenses/>.