Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(124)

Side by Side Diff: third_party/logilab/common/graph.py

Issue 719313003: Revert "pylint: upgrade to 1.3.1" (Closed) Base URL: https://chromium.googlesource.com/chromium/tools/depot_tools.git@master
Patch Set: Created 6 years, 1 month ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « third_party/logilab/common/fileutils.py ('k') | third_party/logilab/common/hg.py » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
1 # copyright 2003-2011 LOGILAB S.A. (Paris, FRANCE), all rights reserved. 1 # copyright 2003-2011 LOGILAB S.A. (Paris, FRANCE), all rights reserved.
2 # contact http://www.logilab.fr/ -- mailto:contact@logilab.fr 2 # contact http://www.logilab.fr/ -- mailto:contact@logilab.fr
3 # 3 #
4 # This file is part of logilab-common. 4 # This file is part of logilab-common.
5 # 5 #
6 # logilab-common is free software: you can redistribute it and/or modify it unde r 6 # logilab-common is free software: you can redistribute it and/or modify it unde r
7 # the terms of the GNU Lesser General Public License as published by the Free 7 # the terms of the GNU Lesser General Public License as published by the Free
8 # Software Foundation, either version 2.1 of the License, or (at your option) an y 8 # Software Foundation, either version 2.1 of the License, or (at your option) an y
9 # later version. 9 # later version.
10 # 10 #
(...skipping 10 matching lines...) Expand all
21 """ 21 """
22 22
23 __docformat__ = "restructuredtext en" 23 __docformat__ = "restructuredtext en"
24 24
25 __metaclass__ = type 25 __metaclass__ = type
26 26
27 import os.path as osp 27 import os.path as osp
28 import os 28 import os
29 import sys 29 import sys
30 import tempfile 30 import tempfile
31 import codecs 31 from logilab.common.compat import str_encode
32 import errno
33 32
34 def escape(value): 33 def escape(value):
35 """Make <value> usable in a dot file.""" 34 """Make <value> usable in a dot file."""
36 lines = [line.replace('"', '\\"') for line in value.split('\n')] 35 lines = [line.replace('"', '\\"') for line in value.split('\n')]
37 data = '\\l'.join(lines) 36 data = '\\l'.join(lines)
38 return '\\n' + data 37 return '\\n' + data
39 38
40 def target_info_from_filename(filename): 39 def target_info_from_filename(filename):
41 """Transforms /some/path/foo.png into ('/some/path', 'foo.png', 'png').""" 40 """Transforms /some/path/foo.png into ('/some/path', 'foo.png', 'png')."""
42 basename = osp.basename(filename) 41 basename = osp.basename(filename)
(...skipping 14 matching lines...) Expand all
57 if rankdir: 56 if rankdir:
58 self.emit('rankdir=%s' % rankdir) 57 self.emit('rankdir=%s' % rankdir)
59 if ratio: 58 if ratio:
60 self.emit('ratio=%s' % ratio) 59 self.emit('ratio=%s' % ratio)
61 if size: 60 if size:
62 self.emit('size="%s"' % size) 61 self.emit('size="%s"' % size)
63 if charset: 62 if charset:
64 assert charset.lower() in ('utf-8', 'iso-8859-1', 'latin1'), \ 63 assert charset.lower() in ('utf-8', 'iso-8859-1', 'latin1'), \
65 'unsupported charset %s' % charset 64 'unsupported charset %s' % charset
66 self.emit('charset="%s"' % charset) 65 self.emit('charset="%s"' % charset)
67 for param in sorted(additionnal_param.items()): 66 for param in additionnal_param.iteritems():
68 self.emit('='.join(param)) 67 self.emit('='.join(param))
69 68
70 def get_source(self): 69 def get_source(self):
71 """returns self._source""" 70 """returns self._source"""
72 if self._source is None: 71 if self._source is None:
73 self.emit("}\n") 72 self.emit("}\n")
74 self._source = '\n'.join(self.lines) 73 self._source = '\n'.join(self.lines)
75 del self.lines 74 del self.lines
76 return self._source 75 return self._source
77 76
(...skipping 22 matching lines...) Expand all
100 pdot, dot_sourcepath = tempfile.mkstemp(".dot", name) 99 pdot, dot_sourcepath = tempfile.mkstemp(".dot", name)
101 os.close(pdot) 100 os.close(pdot)
102 else: 101 else:
103 dot_sourcepath = osp.join(storedir, dotfile) 102 dot_sourcepath = osp.join(storedir, dotfile)
104 else: 103 else:
105 target = 'png' 104 target = 'png'
106 pdot, dot_sourcepath = tempfile.mkstemp(".dot", name) 105 pdot, dot_sourcepath = tempfile.mkstemp(".dot", name)
107 ppng, outputfile = tempfile.mkstemp(".png", name) 106 ppng, outputfile = tempfile.mkstemp(".png", name)
108 os.close(pdot) 107 os.close(pdot)
109 os.close(ppng) 108 os.close(ppng)
110 pdot = codecs.open(dot_sourcepath, 'w', encoding='utf8') 109 pdot = open(dot_sourcepath, 'w')
111 pdot.write(self.source) 110 pdot.write(str_encode(self.source, 'utf8'))
112 pdot.close() 111 pdot.close()
113 if target != 'dot': 112 if target != 'dot':
114 if sys.platform == 'win32': 113 if sys.platform == 'win32':
115 use_shell = True 114 use_shell = True
116 else: 115 else:
117 use_shell = False 116 use_shell = False
118 try: 117 if mapfile:
119 if mapfile: 118 subprocess.call([self.renderer, '-Tcmapx', '-o', mapfile, '-T', target, dot_sourcepath, '-o', outputfile],
120 subprocess.call([self.renderer, '-Tcmapx', '-o', mapfile, ' -T', target, dot_sourcepath, '-o', outputfile], 119 shell=use_shell)
121 shell=use_shell) 120 else:
122 else: 121 subprocess.call([self.renderer, '-T', target,
123 subprocess.call([self.renderer, '-T', target, 122 dot_sourcepath, '-o', outputfile],
124 dot_sourcepath, '-o', outputfile], 123 shell=use_shell)
125 shell=use_shell)
126 except OSError as e:
127 if e.errno == errno.ENOENT:
128 e.strerror = 'File not found: {0}'.format(self.renderer)
129 raise
130 os.unlink(dot_sourcepath) 124 os.unlink(dot_sourcepath)
131 return outputfile 125 return outputfile
132 126
133 def emit(self, line): 127 def emit(self, line):
134 """Adds <line> to final output.""" 128 """Adds <line> to final output."""
135 self.lines.append(line) 129 self.lines.append(line)
136 130
137 def emit_edge(self, name1, name2, **props): 131 def emit_edge(self, name1, name2, **props):
138 """emit an edge from <name1> to <name2>. 132 """emit an edge from <name1> to <name2>.
139 edge properties: see http://www.graphviz.org/doc/info/attrs.html 133 edge properties: see http://www.graphviz.org/doc/info/attrs.html
140 """ 134 """
141 attrs = ['%s="%s"' % (prop, value) for prop, value in props.items()] 135 attrs = ['%s="%s"' % (prop, value) for prop, value in props.items()]
142 n_from, n_to = normalize_node_id(name1), normalize_node_id(name2) 136 n_from, n_to = normalize_node_id(name1), normalize_node_id(name2)
143 self.emit('%s -> %s [%s];' % (n_from, n_to, ', '.join(sorted(attrs))) ) 137 self.emit('%s -> %s [%s];' % (n_from, n_to, ", ".join(attrs)) )
144 138
145 def emit_node(self, name, **props): 139 def emit_node(self, name, **props):
146 """emit a node with given properties. 140 """emit a node with given properties.
147 node properties: see http://www.graphviz.org/doc/info/attrs.html 141 node properties: see http://www.graphviz.org/doc/info/attrs.html
148 """ 142 """
149 attrs = ['%s="%s"' % (prop, value) for prop, value in props.items()] 143 attrs = ['%s="%s"' % (prop, value) for prop, value in props.items()]
150 self.emit('%s [%s];' % (normalize_node_id(name), ', '.join(sorted(attrs) ))) 144 self.emit('%s [%s];' % (normalize_node_id(name), ", ".join(attrs)))
151 145
152 def normalize_node_id(nid): 146 def normalize_node_id(nid):
153 """Returns a suitable DOT node id for `nid`.""" 147 """Returns a suitable DOT node id for `nid`."""
154 return '"%s"' % nid 148 return '"%s"' % nid
155 149
156 class GraphGenerator: 150 class GraphGenerator:
157 def __init__(self, backend): 151 def __init__(self, backend):
158 # the backend is responsible to output the graph in a particular format 152 # the backend is responsible to output the graph in a particular format
159 self.backend = backend 153 self.backend = backend
160 154
(...skipping 64 matching lines...) Expand 10 before | Expand all | Expand 10 after
225 '''given a dictionary representing an ordered graph (i.e. key are vertices 219 '''given a dictionary representing an ordered graph (i.e. key are vertices
226 and values is a list of destination vertices representing edges), return a 220 and values is a list of destination vertices representing edges), return a
227 list of detected cycles 221 list of detected cycles
228 ''' 222 '''
229 if not graph_dict: 223 if not graph_dict:
230 return () 224 return ()
231 result = [] 225 result = []
232 if vertices is None: 226 if vertices is None:
233 vertices = graph_dict.keys() 227 vertices = graph_dict.keys()
234 for vertice in vertices: 228 for vertice in vertices:
235 _get_cycles(graph_dict, [], set(), result, vertice) 229 _get_cycles(graph_dict, vertice, [], result)
236 return result 230 return result
237 231
238 def _get_cycles(graph_dict, path, visited, result, vertice): 232 def _get_cycles(graph_dict, vertice=None, path=None, result=None):
239 """recursive function doing the real work for get_cycles""" 233 """recursive function doing the real work for get_cycles"""
240 if vertice in path: 234 if vertice in path:
241 cycle = [vertice] 235 cycle = [vertice]
242 for node in path[::-1]: 236 for node in path[::-1]:
243 if node == vertice: 237 if node == vertice:
244 break 238 break
245 cycle.insert(0, node) 239 cycle.insert(0, node)
246 # make a canonical representation 240 # make a canonical representation
247 start_from = min(cycle) 241 start_from = min(cycle)
248 index = cycle.index(start_from) 242 index = cycle.index(start_from)
249 cycle = cycle[index:] + cycle[0:index] 243 cycle = cycle[index:] + cycle[0:index]
250 # append it to result if not already in 244 # append it to result if not already in
251 if not cycle in result: 245 if not cycle in result:
252 result.append(cycle) 246 result.append(cycle)
253 return 247 return
254 path.append(vertice) 248 path.append(vertice)
255 try: 249 try:
256 for node in graph_dict[vertice]: 250 for node in graph_dict[vertice]:
257 # don't check already visited nodes again 251 _get_cycles(graph_dict, node, path, result)
258 if node not in visited:
259 _get_cycles(graph_dict, path, visited, result, node)
260 visited.add(node)
261 except KeyError: 252 except KeyError:
262 pass 253 pass
263 path.pop() 254 path.pop()
264 255
265 def has_path(graph_dict, fromnode, tonode, path=None): 256 def has_path(graph_dict, fromnode, tonode, path=None):
266 """generic function taking a simple graph definition as a dictionary, with 257 """generic function taking a simple graph definition as a dictionary, with
267 node has key associated to a list of nodes directly reachable from it. 258 node has key associated to a list of nodes directly reachable from it.
268 259
269 Return None if no path exists to go from `fromnode` to `tonode`, else the 260 Return None if no path exists to go from `fromnode` to `tonode`, else the
270 first path found (as a list including the destination node at last) 261 first path found (as a list including the destination node at last)
271 """ 262 """
272 if path is None: 263 if path is None:
273 path = [] 264 path = []
274 elif fromnode in path: 265 elif fromnode in path:
275 return None 266 return None
276 path.append(fromnode) 267 path.append(fromnode)
277 for destnode in graph_dict[fromnode]: 268 for destnode in graph_dict[fromnode]:
278 if destnode == tonode or has_path(graph_dict, destnode, tonode, path): 269 if destnode == tonode or has_path(graph_dict, destnode, tonode, path):
279 return path[1:] + [tonode] 270 return path[1:] + [tonode]
280 path.pop() 271 path.pop()
281 return None 272 return None
282 273
OLDNEW
« no previous file with comments | « third_party/logilab/common/fileutils.py ('k') | third_party/logilab/common/hg.py » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698