py_tasks_melange: comparison scripts/graph/__init_

equal deleted inserted replaced

-:c1f9435bb645
+:32a30f609530
+# Copyright (c) 2007-2008 Pedro Matiello <pmatiello@gmail.com>
+#                         Christian Muise <christian.muise@gmail.com>
+#                         Nathan Davis <davisn90210@gmail.com>
+#                         Zsolt Haraszti <zsolt@drawwell.net>
+#
+# 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.
+"""
+python-graph
+A library for working with graphs in Python.
+@version: 1.3.1
+"""
+# Imports
+import accessibility
+import generators
+import minmax
+import searching
+import sorting
+import readwrite
+import traversal
+# Graph class --------------------------------------------------------------------------------------
+class graph (object):
+	"""
+	Graph class.
+	Graphs are built of nodes and edges.
+	@sort:  __init__, __getitem__, __iter__, __len__, __str__, add_edge, add_edge_attribute,
+	add_graph, add_node, add_node_attribute, add_nodes, add_spanning_tree, complete, del_edge,
+	del_node, edges, get_edge_attributes, get_edge_label, get_edge_weight, get_node_attributes,
+	has_edge, has_node, inverse, neighbors, nodes, order, set_edge_label, set_edge_weight,
+	traversal, generate, read, write, accessibility, breadth_first_search, connected_components,
+	cut_edges, cut_nodes, depth_first_search, minimal_spanning_tree, shortest_path
+	"""
+	def __init__(self):
+		"""
+		Initialize a graph.
+		"""
+		self.node_neighbors = {}		# Pairing: Node -> Neighbors
+		self.edge_properties = {}		# Pairing: Edge -> (Label, Weight)
+		self.node_attr = {}				# Pairing: Node -> Attributes
+		self.edge_attr = {}				# Pairing: Edge -> Attributes
+	def __str__(self):
+		"""
+		Return a string representing the graph when requested by str() (or print).
+		@rtype:  string
+		@return: String representing the graph.
+		"""
+		return "<graph object " + str(self.nodes()) + " " + str(self.edges()) + ">"
+	def __len__(self):
+		"""
+		Return the order of the graph when requested by len().
+		@rtype:  number
+		@return: Size of the graph.
+		"""
+		return len(self.node_neighbors)
+	def __iter__(self):
+		"""
+		Return a iterator passing through all nodes in the graph.
+		@rtype:  iterator
+		@return: Iterator passing through all nodes in the graph.
+		"""
+		for each in self.node_neighbors.iterkeys():
+			yield each
+	def __getitem__(self, node):
+		"""
+		Return a iterator passing through all neighbors of the given node.
+		@rtype:  iterator
+		@return: Iterator passing through all neighbors of the given node.
+		"""
+		for each in self.node_neighbors[node]:
+			yield each
+	def read(self, string, fmt='xml'):
+		"""
+		Read a graph from a string. Nodes and edges specified in the input will be added to the
+		current graph.
+		@type  string: string
+		@param string: Input string specifying a graph.
+		@type  fmt: string
+		@param fmt: Input format. Possible formats are:
+			1. 'xml' - XML (default)
+		"""
+		if (fmt == 'xml'):
+			readwrite.read_xml(self, string)
+	def write(self, fmt='xml'):
+		"""
+		Write the graph to a string. Depending of the output format, this string can be used by
+		read() to rebuild the graph.
+		@type  fmt: string
+		@param fmt: Output format. Possible formats are:
+			1. 'xml' - XML (default)
+			2. 'dot' - DOT Language (for GraphViz)
+			3. 'dotwt' - DOT Language with weight information
+		@rtype:  string
+		@return: String specifying the graph.
+		"""
+		if (fmt == 'xml'):
+			return readwrite.write_xml(self)
+		elif (fmt == 'dot'):
+			return readwrite.write_dot_graph(self, False)
+		elif (fmt == 'dotwt'):
+			return readwrite.write_dot_graph(self, True)
+	def generate(self, num_nodes, num_edges, weight_range=(1, 1)):
+		"""
+		Add nodes and random edges to the graph.
+		@type  num_nodes: number
+		@param num_nodes: Number of nodes.
+		@type  num_edges: number
+		@param num_edges: Number of edges.
+		@type  weight_range: tuple
+		@param weight_range: tuple of two integers as lower and upper limits on randomly generated
+		weights (uniform distribution).
+		"""
+		generators.generate(self, num_nodes, num_edges, weight_range)
+	def nodes(self):
+		"""
+		Return node list.
+		@rtype:  list
+		@return: Node list.
+		"""
+		return self.node_neighbors.keys()
+	def neighbors(self, node):
+		"""
+		Return all nodes that are directly accessible from given node.
+		@type  node: node
+		@param node: Node identifier
+		@rtype:  list
+		@return: List of nodes directly accessible from given node.
+		"""
+		return self.node_neighbors[node]
+	def edges(self):
+		"""
+		Return all edges in the graph.
+		@rtype:  list
+		@return: List of all edges in the graph.
+		"""
+		return self.edge_properties.keys()
+	def has_node(self, node):
+		"""
+		Return whether the requested node exists.
+		@type  node: node
+		@param node: Node identifier
+		@rtype:  boolean
+		@return: Truth-value for node existence.
+		"""
+		return self.node_neighbors.has_key(node)
+	def add_node(self, node, attrs=[]):
+		"""
+		Add given node to the graph.
+		@attention: While nodes can be of any type, it's strongly recommended to use only numbers
+		and single-line strings as node identifiers if you intend to use write().
+		@type  node: node
+		@param node: Node identifier.
+		@type  attrs: list
+		@param attrs: List of node attributes specified as (attribute, value) tuples.
+		"""
+		if (not node in self.node_neighbors):
+			self.node_neighbors[node] = []
+			self.node_attr[node] = attrs
+	def add_nodes(self, nodelist):
+		"""
+		Add given nodes to the graph.
+		@attention: While nodes can be of any type, it's strongly recommended to use only numbers
+		and single-line strings as node identifiers if you intend to use write().
+		@type  nodelist: list
+		@param nodelist: List of nodes to be added to the graph.
+		"""
+		for each in nodelist:
+			self.add_node(each)
+	def add_edge(self, u, v, wt=1, label='', attrs=[]):
+		"""
+		Add an edge (u,v) to the graph connecting nodes u and v.
+		@type  u: node
+		@param u: One node.
+		@type  v: node
+		@param v: Other node.
+		@type  wt: number
+		@param wt: Edge weight.
+		@type  label: string
+		@param label: Edge label.
+		@type  attrs: list
+		@param attrs: List of node attributes specified as (attribute, value) tuples.
+		"""
+		if (v not in self.node_neighbors[u] and u not in self.node_neighbors[v]):
+			self.node_neighbors[u].append(v)
+			self.node_neighbors[v].append(u)
+			self.edge_properties[(u, v)] = [label, wt]
+			self.edge_properties[(v, u)] = [label, wt]
+			self.edge_attr[(u, v)] = attrs
+			self.edge_attr[(v, u)] = attrs
+	def del_node(self, node):
+		"""
+		Remove a node from the graph.
+		@type  node: node
+		@param node: Node identifier.
+		"""
+		for each in list(self.neighbors(node)):
+			self.del_edge(each, node)
+		del(self.node_neighbors[node])
+		del(self.node_attr[node])
+	def del_edge(self, u, v):
+		"""
+		Remove an edge (u, v) from the graph.
+		@type  u: node
+		@param u: One node.
+		@type  v: node
+		@param v: Other node.
+		"""
+		self.node_neighbors[u].remove(v)
+		self.node_neighbors[v].remove(u)
+		del(self.edge_properties[(u,v)])
+		del(self.edge_properties[(v,u)])
+		del(self.edge_attr[(u,v)])
+		del(self.edge_attr[(v,u)])
+	def get_edge_weight(self, u, v):
+		"""
+		Get the weight of an edge.
+		@type  u: node
+		@param u: One node.
+		@type  v: node
+		@param v: Other node.
+		@rtype:  number
+		@return: Edge weight.
+		"""
+		return self.edge_properties[(u, v)][1]
+	def set_edge_weight(self, u, v, wt):
+		"""
+		Set the weight of an edge.
+		@type  u: node
+		@param u: One node.
+		@type  v: node
+		@param v: Other node.
+		@type  wt: number
+		@param wt: Edge weight.
+		"""
+		self.edge_properties[(u, v)][1] = wt
+		self.edge_properties[(v, u)][1] = wt
+	def get_edge_label(self, u, v):
+		"""
+		Get the label of an edge.
+		@type  u: node
+		@param u: One node.
+		@type  v: node
+		@param v: Other node.
+		@rtype:  string
+		@return: Edge label
+		"""
+		return self.edge_properties[(u, v)][0]
+	def set_edge_label(self, u, v, label):
+		"""
+		Set the label of an edge.
+		@type  u: node
+		@param u: One node.
+		@type  v: node
+		@param v: Other node.
+		@type  label: string
+		@param label: Edge label.
+		"""
+		self.edge_properties[(u, v)][0] = label
+		self.edge_properties[(v, u)][0] = label
+	def add_node_attribute(self, node, attr):
+		"""
+		Add attribute to the given node.
+		@type  node: node
+		@param node: Node identifier
+		@type  attr: tuple
+		@param attr: Node attribute specified as a tuple in the form (attribute, value).
+		"""
+		self.node_attr[node] = self.node_attr[node] + [attr]
+	def get_node_attributes(self, node):
+		"""
+		Return the attributes of the given node.
+		@type  node: node
+		@param node: Node identifier
+		@rtype:  list
+		@return: List of attributes specified tuples in the form (attribute, value).
+		"""
+		return self.node_attr[node]
+	def add_edge_attribute(self, u, v, attr):
+		"""
+		Add attribute to the given edge.
+		@type  u: node
+		@param u: One node.
+		@type  v: node
+		@param v: Other node.
+		@type  attr: tuple
+		@param attr: Node attribute specified as a tuple in the form (attribute, value).
+		"""
+		self.edge_attr[(u,v)] = self.edge_attr[(u,v)] + [attr]
+		self.edge_attr[(v,u)] = self.edge_attr[(v,u)] + [attr]
+	def get_edge_attributes(self, u, v):
+		"""
+		Return the attributes of the given edge.
+		@type  u: node
+		@param u: One node.
+		@type  v: node
+		@param v: Other node.
+		@rtype:  list
+		@return: List of attributes specified tuples in the form (attribute, value).
+		"""
+		return self.edge_attr[(u,v)]
+	def has_edge(self, u, v):
+		"""
+		Return whether an edge between nodes u and v exists.
+		@type  u: node
+		@param u: One node.
+		@type  v: node
+		@param v: Other node.
+		@rtype:  boolean
+		@return: Truth-value for edge existence.
+		"""
+		return self.edge_properties.has_key((u,v)) and self.edge_properties.has_key((v,u))
+	def order(self, node):
+		"""
+		Return the order of the given node.
+		@rtype:  number
+		@return: Order of the given node.
+		"""
+		return len(self.neighbors(node))
+	def complete(self):
+		"""
+		Make the graph a complete graph.
+		@attention: This will modify the current graph.
+		"""
+		for each in self.nodes():
+			for other in self.nodes():
+				if (each != other):
+					self.add_edge(each, other)
+	def inverse(self):
+		"""
+		Return the inverse of the graph.
+		@rtype:  graph
+		@return: Complement graph for the graph.
+		"""
+		inv = graph()
+		inv.add_nodes(self.nodes())
+		inv.complete()
+		for each in self.edges():
+			if (inv.has_edge(each[0], each[1])):
+				inv.del_edge(each[0], each[1])
+		return inv
+	def add_graph(self, graph):
+		"""
+		Add other graph to the graph.
+		@attention: Attributes and labels are not preserved.
+		@type  graph: graph
+		@param graph: Graph
+		"""
+		self.add_nodes(graph.nodes())
+		for each_node in graph.nodes():
+			for each_edge in graph.neighbors(each_node):
+				self.add_edge(each_node, each_edge)
+	def add_spanning_tree(self, st):
+		"""
+		Add a spanning tree to the graph.
+		@type  st: dictionary
+		@param st: Spanning tree.
+		"""
+		self.add_nodes(st.keys())
+		for each in st:
+			if (st[each] is not None):
+				self.add_edge(st[each], each)
+	def traversal(self, node, order='pre'):
+		"""
+		Graph traversal iterator.
+		@type  node: node
+		@param node: Node.
+		@type  order: string
+		@param order: traversal ordering. Possible values are:
+			2. 'pre' - Preordering (default)
+			1. 'post' - Postordering
+		@rtype:  iterator
+		@return: Traversal iterator.
+		"""
+		for each in traversal.traversal(self, node, order):
+			yield each
+	def depth_first_search(self, root=None):
+		"""
+		Depht-first search.
+		@type  root: node
+		@param root: Optional root node (will explore only root's connected component)
+		@rtype:  tuple
+		@return:  tupple containing a dictionary and two lists:
+			1. Generated spanning tree
+			2. Graph's preordering
+			3. Graph's postordering
+		"""
+		return searching.depth_first_search(self, root)
+	def breadth_first_search(self, root=None):
+		"""
+		Breadth-first search.
+		@type  root: node
+		@param root: Optional root node (will explore only root's connected component)
+		@rtype:  dictionary
+		@return: A tuple containing a dictionary and a list.
+			1. Generated spanning tree
+			2. Graph's level-based ordering
+		"""
+		return searching.breadth_first_search(self, root)
+	def accessibility(self):
+		"""
+		Accessibility matrix (transitive closure).
+		@rtype:  dictionary
+		@return: Accessibility information for each node.
+		"""
+		return accessibility.accessibility(self)
+	def connected_components(self):
+		"""
+		Connected components.
+		@attention: Indentification of connected components is meaningful only for non-directed
+		graphs.
+		@rtype:  dictionary
+		@return: Pairing that associates each node to its connected component.
+		"""
+		return accessibility.connected_components(self)
+	def minimal_spanning_tree(self, root=None):
+		"""
+		Minimal spanning tree.
+		@type  root: node
+		@param root: Optional root node (will explore only root's connected component)
+		@attention: Minimal spanning tree meaningful only for weighted graphs.
+		@rtype:  list
+		@return: Generated spanning tree.
+		"""
+		return minmax.minimal_spanning_tree(self, root)
+	def shortest_path(self, source):
+		"""
+		Return the shortest path distance between source node and all other nodes using Dijkstra's
+		algorithm.
+		@attention: All weights must be nonnegative.
+		@type  source: node
+		@param source: Node from which to start the search.
+		@rtype:  tuple
+		@return: A tuple containing two dictionaries, each keyed by target nodes.
+			1. Shortest path spanning tree
+			2. Shortest distance from given source to each target node
+		Inaccessible target nodes do not appear in either dictionary.
+		"""
+		return minmax.shortest_path(self, source)
+	def cut_edges(self):
+		"""
+		Return the cut-edges of the given graph.
+		@rtype:  list
+		@return: List of cut-edges.
+		"""
+		return accessibility.cut_edges(self)
+	def cut_nodes(self):
+		"""
+		Return the cut-nodes of the given graph.
+		@rtype:  list
+		@return: List of cut-nodes.
+		"""
+		return accessibility.cut_nodes(self)
+# Digraph class ------------------------------------------------------------------------------------
+class digraph (object):
+	"""
+	Digraph class.
+	Digraphs are built of nodes and directed edges.
+	@sort: __init__, __getitem__, __iter__, __len__, __str__, add_edge, add_edge_attribute,
+	add_graph, add_node, add_node_attribute, add_nodes, add_spanning_tree, complete, degree,
+	del_edge, del_node, edges, get_edge_attributes, get_edge_label, get_edge_weight,
+	get_node_attributes, has_edge, has_node, incidents, inverse, neighbors, nodes, order,
+	set_edge_label, set_edge_weight, traversal, generate, read, write, accessibility,
+	breadth_first_search, cut_edges, cut_nodes, depth_first_search, minimal_spanning_tree,
+	mutual_accessibility, shortest_path, topological_sorting
+	"""
+	def __init__(self):
+		"""
+		Initialize a digraph.
+		"""
+		self.node_neighbors = {}	# Pairing: Node -> Neighbors
+		self.edge_properties = {}	# Pairing: Edge -> (Label, Weight)
+		self.node_incidence = {}	# Pairing: Node -> Incident nodes
+		self.node_attr = {}			# Pairing: Node -> Attributes
+		self.edge_attr = {}			# Pairing: Edge -> Attributes
+	def __str__(self):
+		"""
+		Return a string representing the digraph when requested by str() (or print).
+		@rtype:  string
+		@return: String representing the graph.
+		"""
+		return "<graph object " + str(self.nodes()) + " " + str(self.edges()) + ">"
+	def __len__(self):
+		"""
+		Return the order of the digraph when requested by len().
+		@rtype:  number
+		@return: Size of the graph.
+		"""
+		return len(self.node_neighbors)
+	def __iter__(self):
+		"""
+		Return a iterator passing through all nodes in the digraph.
+		@rtype:  iterator
+		@return: Iterator passing through all nodes in the digraph.
+		"""
+		for each in self.node_neighbors.iterkeys():
+			yield each
+	def __getitem__(self, node):
+		"""
+		Return a iterator passing through all neighbors of the given node.
+		@rtype:  iterator
+		@return: Iterator passing through all neighbors of the given node.
+		"""
+		for each in self.node_neighbors[node]:
+			yield each
+	def read(self, string, fmt='xml'):
+		"""
+		Read a graph from a string. Nodes and edges specified in the input will be added to the
+		current graph.
+		@type  string: string
+		@param string: Input string specifying a graph.
+		@type  fmt: string
+		@param fmt: Input format. Possible formats are:
+			1. 'xml' - XML (default)
+		"""
+		if (fmt == 'xml'):
+			readwrite.read_xml(self, string)
+	def write(self, fmt='xml'):
+		"""
+		Write the graph to a string. Depending of the output format, this string can be used by
+		read() to rebuild the graph.
+		@type  fmt: string
+		@param fmt: Output format. Possible formats are:
+			1. 'xml' - XML (default)
+			2. 'dot' - DOT Language (for GraphViz)
+			3. 'dotwt' - DOT Language with weight information
+		@rtype:  string
+		@return: String specifying the graph.
+		"""
+		if (fmt == 'xml'):
+			return readwrite.write_xml(self)
+		elif (fmt == 'dot'):
+			return readwrite.write_dot_digraph(self, False)
+		elif (fmt == 'dotwt'):
+			return readwrite.write_dot_digraph(self, True)
+	def generate(self, num_nodes, num_edges, weight_range=(1, 1)):
+		"""
+		Add nodes and random edges to the graph.
+		@type  num_nodes: number
+		@param num_nodes: Number of nodes.
+		@type  num_edges: number
+		@param num_edges: Number of edges.
+		@type  weight_range: tuple
+		@param weight_range: tuple of two integers as lower and upper limits on randomly generated
+		weights (uniform distribution).
+		"""
+		generators.generate(self, num_nodes, num_edges, weight_range)
+	def nodes(self):
+		"""
+		Return node list.
+		@rtype:  list
+		@return: Node list.
+		"""
+		return self.node_neighbors.keys()
+	def neighbors(self, node):
+		"""
+		Return all nodes that are directly accessible from given node.
+		@type  node: node
+		@param node: Node identifier
+		@rtype:  list
+		@return: List of nodes directly accessible from given node.
+		"""
+		return self.node_neighbors[node]
+	def incidents(self, node):
+		"""
+		Return all nodes that are incident to the given node.
+		@type  node: node
+		@param node: Node identifier
+		@rtype:  list
+		@return: List of nodes directly accessible from given node.
+		"""
+		return self.node_incidence[node]
+	def edges(self):
+		"""
+		Return all edges in the graph.
+		@rtype:  list
+		@return: List of all edges in the graph.
+		"""
+		return self.edge_properties.keys()
+	def has_node(self, node):
+		"""
+		Return whether the requested node exists.
+		@type  node: node
+		@param node: Node identifier
+		@rtype:  boolean
+		@return: Truth-value for node existence.
+		"""
+		return self.node_neighbors.has_key(node)
+	def add_node(self, node, attrs=[]):
+		"""
+		Add given node to the graph.
+		@attention: While nodes can be of any type, it's strongly recommended to use only numbers
+		and single-line strings as node identifiers if you intend to use write().
+		@type  node: node
+		@param node: Node identifier.
+		@type  attrs: list
+		@param attrs: List of node attributes specified as (attribute, value) tuples.
+		"""
+		if (node not in self.node_neighbors):
+			self.node_neighbors[node] = []
+			self.node_incidence[node] = []
+			self.node_attr[node] = attrs
+	def add_nodes(self, nodelist):
+		"""
+		Add given nodes to the graph.
+		@attention: While nodes can be of any type, it's strongly recommended to use only numbers
+		and single-line strings as node identifiers if you intend to use write().
+		@type  nodelist: list
+		@param nodelist: List of nodes to be added to the graph.
+		"""
+		for each in nodelist:
+			self.add_node(each)
+	def add_edge(self, u, v, wt=1, label='', attrs=[]):
+		"""
+		Add an directed edge (u,v) to the graph connecting nodes u to v.
+		@type  u: node
+		@param u: One node.
+		@type  v: node
+		@param v: Other node.
+		@type  wt: number
+		@param wt: Edge weight.
+		@type  label: string
+		@param label: Edge label.
+		@type  attrs: list
+		@param attrs: List of node attributes specified as (attribute, value) tuples.
+		"""
+		if (v not in self.node_neighbors[u]):
+			self.node_neighbors[u].append(v)
+			self.node_incidence[v].append(u)
+			self.edge_properties[(u, v)] = [label, wt]
+			self.edge_attr[(u, v)] = attrs
+	def del_node(self, node):
+		"""
+		Remove a node from the graph.
+		@type  node: node
+		@param node: Node identifier.
+		"""
+		for each in list(self.incidents(node)):
+			self.del_edge(each, node)
+		for each in list(self.neighbors(node)):
+			self.del_edge(node, each)
+		del(self.node_neighbors[node])
+		del(self.node_incidence[node])
+		del(self.node_attr[node])
+	def del_edge(self, u, v):
+		"""
+		Remove an directed edge (u, v) from the graph.
+		@type  u: node
+		@param u: One node.
+		@type  v: node
+		@param v: Other node.
+		"""
+		self.node_neighbors[u].remove(v)
+		self.node_incidence[v].remove(u)
+		del(self.edge_properties[(u,v)])
+		del(self.edge_attr[(u,v)])
+	def get_edge_weight(self, u, v):
+		"""
+		Get the weight of an edge.
+		@type  u: node
+		@param u: One node.
+		@type  v: node
+		@param v: Other node.
+		@rtype:  number
+		@return: Edge weight.
+		"""
+		return self.edge_properties[(u, v)][1]
+	def set_edge_weight(self, u, v, wt):
+		"""
+		Set the weight of an edge.
+		@type  u: node
+		@param u: One node.
+		@type  v: node
+		@param v: Other node.
+		@type  wt: number
+		@param wt: Edge weight.
+		"""
+		self.edge_properties[(u, v)][1] = wt
+	def get_edge_label(self, u, v):
+		"""
+		Get the label of an edge.
+		@type  u: node
+		@param u: One node.
+		@type  v: node
+		@param v: Other node.
+		@rtype:  string
+		@return: Edge label
+		"""
+		return self.edge_properties[(u, v)][0]
+	def set_edge_label(self, u, v, label):
+		"""
+		Set the label of an edge.
+		@type  u: node
+		@param u: One node.
+		@type  v: node
+		@param v: Other node.
+		@type  label: string
+		@param label: Edge label.
+		"""
+		self.edge_properties[(u, v)][0] = label
+	def add_node_attribute(self, node, attr):
+		"""
+		Add attribute to the given node.
+		@type  node: node
+		@param node: Node identifier
+		@type  attr: tuple
+		@param attr: Node attribute specified as a tuple in the form (attribute, value).
+		"""
+		self.node_attr[node] = self.node_attr[node] + [attr]
+	def get_node_attributes(self, node):
+		"""
+		Return the attributes of the given node.
+		@type  node: node
+		@param node: Node identifier
+		@rtype:  list
+		@return: List of attributes specified tuples in the form (attribute, value).
+		"""
+		return self.node_attr[node]
+	def add_edge_attribute(self, u, v, attr):
+		"""
+		Add attribute to the given edge.
+		@type  u: node
+		@param u: One node.
+		@type  v: node
+		@param v: Other node.
+		@type  attr: tuple
+		@param attr: Node attribute specified as a tuple in the form (attribute, value).
+		"""
+		self.edge_attr[(u,v)] = self.edge_attr[(u,v)] + [attr]
+	def get_edge_attributes(self, u, v):
+		"""
+		Return the attributes of the given edge.
+		@type  u: node
+		@param u: One node.
+		@type  v: node
+		@param v: Other node.
+		@rtype:  list
+		@return: List of attributes specified tuples in the form (attribute, value).
+		"""
+		return self.edge_attr[(u,v)]
+	def has_edge(self, u, v):
+		"""
+		Return whether an edge between nodes u and v exists.
+		@type  u: node
+		@param u: One node.
+		@type  v: node
+		@param v: Other node.
+		@rtype:  boolean
+		@return: Truth-value for edge existence.
+		"""
+		return self.edge_properties.has_key((u,v))
+	def order(self, node):
+		"""
+		Return the order of the given node.
+		@rtype:  number
+		@return: Order of the given node.
+		"""
+		return len(self.neighbors(node))
+	def degree(self, node):
+		"""
+		Return the degree of the given node.
+		@rtype:  number
+		@return: Order of the given node.
+		"""
+		return len(self.node_incidence[node])
+	def complete(self):
+		"""
+		Make the graph a complete graph.
+		@attention: This will modify the current graph.
+		"""
+		for each in self.nodes():
+			for other in self.nodes():
+				if (each != other):
+					self.add_edge(each, other)
+	def inverse(self):
+		"""
+		Return the inverse of the graph.
+		@rtype:  graph
+		@return: Complement graph for the graph.
+		"""
+		inv = digraph()
+		inv.add_nodes(self.nodes())
+		inv.complete()
+		for each in self.edges():
+			inv.del_edge(each[0], each[1])
+		return inv
+	def add_graph(self, graph):
+		"""
+		Add other graph to the graph.
+		@attention: Attributes and labels are not preserved.
+		@type  graph: graph
+		@param graph: Graph
+		"""
+		self.add_nodes(graph.nodes())
+		for each_node in graph.nodes():
+			for each_edge in graph.neighbors(each_node):
+				self.add_edge(each_node, each_edge)
+	def add_spanning_tree(self, st):
+		"""
+		Add a spanning tree to the graph.
+		@type  st: dictionary
+		@param st: Spanning tree.
+		"""
+		self.add_nodes(st.keys())
+		for each in st:
+			if (st[each] is not None):
+				self.add_edge(st[each], each)
+	def traversal(self, node, order='pre'):
+		"""
+		Graph traversal iterator.
+		@type  node: node
+		@param node: Node.
+		@type  order: string
+		@param order: traversal ordering. Possible values are:
+			2. 'pre' - Preordering (default)
+			1. 'post' - Postordering
+		@rtype:  iterator
+		@return: Traversal iterator.
+		"""
+		for each in traversal.traversal(self, node, order):
+			yield each
+	def depth_first_search(self, root=None):
+		"""
+		Depht-first search.
+		@type  root: node
+		@param root: Optional root node (will explore only root's connected component)
+		@rtype:  tuple
+		@return:  tupple containing a dictionary and two lists:
+			1. Generated spanning tree
+			2. Graph's preordering
+			3. Graph's postordering
+		"""
+		return searching.depth_first_search(self, root)
+	def accessibility(self):
+		"""
+		Accessibility matrix (transitive closure).
+		@rtype:  dictionary
+		@return: Accessibility information for each node.
+		"""
+		return accessibility.accessibility(self)
+	def breadth_first_search(self, root=None):
+		"""
+		Breadth-first search.
+		@type  root: node
+		@param root: Optional root node (will explore only root's connected component)
+		@rtype:  dictionary
+		@return: A tuple containing a dictionary and a list.
+			1. Generated spanning tree
+			2. Graph's level-based ordering
+		"""
+		return searching.breadth_first_search(self, root)
+	def mutual_accessibility(self):
+		"""
+		Mutual-accessibility matrix (strongly connected components).
+		@rtype:  list
+		@return: Mutual-accessibility information for each node.
+		"""
+		return accessibility.mutual_accessibility(self)
+	def topological_sorting(self):
+		"""
+		Topological sorting.
+		@attention: Topological sorting is meaningful only for directed acyclic graphs.
+		@rtype:  list
+		@return: Topological sorting for the graph.
+		"""
+		return sorting.topological_sorting(self)
+	def minimal_spanning_tree(self, root=None):
+		"""
+		Minimal spanning tree.
+		@type  root: node
+		@param root: Optional root node (will explore only root's connected component)
+		@attention: Minimal spanning tree meaningful only for weighted graphs.
+		@rtype:  list
+		@return: Generated spanning tree.
+		"""
+		return minmax.minimal_spanning_tree(self, root)
+	def shortest_path(self, source):
+		"""
+		Return the shortest path distance between source node and all other nodes using Dijkstra's
+		algorithm.
+		@attention: All weights must be nonnegative.
+		@type  source: node
+		@param source: Node from which to start the search.
+		@rtype:  tuple
+		@return: A tuple containing two dictionaries, each keyed by target nodes.
+			1. Shortest path spanning tree
+			2. Shortest distance from given source to each target node
+		Inaccessible target nodes do not appear in either dictionary.
+		"""
+		return minmax.shortest_path(self, source)
+	def cut_edges(self):
+		"""
+		Return the cut-edges of the given graph.
+		@rtype:  list
+		@return: List of cut-edges.
+		"""
+		return accessibility.cut_edges(self)
+	def cut_nodes(self):
+		"""
+		Return the cut-nodes of the given graph.
+		@rtype:  list
+		@return: List of cut-nodes.
+		"""
+		return accessibility.cut_nodes(self)
+# Hypergraph class ---------------------------------------------------------------------------------
+class hypergraph (object):
+	"""
+	Hypergraph class.
+	Hypergraphs are a generalization of graphs where an edge (called hyperedge) can connect more
+	than two nodes.
+	@sort: __init__, __len__, __str__, add_hyperedge, add_hyperedges, add_node,	add_nodes, has_node,
+	hyperedges, link, links, nodes, unlink, read, write, accessibility,	connected_components,
+	cut_hyperedges, cut_nodes
+	"""
+	def __init__(self):
+		"""
+		Initialize a hypergraph.
+		"""
+		self.node_links = {}	# Pairing: Node -> Hyperedge
+		self.edge_links = {} 	# Pairing: Hyperedge -> Node
+		self.graph = graph()	# Ordinary graph
+	def __str__(self):
+		"""
+		Return a string representing the hypergraph when requested by str() (or print).
+		@rtype:  string
+		@return: String representing the hypergraph.
+		"""
+		return "<hypergraph object " + str(self.nodes()) + " " + str(self.edge_links) + ">"
+	def __len__(self):
+		"""
+		Return the size of the hypergraph when requested by len().
+		@rtype:  number
+		@return: Size of the hypergraph.
+		"""
+		return len(self.node_links)
+	def read(self, string, fmt='xml'):
+		"""
+		Read a hypergraph from a string. Nodes and hyperedges specified in the input will be added
+		to the current graph.
+		@type  string: string
+		@param string: Input string specifying a graph.
+		@type  fmt: string
+		@param fmt: Input format. Possible formats are:
+			1. 'xml' - XML (default)
+		"""
+		if (fmt == 'xml'):
+			readwrite.read_xml_hypergraph(self, string)
+	def write(self, fmt='xml'):
+		"""
+		Write the hypergraph to a string. Depending of the output format, this string can be used by
+		read() to rebuild the graph.
+		@type  fmt: string
+		@param fmt: Output format. Possible formats are:
+			1. 'xml' - XML (default)
+			2. 'dot' - DOT Language (for GraphViz)
+			3. 'dotclr' - DOT Language, coloured
+		@rtype:  string
+		@return: String specifying the graph.
+		"""
+		if (fmt == 'xml'):
+			return readwrite.write_xml_hypergraph(self)
+		elif (fmt == 'dot'):
+			return readwrite.write_dot_hypergraph(self)
+		elif (fmt == 'dotclr'):
+			return readwrite.write_dot_hypergraph(self, coloured=True)
+	def nodes(self):
+		"""
+		Return node list.
+		@rtype:  list
+		@return: Node list.
+		"""
+		return self.node_links.keys()
+	def hyperedges(self):
+		"""
+		Return hyperedge list.
+		@rtype:  list
+		@return: List of hyperedges linked to the given node.
+		"""
+		return self.edge_links.keys()
+	def links(self, obj):
+		"""
+		Return all objects linked to the given one.
+		If given a node, linked hyperedges will be returned. If given a hyperedge, linked nodes will
+		be returned.
+		@type  obj: node or hyperedge
+		@param obj: Object identifier.
+		@rtype:  list
+		@return: List of objects linked to the given one.
+		"""
+		if (obj in self.node_links):
+			return self.node_links[obj]
+		else:
+			return self.edge_links[obj]
+	def has_node(self, node):
+		"""
+		Return whether the requested node exists.
+		@type  node: node
+		@param node: Node identifier
+		@rtype:  boolean
+		@return: Truth-value for node existence.
+		"""
+		return self.node_links.has_key(node)
+	def add_node(self, node):
+		"""
+		Add given node to the hypergraph.
+		@attention: While nodes can be of any type, it's strongly recommended to use only numbers
+		and single-line strings as node identifiers if you intend to use write().
+		@type  node: node
+		@param node: Node identifier.
+		"""
+		if (not node in self.node_links):
+			self.node_links[node] = []
+			self.graph.add_node((node,'n'))
+	def add_nodes(self, nodelist):
+		"""
+		Add given nodes to the hypergraph.
+		@attention: While nodes can be of any type, it's strongly recommended to use only numbers
+		and single-line strings as node identifiers if you intend to use write().
+		@type  nodelist: list
+		@param nodelist: List of nodes to be added to the graph.
+		"""
+		for each in nodelist:
+			self.add_node(each)
+	def add_hyperedge(self, hyperedge):
+		"""
+		Add given hyperedge to the hypergraph.
+		@attention: While hyperedge-nodes can be of any type, it's strongly recommended to use only
+		numbers and single-line strings as node identifiers if you intend to use write().
+		@type  hyperedge: hyperedge
+		@param hyperedge: Hyperedge identifier.
+		"""
+		if (not hyperedge in self.edge_links):
+			self.edge_links[hyperedge] = []
+			self.graph.add_node((hyperedge,'h'))
+	def add_hyperedges(self, edgelist):
+		"""
+		Add given hyperedges to the hypergraph.
+		@attention: While hyperedge-nodes can be of any type, it's strongly recommended to use only
+		numbers and single-line strings as node identifiers if you intend to use write().
+		@type  edgelist: list
+		@param edgelist: List of hyperedge-nodes to be added to the graph.
+		"""
+		for each in edgelist:
+			self.add_hyperedge(each)
+	def link(self, node, hyperedge):
+		"""
+		Link given node and hyperedge.
+		@type  node: node
+		@param node: Node.
+		@type  hyperedge: node
+		@param hyperedge: Hyperedge.
+		"""
+		if (hyperedge not in self.node_links[node]):
+			self.node_links[node].append(hyperedge)
+			self.edge_links[hyperedge].append(node)
+			self.graph.add_edge((node,'n'), (hyperedge,'h'))
+	def unlink(self, node, hyperedge):
+		"""
+		Unlink given node and hyperedge.
+		@type  node: node
+		@param node: Node.
+		@type  hyperedge: hyperedge
+		@param hyperedge: Hyperedge.
+		"""
+		self.node_links[node].remove(hyperedge)
+		self.edge_links[hyperedge].remove(node)
+	def accessibility(self):
+		"""
+		Accessibility matrix (transitive closure).
+		@rtype:  dictionary
+		@return: Accessibility information for each node.
+		"""
+		access_ = accessibility.accessibility(self.graph)
+		access = {}
+		for each in access_.keys():
+			if (each[1] == 'n'):
+				access[each[0]] = []
+				for other in access_[each]:
+					if (other[1] == 'n'):
+						access[each[0]].append(other[0])
+		return access
+	def connected_components(self):
+		"""
+		Connected components.
+		@rtype:  dictionary
+		@return: Pairing that associates each node to its connected component.
+		"""
+		components_ = accessibility.connected_components(self.graph)
+		components = {}
+		for each in components_.keys():
+			if (each[1] == 'n'):
+				components[each[0]] = components_[each]
+		return components
+	def cut_nodes(self):
+		"""
+		Return the cut-nodes of the given hypergraph.
+		@rtype:  list
+		@return: List of cut-nodes.
+		"""
+		cut_nodes_ = accessibility.cut_nodes(self.graph)
+		cut_nodes = []
+		for each in cut_nodes_:
+			if (each[1] == 'n'):
+				cut_nodes.append(each[0])
+		return cut_nodes
+	def cut_hyperedges(self):
+		"""
+		Return the cut-hyperedges of the given hypergraph.
+		@rtype:  list
+		@return: List of cut-nodes.
+		"""
+		cut_nodes_ = accessibility.cut_nodes(self.graph)
+		cut_nodes = []
+		for each in cut_nodes_:
+			if (each[1] == 'h'):
+				cut_nodes.append(each[0])
+		return cut_nodes
+	def rank(self):
+		"""
+		Return the rank of the given hypergraph.
+		@rtype:  int
+		@return: Rank of graph.
+		"""
+		max_rank = 0
+		for each in hyperedges:
+			if len(each) > max_rank:
+				max_rank = len(each)
+		return max_rank

changeset 599	32a30f609530
parent 594	06c2228e39cb