diff -r 01f8c7aabb7e -r 06c2228e39cb thirdparty/python-graph/graph/__init__.py --- /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 +# Christian Muise +# Nathan Davis +# Zsolt Haraszti +# +# 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 "" + + + 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 "" + + + 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 "" + + + 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