diff -r 342bebadd075 -r 88c486951f10 thirdparty/python-graph/graph/readwrite.py --- a/thirdparty/python-graph/graph/readwrite.py Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,302 +0,0 @@ -# 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