1 """Graph manipulation utilities.
2
3 (dot generation adapted from pypy/translator/tool/make_dot.py)
4
5 :copyright: 2000-2009 LOGILAB S.A. (Paris, FRANCE), all rights reserved.
6 :contact: http://www.logilab.fr/ -- mailto:contact@logilab.fr
7 :license: General Public License version 2 - http://www.gnu.org/licenses
8 """
9 __docformat__ = "restructuredtext en"
10
11 __metaclass__ = type
12
13 import os.path as osp
14 import os
15 import subprocess
16 import sys
17 import tempfile
18
20 """Make <value> usable in a dot file."""
21 lines = [line.replace('"', '\\"') for line in value.split('\n')]
22 data = '\\l'.join(lines)
23 return '\\n' + data
24
26 """Transforms /some/path/foo.png into ('/some/path', 'foo.png', 'png')."""
27 basename = osp.basename(filename)
28 storedir = osp.dirname(osp.abspath(filename))
29 target = filename.split('.')[-1]
30 return storedir, basename, target
31
32
34 """Dot File backend."""
35 - def __init__(self, graphname, rankdir=None, size=None, ratio=None,
36 charset='utf-8', renderer='dot', additionnal_param={}):
37 self.graphname = graphname
38 self.renderer = renderer
39 self.lines = []
40 self._source = None
41 self.emit("digraph %s {" % normalize_node_id(graphname))
42 if rankdir:
43 self.emit('rankdir=%s' % rankdir)
44 if ratio:
45 self.emit('ratio=%s' % ratio)
46 if size:
47 self.emit('size="%s"' % size)
48 if charset:
49 assert charset.lower() in ('utf-8', 'iso-8859-1', 'latin1'), \
50 'unsupported charset %s' % charset
51 self.emit('charset="%s"' % charset)
52 for param in additionnal_param.iteritems():
53 self.emit('='.join(param))
54
56 """returns self._source"""
57 if self._source is None:
58 self.emit("}\n")
59 self._source = '\n'.join(self.lines)
60 del self.lines
61 return self._source
62
63 source = property(get_source)
64
65 - def generate(self, outputfile=None, dotfile=None):
66 """Generates a graph file.
67
68 :param outputfile: filename and path [defaults to graphname.png]
69 :param dotfile: filename and path [defaults to graphname.dot]
70
71 :rtype: str
72 :return: a path to the generated file
73 """
74 name = self.graphname
75 if not dotfile:
76
77 if outputfile and outputfile.endswith(".dot"):
78 dotfile = outputfile
79 else:
80 dotfile = '%s.dot' % name
81 if outputfile is not None:
82 storedir, basename, target = target_info_from_filename(outputfile)
83 if target != "dot":
84 pdot, dot_sourcepath = tempfile.mkstemp(".dot", name)
85 os.close(pdot)
86 else:
87 dot_sourcepath = osp.join(storedir, dotfile)
88 else:
89 target = 'png'
90 pdot, dot_sourcepath = tempfile.mkstemp(".dot", name)
91 ppng, outputfile = tempfile.mkstemp(".png", name)
92 os.close(pdot)
93 os.close(ppng)
94 pdot = open(dot_sourcepath,'w')
95 if isinstance(self.source, unicode):
96 pdot.write(self.source.encode('UTF8'))
97 else:
98 pdot.write(self.source)
99 pdot.close()
100 if target != 'dot':
101 subprocess.call('%s -T%s %s -o%s' % (self.renderer, target,
102 dot_sourcepath, outputfile), shell=True)
103 os.unlink(dot_sourcepath)
104 return outputfile
105
106 - def emit(self, line):
107 """Adds <line> to final output."""
108 self.lines.append(line)
109
111 """emit an edge from <name1> to <name2>.
112 edge properties: see http://www.graphviz.org/doc/info/attrs.html
113 """
114 attrs = ['%s="%s"' % (prop, value) for prop, value in props.items()]
115 n_from, n_to = normalize_node_id(name1), normalize_node_id(name2)
116 self.emit('%s -> %s [%s];' % (n_from, n_to, ", ".join(attrs)) )
117
119 """emit a node with given properties.
120 node properties: see http://www.graphviz.org/doc/info/attrs.html
121 """
122 attrs = ['%s="%s"' % (prop, value) for prop, value in props.items()]
123 self.emit('%s [%s];' % (normalize_node_id(name), ", ".join(attrs)))
124
126 """Returns a suitable DOT node id for `nid`."""
127 return '"%s"' % nid
128
131
132 self.backend = backend
133
134 - def generate(self, visitor, propshdlr, outputfile=None):
135
136
137
138 self.propshdlr = propshdlr
139 for nodeid, node in visitor.nodes():
140 props = propshdlr.node_properties(node)
141 self.backend.emit_node(nodeid, **props)
142 for subjnode, objnode, edge in visitor.edges():
143 props = propshdlr.edge_properties(edge, subjnode, objnode)
144 self.backend.emit_edge(subjnode, objnode, **props)
145 return self.backend.generate(outputfile)
146
147
148
150 '''given a dictionary representing an ordered graph (i.e. key are vertices
151 and values is a list of destination vertices representing edges), return a
152 list of detected cycles
153 '''
154 if not graph_dict:
155 return ()
156 result = []
157 if vertices is None:
158 vertices = graph_dict.keys()
159 for vertice in vertices:
160 _get_cycles(graph_dict, vertice, [], result)
161 return result
162
163 -def _get_cycles(graph_dict, vertice=None, path=None, result=None):
164 """recursive function doing the real work for get_cycles"""
165 if vertice in path:
166 cycle = [vertice]
167 for node in path[::-1]:
168 if node == vertice:
169 break
170 cycle.insert(0, node)
171
172 start_from = min(cycle)
173 index = cycle.index(start_from)
174 cycle = cycle[index:] + cycle[0:index]
175
176 if not cycle in result:
177 result.append(cycle)
178 return
179 path.append(vertice)
180 try:
181 for node in graph_dict[vertice]:
182 _get_cycles(graph_dict, node, path, result)
183 except KeyError:
184 pass
185 path.pop()
186
187 -def has_path(graph_dict, fromnode, tonode, path=None):
188 """generic function taking a simple graph definition as a dictionary, with
189 node has key associated to a list of nodes directly reachable from it.
190
191 Return None if no path exists to go from `fromnode` to `tonode`, else the
192 first path found (as a list including the destination node at last)
193 """
194 if path is None:
195 path = []
196 elif fromnode in path:
197 return None
198 path.append(fromnode)
199 for destnode in graph_dict[fromnode]:
200 if destnode == tonode or has_path(graph_dict, destnode, tonode, path):
201 return path[1:] + [tonode]
202 path.pop()
203 return None
204