|
1 # Copyright (c) 2007-2008 Pedro Matiello <pmatiello@gmail.com> |
|
2 # |
|
3 # Permission is hereby granted, free of charge, to any person |
|
4 # obtaining a copy of this software and associated documentation |
|
5 # files (the "Software"), to deal in the Software without |
|
6 # restriction, including without limitation the rights to use, |
|
7 # copy, modify, merge, publish, distribute, sublicense, and/or sell |
|
8 # copies of the Software, and to permit persons to whom the |
|
9 # Software is furnished to do so, subject to the following |
|
10 # conditions: |
|
11 |
|
12 # The above copyright notice and this permission notice shall be |
|
13 # included in all copies or substantial portions of the Software. |
|
14 |
|
15 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, |
|
16 # EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES |
|
17 # OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND |
|
18 # NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT |
|
19 # HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, |
|
20 # WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING |
|
21 # FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR |
|
22 # OTHER DEALINGS IN THE SOFTWARE. |
|
23 |
|
24 |
|
25 """ |
|
26 Functions for reading and writing graphs. |
|
27 |
|
28 @sort: read_xml, write_xml, write_dot_graph, write_dot_digraph, write_dot_hypergraph |
|
29 """ |
|
30 |
|
31 |
|
32 # Imports |
|
33 from xml.dom.minidom import Document, parseString |
|
34 |
|
35 |
|
36 # Values |
|
37 colors = ['aquamarine4', 'blue4', 'brown4', 'cornflowerblue', 'cyan4', |
|
38 'darkgreen', 'darkorange3', 'darkorchid4', 'darkseagreen4', 'darkslategray', |
|
39 'deeppink4', 'deepskyblue4', 'firebrick3', 'hotpink3', 'indianred3', |
|
40 'indigo', 'lightblue4', 'lightseagreen', 'lightskyblue4', 'magenta4', |
|
41 'maroon', 'palevioletred3', 'steelblue', 'violetred3'] |
|
42 |
|
43 |
|
44 # XML |
|
45 |
|
46 def write_xml(graph): |
|
47 """ |
|
48 Return a string specifying the given graph as a XML document. |
|
49 |
|
50 @type graph: graph |
|
51 @param graph: Graph. |
|
52 |
|
53 @rtype: string |
|
54 @return: String specifying the graph as a XML document. |
|
55 """ |
|
56 |
|
57 # Document root |
|
58 grxml = Document() |
|
59 grxmlr = grxml.createElement('graph') |
|
60 grxml.appendChild(grxmlr) |
|
61 |
|
62 # Each node... |
|
63 for each_node in graph.nodes(): |
|
64 node = grxml.createElement('node') |
|
65 node.setAttribute('id',str(each_node)) |
|
66 grxmlr.appendChild(node) |
|
67 for each_attr in graph.get_node_attributes(each_node): |
|
68 attr = grxml.createElement('attribute') |
|
69 attr.setAttribute('attr', each_attr[0]) |
|
70 attr.setAttribute('value', each_attr[1]) |
|
71 node.appendChild(attr) |
|
72 |
|
73 # Each edge... |
|
74 for edge_from, edge_to in graph.edges(): |
|
75 edge = grxml.createElement('edge') |
|
76 edge.setAttribute('from',str(edge_from)) |
|
77 edge.setAttribute('to',str(edge_to)) |
|
78 edge.setAttribute('wt',str(graph.get_edge_weight(edge_from, edge_to))) |
|
79 edge.setAttribute('label',str(graph.get_edge_label(edge_from, edge_to))) |
|
80 grxmlr.appendChild(edge) |
|
81 for attr_name, attr_value in graph.get_edge_attributes(edge_from, edge_to): |
|
82 attr = grxml.createElement('attribute') |
|
83 attr.setAttribute('attr', attr_name) |
|
84 attr.setAttribute('value', attr_value) |
|
85 edge.appendChild(attr) |
|
86 |
|
87 return grxml.toprettyxml() |
|
88 |
|
89 |
|
90 def write_xml_hypergraph(hypergraph): |
|
91 """ |
|
92 Return a string specifying the given hypergraph as a XML document. |
|
93 |
|
94 @type hypergraph: hypergraph |
|
95 @param hypergraph: Hypergraph. |
|
96 |
|
97 @rtype: string |
|
98 @return: String specifying the graph as a XML document. |
|
99 """ |
|
100 |
|
101 # Document root |
|
102 grxml = Document() |
|
103 grxmlr = grxml.createElement('hypergraph') |
|
104 grxml.appendChild(grxmlr) |
|
105 |
|
106 # Each node... |
|
107 nodes = hypergraph.nodes() |
|
108 hyperedges = hypergraph.get_hyperedges() |
|
109 for each_node in (nodes + hyperedges): |
|
110 if (each_node in nodes): |
|
111 node = grxml.createElement('node') |
|
112 else: |
|
113 node = grxml.createElement('hyperedge') |
|
114 node.setAttribute('id',str(each_node)) |
|
115 grxmlr.appendChild(node) |
|
116 |
|
117 # and its outgoing edge |
|
118 for each_edge in hypergraph.get_links(each_node): |
|
119 edge = grxml.createElement('link') |
|
120 edge.setAttribute('to',str(each_edge)) |
|
121 node.appendChild(edge) |
|
122 |
|
123 return grxml.toprettyxml() |
|
124 |
|
125 |
|
126 def read_xml(graph, string): |
|
127 """ |
|
128 Read a graph from a XML document. Nodes and edges specified in the input will be added to the current graph. |
|
129 |
|
130 @type graph: graph |
|
131 @param graph: Graph |
|
132 |
|
133 @type string: string |
|
134 @param string: Input string in XML format specifying a graph. |
|
135 """ |
|
136 dom = parseString(string) |
|
137 |
|
138 # Read nodes... |
|
139 for each_node in dom.getElementsByTagName("node"): |
|
140 graph.add_node(each_node.getAttribute('id')) |
|
141 for each_attr in each_node.getElementsByTagName("attribute"): |
|
142 graph.add_node_attribute(each_node.getAttribute('id'), (each_attr.getAttribute('attr'), |
|
143 each_attr.getAttribute('value'))) |
|
144 |
|
145 # Read edges... |
|
146 for each_edge in dom.getElementsByTagName("edge"): |
|
147 graph.add_edge(each_edge.getAttribute('from'), each_edge.getAttribute('to'), \ |
|
148 wt=float(each_edge.getAttribute('wt')), label=each_edge.getAttribute('label')) |
|
149 for each_attr in each_edge.getElementsByTagName("attribute"): |
|
150 attr_tuple = (each_attr.getAttribute('attr'), each_attr.getAttribute('value')) |
|
151 if (attr_tuple not in graph.get_edge_attributes(each_edge.getAttribute('from'), \ |
|
152 each_edge.getAttribute('to'))): |
|
153 graph.add_edge_attribute(each_edge.getAttribute('from'), \ |
|
154 each_edge.getAttribute('to'), attr_tuple) |
|
155 |
|
156 |
|
157 def read_xml_hypergraph(hypergraph, string): |
|
158 """ |
|
159 Read a graph from a XML document. Nodes and hyperedges specified in the input will be added to the current graph. |
|
160 |
|
161 @type hypergraph: hypergraph |
|
162 @param hypergraph: Hypergraph |
|
163 |
|
164 @type string: string |
|
165 @param string: Input string in XML format specifying a graph. |
|
166 """ |
|
167 dom = parseString(string) |
|
168 for each_node in dom.getElementsByTagName("node"): |
|
169 hypergraph.add_nodes(each_node.getAttribute('id')) |
|
170 for each_node in dom.getElementsByTagName("hyperedge"): |
|
171 hypergraph.add_hyperedges(each_node.getAttribute('id')) |
|
172 dom = parseString(string) |
|
173 for each_node in dom.getElementsByTagName("node"): |
|
174 for each_edge in each_node.getElementsByTagName("link"): |
|
175 hypergraph.link(each_node.getAttribute('id'), each_edge.getAttribute('to')) |
|
176 |
|
177 |
|
178 # DOT Language |
|
179 |
|
180 def _dot_node_str(graph, node, wt): |
|
181 line = '\t"%s" [ ' % str(node) |
|
182 attrlist = graph.get_node_attributes(node) |
|
183 for each in attrlist: |
|
184 attr = '%s="%s" ' % (each[0], each[1]) |
|
185 line = line + attr |
|
186 line = line + ']\n' |
|
187 return line |
|
188 |
|
189 |
|
190 def _dot_edge_str(graph, u, v, wt): |
|
191 line = '\t"%s" -- "%s" [ ' % (str(u), str(v)) |
|
192 attrlist = graph.get_edge_attributes(u, v) + [('label',graph.get_edge_label(u, v))] |
|
193 for each in attrlist: |
|
194 attr = '%s="%s" ' % (each[0], each[1]) |
|
195 line = line + attr |
|
196 line = line + ']\n' |
|
197 return line |
|
198 |
|
199 |
|
200 def _dot_arrow_str(graph, u, v, wt): |
|
201 line = '\t"%s" -> "%s" [ ' % (str(u), str(v)) |
|
202 attrlist = graph.get_edge_attributes(u, v) + [('label',graph.get_edge_label(u, v))] |
|
203 for each in attrlist: |
|
204 attr = '%s="%s" ' % (each[0], each[1]) |
|
205 line = line + attr |
|
206 line = line + ']\n' |
|
207 return line |
|
208 |
|
209 |
|
210 def write_dot_graph(graph, wt): |
|
211 """ |
|
212 Return a string specifying the given graph in DOT Language. |
|
213 |
|
214 @type graph: graph |
|
215 @param graph: Graph. |
|
216 |
|
217 @type wt: boolean |
|
218 @param wt: Whether edges should be labelled with its weight. |
|
219 |
|
220 @rtype: string |
|
221 @return: String specifying the graph in DOT Language. |
|
222 """ |
|
223 doc = 'graph graphname \n{\n' |
|
224 for node in graph: |
|
225 doc = doc + _dot_node_str(graph, node, wt) |
|
226 for edge in graph[node]: |
|
227 if (node >= edge): |
|
228 doc = doc + _dot_edge_str(graph, node, edge, wt) |
|
229 doc = doc + '}' |
|
230 return doc |
|
231 |
|
232 |
|
233 def write_dot_digraph(graph, wt): |
|
234 """ |
|
235 Return a string specifying the given digraph in DOT Language. |
|
236 |
|
237 @type graph: graph |
|
238 @param graph: Graph. |
|
239 |
|
240 @type wt: boolean |
|
241 @param wt: Whether arrows should be labelled with its weight. |
|
242 |
|
243 @rtype: string |
|
244 @return: String specifying the graph in DOT Language. |
|
245 """ |
|
246 doc = 'digraph graphname \n{\n' |
|
247 for node in graph: |
|
248 doc = doc + _dot_node_str(graph, node, wt) |
|
249 for edge in graph[node]: |
|
250 doc = doc + _dot_arrow_str(graph, node, edge, wt) |
|
251 doc = doc + '}' |
|
252 return doc |
|
253 |
|
254 |
|
255 def write_dot_hypergraph(hypergraph, coloured=False): |
|
256 """ |
|
257 Return a string specifying the given hypergraph in DOT Language. |
|
258 |
|
259 @type hypergraph: hypergraph |
|
260 @param hypergraph: Hypergraph. |
|
261 |
|
262 @type coloured: boolean |
|
263 @param coloured: Whether hyperedges should be coloured. |
|
264 |
|
265 @rtype: string |
|
266 @return: String specifying the hypergraph in DOT Language. |
|
267 """ |
|
268 # Start document |
|
269 doc = "" |
|
270 doc = doc + "graph graphname" + "\n{\n" |
|
271 colortable = {} |
|
272 colorcount = 0 |
|
273 |
|
274 |
|
275 # Add hyperedges |
|
276 color = '' |
|
277 for each_hyperedge in hypergraph.hyperedges(): |
|
278 colortable[each_hyperedge] = colors[colorcount % len(colors)] |
|
279 colorcount = colorcount + 1 |
|
280 if (coloured): |
|
281 color = " color=%s" % colortable[each_hyperedge] |
|
282 vars = { |
|
283 'hyperedge' : str(each_hyperedge), |
|
284 'color' : color |
|
285 } |
|
286 doc = doc + '\t"%(hyperedge)s" [shape=point %(color)s]\n' % vars |
|
287 |
|
288 color = "\n" |
|
289 # Add nodes and links |
|
290 for each_node in hypergraph.nodes(): |
|
291 doc = doc + "\t\"%s\"\n" % str(each_node) |
|
292 for each_link in hypergraph.links(each_node): |
|
293 if (coloured): |
|
294 color = " [color=%s]\n" % colortable[each_link] |
|
295 linkvars = { |
|
296 'node' : str(each_node), |
|
297 'hyperedge' : str(each_link) |
|
298 } |
|
299 doc = doc + '\t %(node)s -- %(hyperedge)s' % linkvars + color |
|
300 |
|
301 doc = doc + "}" |
|
302 return doc |