--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/thirdparty/python-graph/graph/__init__.py Wed Nov 26 23:56:19 2008 +0000
@@ -0,0 +1,1573 @@
+# 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