# Copyright (c) 2007-2008 Pedro Matiello <pmatiello@gmail.com>

#

# 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