diff -r 01f8c7aabb7e -r 06c2228e39cb app/graph/readwrite.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/app/graph/readwrite.py Wed Nov 26 23:56:19 2008 +0000 @@ -0,0 +1,302 @@ +# Copyright (c) 2007-2008 Pedro Matiello +# +# Permission is hereby granted, free of charge, to any person +# obtaining a copy of this software and associated documentation +# files (the "Software"), to deal in the Software without +# restriction, including without limitation the rights to use, +# copy, modify, merge, publish, distribute, sublicense, and/or sell +# copies of the Software, and to permit persons to whom the +# Software is furnished to do so, subject to the following +# conditions: + +# The above copyright notice and this permission notice shall be +# included in all copies or substantial portions of the Software. + +# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES +# OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND +# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT +# HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, +# WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR +# OTHER DEALINGS IN THE SOFTWARE. + + +""" +Functions for reading and writing graphs. + +@sort: read_xml, write_xml, write_dot_graph, write_dot_digraph, write_dot_hypergraph +""" + + +# Imports +from xml.dom.minidom import Document, parseString + + +# Values +colors = ['aquamarine4', 'blue4', 'brown4', 'cornflowerblue', 'cyan4', + 'darkgreen', 'darkorange3', 'darkorchid4', 'darkseagreen4', 'darkslategray', + 'deeppink4', 'deepskyblue4', 'firebrick3', 'hotpink3', 'indianred3', + 'indigo', 'lightblue4', 'lightseagreen', 'lightskyblue4', 'magenta4', + 'maroon', 'palevioletred3', 'steelblue', 'violetred3'] + + +# XML + +def write_xml(graph): + """ + Return a string specifying the given graph as a XML document. + + @type graph: graph + @param graph: Graph. + + @rtype: string + @return: String specifying the graph as a XML document. + """ + + # Document root + grxml = Document() + grxmlr = grxml.createElement('graph') + grxml.appendChild(grxmlr) + + # Each node... + for each_node in graph.nodes(): + node = grxml.createElement('node') + node.setAttribute('id',str(each_node)) + grxmlr.appendChild(node) + for each_attr in graph.get_node_attributes(each_node): + attr = grxml.createElement('attribute') + attr.setAttribute('attr', each_attr[0]) + attr.setAttribute('value', each_attr[1]) + node.appendChild(attr) + + # Each edge... + for edge_from, edge_to in graph.edges(): + edge = grxml.createElement('edge') + edge.setAttribute('from',str(edge_from)) + edge.setAttribute('to',str(edge_to)) + edge.setAttribute('wt',str(graph.get_edge_weight(edge_from, edge_to))) + edge.setAttribute('label',str(graph.get_edge_label(edge_from, edge_to))) + grxmlr.appendChild(edge) + for attr_name, attr_value in graph.get_edge_attributes(edge_from, edge_to): + attr = grxml.createElement('attribute') + attr.setAttribute('attr', attr_name) + attr.setAttribute('value', attr_value) + edge.appendChild(attr) + + return grxml.toprettyxml() + + +def write_xml_hypergraph(hypergraph): + """ + Return a string specifying the given hypergraph as a XML document. + + @type hypergraph: hypergraph + @param hypergraph: Hypergraph. + + @rtype: string + @return: String specifying the graph as a XML document. + """ + + # Document root + grxml = Document() + grxmlr = grxml.createElement('hypergraph') + grxml.appendChild(grxmlr) + + # Each node... + nodes = hypergraph.nodes() + hyperedges = hypergraph.get_hyperedges() + for each_node in (nodes + hyperedges): + if (each_node in nodes): + node = grxml.createElement('node') + else: + node = grxml.createElement('hyperedge') + node.setAttribute('id',str(each_node)) + grxmlr.appendChild(node) + + # and its outgoing edge + for each_edge in hypergraph.get_links(each_node): + edge = grxml.createElement('link') + edge.setAttribute('to',str(each_edge)) + node.appendChild(edge) + + return grxml.toprettyxml() + + +def read_xml(graph, string): + """ + Read a graph from a XML document. Nodes and edges specified in the input will be added to the current graph. + + @type graph: graph + @param graph: Graph + + @type string: string + @param string: Input string in XML format specifying a graph. + """ + dom = parseString(string) + + # Read nodes... + for each_node in dom.getElementsByTagName("node"): + graph.add_node(each_node.getAttribute('id')) + for each_attr in each_node.getElementsByTagName("attribute"): + graph.add_node_attribute(each_node.getAttribute('id'), (each_attr.getAttribute('attr'), + each_attr.getAttribute('value'))) + + # Read edges... + for each_edge in dom.getElementsByTagName("edge"): + graph.add_edge(each_edge.getAttribute('from'), each_edge.getAttribute('to'), \ + wt=float(each_edge.getAttribute('wt')), label=each_edge.getAttribute('label')) + for each_attr in each_edge.getElementsByTagName("attribute"): + attr_tuple = (each_attr.getAttribute('attr'), each_attr.getAttribute('value')) + if (attr_tuple not in graph.get_edge_attributes(each_edge.getAttribute('from'), \ + each_edge.getAttribute('to'))): + graph.add_edge_attribute(each_edge.getAttribute('from'), \ + each_edge.getAttribute('to'), attr_tuple) + + +def read_xml_hypergraph(hypergraph, string): + """ + Read a graph from a XML document. Nodes and hyperedges specified in the input will be added to the current graph. + + @type hypergraph: hypergraph + @param hypergraph: Hypergraph + + @type string: string + @param string: Input string in XML format specifying a graph. + """ + dom = parseString(string) + for each_node in dom.getElementsByTagName("node"): + hypergraph.add_nodes(each_node.getAttribute('id')) + for each_node in dom.getElementsByTagName("hyperedge"): + hypergraph.add_hyperedges(each_node.getAttribute('id')) + dom = parseString(string) + for each_node in dom.getElementsByTagName("node"): + for each_edge in each_node.getElementsByTagName("link"): + hypergraph.link(each_node.getAttribute('id'), each_edge.getAttribute('to')) + + +# DOT Language + +def _dot_node_str(graph, node, wt): + line = '\t"%s" [ ' % str(node) + attrlist = graph.get_node_attributes(node) + for each in attrlist: + attr = '%s="%s" ' % (each[0], each[1]) + line = line + attr + line = line + ']\n' + return line + + +def _dot_edge_str(graph, u, v, wt): + line = '\t"%s" -- "%s" [ ' % (str(u), str(v)) + attrlist = graph.get_edge_attributes(u, v) + [('label',graph.get_edge_label(u, v))] + for each in attrlist: + attr = '%s="%s" ' % (each[0], each[1]) + line = line + attr + line = line + ']\n' + return line + + +def _dot_arrow_str(graph, u, v, wt): + line = '\t"%s" -> "%s" [ ' % (str(u), str(v)) + attrlist = graph.get_edge_attributes(u, v) + [('label',graph.get_edge_label(u, v))] + for each in attrlist: + attr = '%s="%s" ' % (each[0], each[1]) + line = line + attr + line = line + ']\n' + return line + + +def write_dot_graph(graph, wt): + """ + Return a string specifying the given graph in DOT Language. + + @type graph: graph + @param graph: Graph. + + @type wt: boolean + @param wt: Whether edges should be labelled with its weight. + + @rtype: string + @return: String specifying the graph in DOT Language. + """ + doc = 'graph graphname \n{\n' + for node in graph: + doc = doc + _dot_node_str(graph, node, wt) + for edge in graph[node]: + if (node >= edge): + doc = doc + _dot_edge_str(graph, node, edge, wt) + doc = doc + '}' + return doc + + +def write_dot_digraph(graph, wt): + """ + Return a string specifying the given digraph in DOT Language. + + @type graph: graph + @param graph: Graph. + + @type wt: boolean + @param wt: Whether arrows should be labelled with its weight. + + @rtype: string + @return: String specifying the graph in DOT Language. + """ + doc = 'digraph graphname \n{\n' + for node in graph: + doc = doc + _dot_node_str(graph, node, wt) + for edge in graph[node]: + doc = doc + _dot_arrow_str(graph, node, edge, wt) + doc = doc + '}' + return doc + + +def write_dot_hypergraph(hypergraph, coloured=False): + """ + Return a string specifying the given hypergraph in DOT Language. + + @type hypergraph: hypergraph + @param hypergraph: Hypergraph. + + @type coloured: boolean + @param coloured: Whether hyperedges should be coloured. + + @rtype: string + @return: String specifying the hypergraph in DOT Language. + """ + # Start document + doc = "" + doc = doc + "graph graphname" + "\n{\n" + colortable = {} + colorcount = 0 + + + # Add hyperedges + color = '' + for each_hyperedge in hypergraph.hyperedges(): + colortable[each_hyperedge] = colors[colorcount % len(colors)] + colorcount = colorcount + 1 + if (coloured): + color = " color=%s" % colortable[each_hyperedge] + vars = { + 'hyperedge' : str(each_hyperedge), + 'color' : color + } + doc = doc + '\t"%(hyperedge)s" [shape=point %(color)s]\n' % vars + + color = "\n" + # Add nodes and links + for each_node in hypergraph.nodes(): + doc = doc + "\t\"%s\"\n" % str(each_node) + for each_link in hypergraph.links(each_node): + if (coloured): + color = " [color=%s]\n" % colortable[each_link] + linkvars = { + 'node' : str(each_node), + 'hyperedge' : str(each_link) + } + doc = doc + '\t %(node)s -- %(hyperedge)s' % linkvars + color + + doc = doc + "}" + return doc