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