# HG changeset patch # User Sverre Rabbelier # Date 1227743779 0 # Node ID 06c2228e39cbc66fbb890409419f07b0eac2021a # Parent 01f8c7aabb7ed46c77e3b4e77366c6a9e2bf8c86 Added the python-graph module http://code.google.com/p/python-graph/ Patch by: Sverre Rabbelier diff -r 01f8c7aabb7e -r 06c2228e39cb app/graph/__init__.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/app/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 diff -r 01f8c7aabb7e -r 06c2228e39cb app/graph/accessibility.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/app/graph/accessibility.py Wed Nov 26 23:56:19 2008 +0000 @@ -0,0 +1,228 @@ +# Copyright (c) 2007-2008 Pedro Matiello +# +# Permission is hereby granted, free of charge, to any person +# obtaining a copy of this software and associated documentation +# files (the "Software"), to deal in the Software without +# restriction, including without limitation the rights to use, +# copy, modify, merge, publish, distribute, sublicense, and/or sell +# copies of the Software, and to permit persons to whom the +# Software is furnished to do so, subject to the following +# conditions: + +# The above copyright notice and this permission notice shall be +# included in all copies or substantial portions of the Software. + +# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES +# OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND +# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT +# HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, +# WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR +# OTHER DEALINGS IN THE SOFTWARE. + + +""" +Accessibility algorithms for python-graph. + +@sort: accessibility, connected_components, cut_edges, cut_nodes, mutual_accessibility +""" + + +# Transitive-closure + +def accessibility(graph): + """ + Accessibility matrix (transitive closure). + + @type graph: graph + @param graph: Graph. + + @rtype: dictionary + @return: Accessibility information for each node. + """ + accessibility = {} # Accessibility matrix + + # For each node i, mark each node j if that exists a path from i to j. + for each in graph: + access = {} + # Perform DFS to explore all reachable nodes + _dfs(graph, access, 1, each) + accessibility[each] = access.keys() + return accessibility + + +# Strongly connected components + +def mutual_accessibility(graph): + """ + Mutual-accessibility matrix (strongly connected components). + + @type graph: graph + @param graph: Graph. + + @rtype: dictionary + @return: Mutual-accessibility information for each node. + """ + mutual_access = {} + access = graph.accessibility() + + for i in graph: + mutual_access[i] = [] + for j in graph: + if (i in access[j] and j in access[i]): + mutual_access[i].append(j) + + return mutual_access + + +# Connected components + +def connected_components(graph): + """ + Connected components. + + @attention: Indentification of connected components is meaningful only for non-directed graphs. + + @type graph: graph + @param graph: Graph. + + @rtype: dictionary + @return: Pairing that associates each node to its connected component. + """ + visited = {} + count = 1 + + # For 'each' node not found to belong to a connected component, find its connected component. + for each in graph: + if (each not in visited): + _dfs(graph, visited, count, each) + count = count + 1 + + return visited + + +# Limited DFS implementations used by algorithms here + +def _dfs(graph, visited, count, node): + """ + Depht-first search subfunction adapted for accessibility algorithms. + + @type graph: graph + @param graph: Graph. + + @type visited: dictionary + @param visited: List of nodes (visited nodes are marked non-zero). + + @type count: number + @param count: Counter of connected components. + + @type node: number + @param node: Node to be explored by DFS. + """ + visited[node] = count + # Explore recursively the connected component + for each in graph[node]: + if (each not in visited): + _dfs(graph, visited, count, each) + + +# Cut-Edge and Cut-Vertex identification + +def cut_edges(graph): + """ + Return the cut-edges of the given graph. + + @rtype: list + @return: List of cut-edges. + """ + pre = {} + low = {} + spanning_tree = {} + reply = [] + pre[None] = 0 + + for each in graph: + if (not pre.has_key(each)): + spanning_tree[each] = None + _cut_dfs(graph, spanning_tree, pre, low, reply, each) + return reply + + +def cut_nodes(graph): + """ + Return the cut-nodes of the given graph. + + @rtype: list + @return: List of cut-nodes. + """ + pre = {} # Pre-ordering + low = {} # Lowest pre[] reachable from this node going down the spanning tree + one backedge + reply = {} + spanning_tree = {} + pre[None] = 0 + + # Create spanning trees, calculate pre[], low[] + for each in graph: + if (not pre.has_key(each)): + spanning_tree[each] = None + _cut_dfs(graph, spanning_tree, pre, low, [], each) + + # Find cuts + for each in graph: + # If node is not a root + if (spanning_tree[each] is not None): + for other in graph[each]: + # If there is no back-edge from descendent to a ancestral of each + if (low[other] >= pre[each] and spanning_tree[other] == each): + reply[each] = 1 + # If node is a root + else: + children = 0 + for other in graph: + if (spanning_tree[other] == each): + children = children + 1 + # root is cut-vertex iff it has two or more children + if (children >= 2): + reply[each] = 1 + + return reply.keys() + + +def _cut_dfs(graph, spanning_tree, pre, low, reply, node): + """ + Depth first search adapted for identification of cut-edges and cut-nodes. + + @type graph: graph + @param graph: Graph + + @type spanning_tree: dictionary + @param spanning_tree: Spanning tree being built for the graph by DFS. + + @type pre: dictionary + @param pre: Graph's preordering. + + @type low: dictionary + @param low: Associates to each node, the preordering index of the node of lowest preordering + accessible from the given node. + + @type reply: list + @param reply: List of cut-edges. + + @type node: node + @param node: Node to be explored by DFS. + """ + pre[node] = pre[None] + low[node] = pre[None] + pre[None] = pre[None] + 1 + + for each in graph[node]: + if (not pre.has_key(each)): + spanning_tree[each] = node + _cut_dfs(graph, spanning_tree, pre, low, reply, each) + if (low[node] > low[each]): + low[node] = low[each] + if (low[each] == pre[each]): + reply.append((node, each)) + elif (low[node] > pre[each] and spanning_tree[node] != each): + low[node] = pre[each] diff -r 01f8c7aabb7e -r 06c2228e39cb app/graph/generators.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/app/graph/generators.py Wed Nov 26 23:56:19 2008 +0000 @@ -0,0 +1,82 @@ +# Copyright (c) 2007-2008 Pedro Matiello +# 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. + + +""" +Random graph generators for python-graph. + +@sort: generate +""" + + +# Imports +import graph as classes +from random import randint + + +# Generator + +def generate(graph, num_nodes, num_edges, weight_range=(1, 1)): + """ + Add nodes and random edges to the graph. + + @type graph: graph + @param graph: 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). + """ + # Discover if graph is directed or not + directed = (type(graph) == classes.digraph) + + # Nodes first + nodes = xrange(num_nodes) + graph.add_nodes(nodes) + + # Build a list of all possible edges + edges = [] + edges_append = edges.append + for x in nodes: + for y in nodes: + if ((directed and x != y) or (x > y)): + edges_append((x, y)) + + # Randomize the list + for i in xrange(len(edges)): + r = randint(0, len(edges)-1) + edges[i], edges[r] = edges[r], edges[i] + + # Add edges to the graph + min_wt = min(weight_range) + max_wt = max(weight_range) + for i in xrange(num_edges): + each = edges[i] + graph.add_edge(each[0], each[1], wt = randint(min_wt, max_wt)) diff -r 01f8c7aabb7e -r 06c2228e39cb app/graph/minmax.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/app/graph/minmax.py Wed Nov 26 23:56:19 2008 +0000 @@ -0,0 +1,168 @@ +# Copyright (c) 2007-2008 Pedro Matiello +# Rhys Ulerich +# +# 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. + + +""" +Minimization and maximization algorithms for python-graph. + +@sort: minimal_spanning_tree, shortest_path, _first_unvisited, _lightest_edge +""" + + +# Minimal spanning tree + +def minimal_spanning_tree(graph, root=None): + """ + Minimal spanning tree. + + @attention: Minimal spanning tree meaningful only for weighted graphs. + + @type graph: graph + @param graph: Graph. + + @type root: node + @param root: Optional root node (will explore only root's connected component) + + @rtype: dictionary + @return: Generated spanning tree. + """ + visited = [] # List for marking visited and non-visited nodes + spanning_tree = {} # MInimal Spanning tree + + # Initialization + if (root is not None): + visited.append(root) + nroot = root + spanning_tree[root] = None + else: + nroot = 1 + + # Algorithm loop + while (nroot is not None): + ledge = _lightest_edge(graph, visited) + if (ledge == (-1, -1)): + if (root is not None): + break + nroot = _first_unvisited(graph, visited) + if (nroot is not None): + spanning_tree[nroot] = None + visited.append(nroot) + else: + spanning_tree[ledge[1]] = ledge[0] + visited.append(ledge[1]) + + return spanning_tree + + +def _first_unvisited(graph, visited): + """ + Return first unvisited node. + + @type graph: graph + @param graph: Graph. + + @type visited: list + @param visited: List of nodes. + + @rtype: node + @return: First unvisited node. + """ + for each in graph: + if (each not in visited): + return each + return None + + +def _lightest_edge(graph, visited): + """ + Return the lightest edge in graph going from a visited node to an unvisited one. + + @type graph: graph + @param graph: Graph. + + @type visited: list + @param visited: List of nodes. + + @rtype: tuple + @return: Lightest edge in graph going from a visited node to an unvisited one. + """ + lightest_edge = (-1, -1) + weight = -1 + for each in visited: + for other in graph[each]: + if (other not in visited): + w = graph.get_edge_weight(each, other) + if (w < weight or weight < 0): + lightest_edge = (each, other) + weight = w + return lightest_edge + + +# Shortest Path +# Code donated by Rhys Ulerich + +def shortest_path(graph, source): + """ + Return the shortest path distance between source and all other nodes using Dijkstra's algorithm. + + @attention: All weights must be nonnegative. + + @type graph: graph + @param graph: Graph. + + @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. + """ + # Initialization + dist = { source: 0 } + previous = { source: None} + q = graph.nodes() + + # Algorithm loop + while q: + # examine_min process performed using O(nodes) pass here. + # May be improved using another examine_min data structure. + u = q[0] + for node in q[1:]: + if ((not dist.has_key(u)) + or (dist.has_key(node) and dist[node] < dist[u])): + u = node + q.remove(u) + + # Process reachable, remaining nodes from u + if (dist.has_key(u)): + for v in graph[u]: + if v in q: + alt = dist[u] + graph.get_edge_weight(u, v) + if (not dist.has_key(v)) or (alt < dist[v]): + dist[v] = alt + previous[v] = u + + return previous, dist diff -r 01f8c7aabb7e -r 06c2228e39cb app/graph/readwrite.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/app/graph/readwrite.py Wed Nov 26 23:56:19 2008 +0000 @@ -0,0 +1,302 @@ +# Copyright (c) 2007-2008 Pedro Matiello +# +# Permission is hereby granted, free of charge, to any person +# obtaining a copy of this software and associated documentation +# files (the "Software"), to deal in the Software without +# restriction, including without limitation the rights to use, +# copy, modify, merge, publish, distribute, sublicense, and/or sell +# copies of the Software, and to permit persons to whom the +# Software is furnished to do so, subject to the following +# conditions: + +# The above copyright notice and this permission notice shall be +# included in all copies or substantial portions of the Software. + +# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES +# OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND +# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT +# HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, +# WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR +# OTHER DEALINGS IN THE SOFTWARE. + + +""" +Functions for reading and writing graphs. + +@sort: read_xml, write_xml, write_dot_graph, write_dot_digraph, write_dot_hypergraph +""" + + +# Imports +from xml.dom.minidom import Document, parseString + + +# Values +colors = ['aquamarine4', 'blue4', 'brown4', 'cornflowerblue', 'cyan4', + 'darkgreen', 'darkorange3', 'darkorchid4', 'darkseagreen4', 'darkslategray', + 'deeppink4', 'deepskyblue4', 'firebrick3', 'hotpink3', 'indianred3', + 'indigo', 'lightblue4', 'lightseagreen', 'lightskyblue4', 'magenta4', + 'maroon', 'palevioletred3', 'steelblue', 'violetred3'] + + +# XML + +def write_xml(graph): + """ + Return a string specifying the given graph as a XML document. + + @type graph: graph + @param graph: Graph. + + @rtype: string + @return: String specifying the graph as a XML document. + """ + + # Document root + grxml = Document() + grxmlr = grxml.createElement('graph') + grxml.appendChild(grxmlr) + + # Each node... + for each_node in graph.nodes(): + node = grxml.createElement('node') + node.setAttribute('id',str(each_node)) + grxmlr.appendChild(node) + for each_attr in graph.get_node_attributes(each_node): + attr = grxml.createElement('attribute') + attr.setAttribute('attr', each_attr[0]) + attr.setAttribute('value', each_attr[1]) + node.appendChild(attr) + + # Each edge... + for edge_from, edge_to in graph.edges(): + edge = grxml.createElement('edge') + edge.setAttribute('from',str(edge_from)) + edge.setAttribute('to',str(edge_to)) + edge.setAttribute('wt',str(graph.get_edge_weight(edge_from, edge_to))) + edge.setAttribute('label',str(graph.get_edge_label(edge_from, edge_to))) + grxmlr.appendChild(edge) + for attr_name, attr_value in graph.get_edge_attributes(edge_from, edge_to): + attr = grxml.createElement('attribute') + attr.setAttribute('attr', attr_name) + attr.setAttribute('value', attr_value) + edge.appendChild(attr) + + return grxml.toprettyxml() + + +def write_xml_hypergraph(hypergraph): + """ + Return a string specifying the given hypergraph as a XML document. + + @type hypergraph: hypergraph + @param hypergraph: Hypergraph. + + @rtype: string + @return: String specifying the graph as a XML document. + """ + + # Document root + grxml = Document() + grxmlr = grxml.createElement('hypergraph') + grxml.appendChild(grxmlr) + + # Each node... + nodes = hypergraph.nodes() + hyperedges = hypergraph.get_hyperedges() + for each_node in (nodes + hyperedges): + if (each_node in nodes): + node = grxml.createElement('node') + else: + node = grxml.createElement('hyperedge') + node.setAttribute('id',str(each_node)) + grxmlr.appendChild(node) + + # and its outgoing edge + for each_edge in hypergraph.get_links(each_node): + edge = grxml.createElement('link') + edge.setAttribute('to',str(each_edge)) + node.appendChild(edge) + + return grxml.toprettyxml() + + +def read_xml(graph, string): + """ + Read a graph from a XML document. Nodes and edges specified in the input will be added to the current graph. + + @type graph: graph + @param graph: Graph + + @type string: string + @param string: Input string in XML format specifying a graph. + """ + dom = parseString(string) + + # Read nodes... + for each_node in dom.getElementsByTagName("node"): + graph.add_node(each_node.getAttribute('id')) + for each_attr in each_node.getElementsByTagName("attribute"): + graph.add_node_attribute(each_node.getAttribute('id'), (each_attr.getAttribute('attr'), + each_attr.getAttribute('value'))) + + # Read edges... + for each_edge in dom.getElementsByTagName("edge"): + graph.add_edge(each_edge.getAttribute('from'), each_edge.getAttribute('to'), \ + wt=float(each_edge.getAttribute('wt')), label=each_edge.getAttribute('label')) + for each_attr in each_edge.getElementsByTagName("attribute"): + attr_tuple = (each_attr.getAttribute('attr'), each_attr.getAttribute('value')) + if (attr_tuple not in graph.get_edge_attributes(each_edge.getAttribute('from'), \ + each_edge.getAttribute('to'))): + graph.add_edge_attribute(each_edge.getAttribute('from'), \ + each_edge.getAttribute('to'), attr_tuple) + + +def read_xml_hypergraph(hypergraph, string): + """ + Read a graph from a XML document. Nodes and hyperedges specified in the input will be added to the current graph. + + @type hypergraph: hypergraph + @param hypergraph: Hypergraph + + @type string: string + @param string: Input string in XML format specifying a graph. + """ + dom = parseString(string) + for each_node in dom.getElementsByTagName("node"): + hypergraph.add_nodes(each_node.getAttribute('id')) + for each_node in dom.getElementsByTagName("hyperedge"): + hypergraph.add_hyperedges(each_node.getAttribute('id')) + dom = parseString(string) + for each_node in dom.getElementsByTagName("node"): + for each_edge in each_node.getElementsByTagName("link"): + hypergraph.link(each_node.getAttribute('id'), each_edge.getAttribute('to')) + + +# DOT Language + +def _dot_node_str(graph, node, wt): + line = '\t"%s" [ ' % str(node) + attrlist = graph.get_node_attributes(node) + for each in attrlist: + attr = '%s="%s" ' % (each[0], each[1]) + line = line + attr + line = line + ']\n' + return line + + +def _dot_edge_str(graph, u, v, wt): + line = '\t"%s" -- "%s" [ ' % (str(u), str(v)) + attrlist = graph.get_edge_attributes(u, v) + [('label',graph.get_edge_label(u, v))] + for each in attrlist: + attr = '%s="%s" ' % (each[0], each[1]) + line = line + attr + line = line + ']\n' + return line + + +def _dot_arrow_str(graph, u, v, wt): + line = '\t"%s" -> "%s" [ ' % (str(u), str(v)) + attrlist = graph.get_edge_attributes(u, v) + [('label',graph.get_edge_label(u, v))] + for each in attrlist: + attr = '%s="%s" ' % (each[0], each[1]) + line = line + attr + line = line + ']\n' + return line + + +def write_dot_graph(graph, wt): + """ + Return a string specifying the given graph in DOT Language. + + @type graph: graph + @param graph: Graph. + + @type wt: boolean + @param wt: Whether edges should be labelled with its weight. + + @rtype: string + @return: String specifying the graph in DOT Language. + """ + doc = 'graph graphname \n{\n' + for node in graph: + doc = doc + _dot_node_str(graph, node, wt) + for edge in graph[node]: + if (node >= edge): + doc = doc + _dot_edge_str(graph, node, edge, wt) + doc = doc + '}' + return doc + + +def write_dot_digraph(graph, wt): + """ + Return a string specifying the given digraph in DOT Language. + + @type graph: graph + @param graph: Graph. + + @type wt: boolean + @param wt: Whether arrows should be labelled with its weight. + + @rtype: string + @return: String specifying the graph in DOT Language. + """ + doc = 'digraph graphname \n{\n' + for node in graph: + doc = doc + _dot_node_str(graph, node, wt) + for edge in graph[node]: + doc = doc + _dot_arrow_str(graph, node, edge, wt) + doc = doc + '}' + return doc + + +def write_dot_hypergraph(hypergraph, coloured=False): + """ + Return a string specifying the given hypergraph in DOT Language. + + @type hypergraph: hypergraph + @param hypergraph: Hypergraph. + + @type coloured: boolean + @param coloured: Whether hyperedges should be coloured. + + @rtype: string + @return: String specifying the hypergraph in DOT Language. + """ + # Start document + doc = "" + doc = doc + "graph graphname" + "\n{\n" + colortable = {} + colorcount = 0 + + + # Add hyperedges + color = '' + for each_hyperedge in hypergraph.hyperedges(): + colortable[each_hyperedge] = colors[colorcount % len(colors)] + colorcount = colorcount + 1 + if (coloured): + color = " color=%s" % colortable[each_hyperedge] + vars = { + 'hyperedge' : str(each_hyperedge), + 'color' : color + } + doc = doc + '\t"%(hyperedge)s" [shape=point %(color)s]\n' % vars + + color = "\n" + # Add nodes and links + for each_node in hypergraph.nodes(): + doc = doc + "\t\"%s\"\n" % str(each_node) + for each_link in hypergraph.links(each_node): + if (coloured): + color = " [color=%s]\n" % colortable[each_link] + linkvars = { + 'node' : str(each_node), + 'hyperedge' : str(each_link) + } + doc = doc + '\t %(node)s -- %(hyperedge)s' % linkvars + color + + doc = doc + "}" + return doc diff -r 01f8c7aabb7e -r 06c2228e39cb app/graph/searching.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/app/graph/searching.py Wed Nov 26 23:56:19 2008 +0000 @@ -0,0 +1,167 @@ +# Copyright (c) 2007-2008 Pedro Matiello +# +# Permission is hereby granted, free of charge, to any person +# obtaining a copy of this software and associated documentation +# files (the "Software"), to deal in the Software without +# restriction, including without limitation the rights to use, +# copy, modify, merge, publish, distribute, sublicense, and/or sell +# copies of the Software, and to permit persons to whom the +# Software is furnished to do so, subject to the following +# conditions: + +# The above copyright notice and this permission notice shall be +# included in all copies or substantial portions of the Software. + +# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES +# OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND +# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT +# HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, +# WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR +# OTHER DEALINGS IN THE SOFTWARE. + + +""" +Search algorithms for python-graph. + +@sort: breadth_first_search, depth_first_search, _bfs, _dfs +""" + + +# Depth-first search + +def depth_first_search(graph, root=None): + """ + Depth-first search. + + @type graph: graph + @param graph: Graph. + + @type root: node + @param root: Optional root node (will explore only root's connected component) + + @rtype: tuple + @return: A tupple containing a dictionary and two lists: + 1. Generated spanning tree + 2. Graph's preordering + 3. Graph's postordering + """ + visited = {} # List for marking visited and non-visited nodes + spanning_tree = {} # Spanning tree + pre = [] # Graph's preordering + post = [] # Graph's postordering + + # DFS from one node only + if (root is not None): + spanning_tree[root] = None + _dfs(graph, visited, spanning_tree, pre, post, root) + return spanning_tree, pre, post + + # Algorithm loop + for each in graph: + # Select a non-visited node + if (each not in visited): + spanning_tree[each] = None + # Explore node's connected component + _dfs(graph, visited, spanning_tree, pre, post, each) + + return spanning_tree, pre, post + + +def _dfs(graph, visited, spanning_tree, pre, post, node): + """ + Depht-first search subfunction. + + @type graph: graph + @param graph: Graph. + + @type visited: dictionary + @param visited: List of nodes (visited nodes are marked non-zero). + + @type spanning_tree: dictionary + @param spanning_tree: Spanning tree being built for the graph by DFS. + + @type pre: list + @param pre: Graph's preordering. + + @type post: list + @param post: Graph's postordering. + + @type node: node + @param node: Node to be explored by DFS. + """ + visited[node] = 1 + pre.append(node) + # Explore recursively the connected component + for each in graph[node]: + if (each not in visited): + spanning_tree[each] = node + _dfs(graph, visited, spanning_tree, pre, post, each) + post.append(node) + + +# Breadth-first search + +def breadth_first_search(graph, root=None): + """ + Breadth-first search. + + @type graph: graph + @param graph: Graph. + + @type root: node + @param root: Optional root node (will explore only root's connected component) + + @rtype: tuple + @return: A tuple containing a dictionary and a list. + 1. Generated spanning tree + 2. Graph's level-based ordering + """ + queue = [] # Visiting queue + spanning_tree = {} # Spanning tree + ordering = [] + + # BFS from one node only + if (root is not None): + queue.append(root) + ordering.append(root) + spanning_tree[root] = None + _bfs(graph, queue, spanning_tree, ordering) + return spanning_tree, ordering + + # Algorithm + for each in graph: + if (each not in spanning_tree): + queue.append(each) + ordering.append(root) + spanning_tree[each] = None + _bfs(graph, queue, spanning_tree, ordering) + + return spanning_tree, ordering[1:] + + +def _bfs(graph, queue, spanning_tree, ordering): + """ + Breadth-first search subfunction. + + @type graph: graph + @param graph: Graph. + + @type spanning_tree: dictionary + @param spanning_tree: Spanning tree being built for the graph by DFS. + + @type ordering: list + @param ordering: Graph's level-based ordering. + + @type queue: list + @param queue: Nodes to be visited (ordered). + """ + while (queue != []): + node = queue.pop(0) + + for other in graph[node]: + if (other not in spanning_tree): + queue.append(other) + ordering.append(other) + spanning_tree[other] = node diff -r 01f8c7aabb7e -r 06c2228e39cb app/graph/sorting.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/app/graph/sorting.py Wed Nov 26 23:56:19 2008 +0000 @@ -0,0 +1,49 @@ +# Copyright (c) 2007-2008 Pedro Matiello +# +# Permission is hereby granted, free of charge, to any person +# obtaining a copy of this software and associated documentation +# files (the "Software"), to deal in the Software without +# restriction, including without limitation the rights to use, +# copy, modify, merge, publish, distribute, sublicense, and/or sell +# copies of the Software, and to permit persons to whom the +# Software is furnished to do so, subject to the following +# conditions: + +# The above copyright notice and this permission notice shall be +# included in all copies or substantial portions of the Software. + +# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES +# OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND +# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT +# HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, +# WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR +# OTHER DEALINGS IN THE SOFTWARE. + + +""" +Sorting algorithms for python-graph. + +@sort: topological_sorting +""" + + +# Topological sorting + +def topological_sorting(graph): + """ + Topological sorting. + + @attention: Topological sorting is meaningful only for directed acyclic graphs. + + @type graph: graph + @param graph: Graph. + + @rtype: list + @return: Topological sorting for the graph. + """ + # The topological sorting of a DAG is equivalent to its reverse postordering. + tmp, tmp, post = graph.depth_first_search() + post.reverse() + return post diff -r 01f8c7aabb7e -r 06c2228e39cb app/graph/traversal.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/app/graph/traversal.py Wed Nov 26 23:56:19 2008 +0000 @@ -0,0 +1,81 @@ +# Copyright (c) 2007-2008 Pedro Matiello +# +# Permission is hereby granted, free of charge, to any person +# obtaining a copy of this software and associated documentation +# files (the "Software"), to deal in the Software without +# restriction, including without limitation the rights to use, +# copy, modify, merge, publish, distribute, sublicense, and/or sell +# copies of the Software, and to permit persons to whom the +# Software is furnished to do so, subject to the following +# conditions: + +# The above copyright notice and this permission notice shall be +# included in all copies or substantial portions of the Software. + +# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES +# OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND +# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT +# HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, +# WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR +# OTHER DEALINGS IN THE SOFTWARE. + + +""" +Traversal algorithms for python-graph. + +@sort: traversal +""" + + +# Minimal spanning tree + +def traversal(graph, node, order): + """ + 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. + """ + visited = {} + if (order == 'pre'): + pre = 1 + post = 0 + elif (order == 'post'): + pre = 0 + post = 1 + + for each in _dfs(graph, visited, node, pre, post): + yield each + + +def _dfs(graph, visited, node, pre, post): + """ + Depht-first search subfunction for traversals. + + @type graph: graph + @param graph: Graph. + + @type visited: dictionary + @param visited: List of nodes (visited nodes are marked non-zero). + + @type node: node + @param node: Node to be explored by DFS. + """ + visited[node] = 1 + if (pre): yield node + # Explore recursively the connected component + for each in graph[node]: + if (each not in visited): + for other in _dfs(graph, visited, each, pre, post): + yield other + if (post): yield node diff -r 01f8c7aabb7e -r 06c2228e39cb thirdparty/python-graph/COPYING --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/thirdparty/python-graph/COPYING Wed Nov 26 23:56:19 2008 +0000 @@ -0,0 +1,22 @@ +# Copyright (c) 2007 Pedro Matiello +# +# Permission is hereby granted, free of charge, to any person +# obtaining a copy of this software and associated documentation +# files (the "Software"), to deal in the Software without +# restriction, including without limitation the rights to use, +# copy, modify, merge, publish, distribute, sublicense, and/or sell +# copies of the Software, and to permit persons to whom the +# Software is furnished to do so, subject to the following +# conditions: + +# The above copyright notice and this permission notice shall be +# included in all copies or substantial portions of the Software. + +# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES +# OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND +# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT +# HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, +# WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR +# OTHER DEALINGS IN THE SOFTWARE. diff -r 01f8c7aabb7e -r 06c2228e39cb thirdparty/python-graph/Changelog --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/thirdparty/python-graph/Changelog Wed Nov 26 23:56:19 2008 +0000 @@ -0,0 +1,140 @@ +python-graph +A library for working with graphs in Python +-------------------------------------------------------------------------------- + +CHANGELOG + + +Release 1.3.1 [Out 27, 2008] + +Fixes: + Graph and digraph inverse was not working; + Node removal in digraphs was not deleting all relevant edges (Issue 13). + +Important API Changes: + Deprecated methods were removed. + + +Release 1.3.0 [Sep 28, 2008] + +Enhancements: + Tree traversals (preorder and postorder). + +Fixes: + Node insertion is much faster now (Issue 11). + Hypernode/hyperedge insertion also much faster. + +Important API Changes: + get_nodes() is now nodes(); + get_edges() is now edges(); + get_neighbors() is now neighbors(); + get_incidents() is now incidents(); + get_order() is now order(); + get_degree() is now degree(). + (Former method names are deprecated and will be removed in the next release.) + + +Release 1.2.0 [Sep 09, 2008] + +Enhancements: + Moved to new class style; + Graphs and digraphs are separated classes now; + Added level-based ordering to breadth first search; + Graph object is now iterable; + Graph object is now a container and graphobj[nodeid] iterates too; + Support for node and edge attributes (Issue 5); + Node deletion. + +Fixes: + Install now works with a prefix (Issue 10); + Shortest path spanning trees did not had an explicit root. + +Important API Changes: + breadth_first_search() now returns a tuple; + Arrow methods are gone. Use class digraph + edge methods for directed graphs now. + + +Release 1.1.1 [Sep 04, 2008] + +Enhancements: + Improved install script. + +Fixes: + DOT Language output now works for nodes/edges labelled with spaces. + +Important API Changes: + get_neighbours() is now get_neighbors() (Issue 9). + + +Release 1.1.0 [Aug 31, 2008] + +Enhancements: + Hypergraph support (Issue 4); + Complete and complement graph generation; + Weights in random generated graphs (Issue 8). + +Fixes: + Fixed bug in cut-node identification; + Fixed bug causing wrong results for graphs with nodes labelled with values that evaluate to False (Issue 7). + +Important API Changes: + get_edges() now return all edges in the graph; + get_neighbours() has the former behaviour of get_edges(). + + +Release 1.0.0 [Aug 01, 2008] + +Adds some operations; +Random graph generation; +Cut-vertex/cut-edge identification. + + +Release 0.85 [Jul 27, 2008] + +Adds DOT-Language output (Issue 1); +Install script included (Issue 3). + + +Release 0.75 [Jul 06, 2008] + +Added XML import/export; +Docs are bundled now. + + +Release 0.65 [Jun 25, 2008] + +DFS, BFS and MST can be generated for given roots; +Added Dijkstra's shortest path algorithm (Issue 2). + + +Release 0.50 [May 13, 2008] + +Some API changes; +Nodes can now be arbitrary names/objects. + + +Release 0.45 [May 12, 2008] + +Adds Prim's minimal spanning tree. + + +Release 0.40 [Mar 09, 2008] + +Adds topological sorting; +Support for weighted graphs. + + +Release 0.30 [Aug 30, 2007] + +Adds algorithms for accessibility and mutual accessibility. + +Release 0.20 [Jul 16, 2007] + +Adds breadth-first search; +API documentation. + + +Release 0.10 [Jul 10, 2007] + +First release; +Feat. basic operations and depth-first searching. diff -r 01f8c7aabb7e -r 06c2228e39cb thirdparty/python-graph/MANIFEST --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/thirdparty/python-graph/MANIFEST Wed Nov 26 23:56:19 2008 +0000 @@ -0,0 +1,34 @@ +README +COPYING +Changelog +setup.py +graph/__init__.py +graph/accessibility.py +graph/generators.py +graph/minmax.py +graph/readwrite.py +graph/searching.py +graph/sorting.py +graph/traversal.py +docs/api-objects.txt +docs/class-tree.html +docs/crarr.png +docs/epydoc.css +docs/epydoc.js +docs/graph.accessibility-module.html +docs/graph.digraph-class.html +docs/graph.generators-module.html +docs/graph.graph-class.html +docs/graph.hypergraph-class.html +docs/graph.minmax-module.html +docs/graph-module.html +docs/graph.readwrite-module.html +docs/graph.searching-module.html +docs/graph.sorting-module.html +docs/graph.transversal-module.html +docs/graph.traversal-module.html +docs/help.html +docs/identifier-index.html +docs/index.html +docs/module-tree.html +docs/redirect.html diff -r 01f8c7aabb7e -r 06c2228e39cb thirdparty/python-graph/Makefile --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/thirdparty/python-graph/Makefile Wed Nov 26 23:56:19 2008 +0000 @@ -0,0 +1,17 @@ +none: + +install: + ./setup.py install + +docs: graph/*.py + epydoc -v --no-frames --no-sourcecode --name="python-graph" --url="http://code.google.com/p/python-graph/" --no-private --html --css misc/epydoc.css -o docs graph/*.py + +edit: graph/*.py + gedit graph/__init__.py & + gedit graph/*.py & + +clean: + rm -rf docs + rm -rf dist + rm -rf build + rm graph/*.pyc diff -r 01f8c7aabb7e -r 06c2228e39cb thirdparty/python-graph/README --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/thirdparty/python-graph/README Wed Nov 26 23:56:19 2008 +0000 @@ -0,0 +1,48 @@ +python-graph +A library for working with graphs in Python +-------------------------------------------------------------------------------- + + +AUTHORS + +Pedro Matiello + + +CONTRIBUTORS + +Christian Muise + * Various Hypergraph algorithms. + +Nathan Davis + * Faster node insertion. + +Rhys Ulerich + * Dijkstra's Shortest path algorithm. + +Zsolt Haraszti + * Weighted random generated graphs. + + +LICENSE + +This software is provided under the MIT license. See accompanying COPYING file for details. + + +DOCUMENTATION + +To generate the API documentation for this package, run: + + make docs + +You'll need epydoc installed in your system. + + +WEBSITE + +The latest version of this package can be found at: + + http://code.google.com/p/python-graph/ + +Please report bugs at: + + http://code.google.com/p/python-graph/issues/list diff -r 01f8c7aabb7e -r 06c2228e39cb thirdparty/python-graph/docs/api-objects.txt --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/thirdparty/python-graph/docs/api-objects.txt Wed Nov 26 23:56:19 2008 +0000 @@ -0,0 +1,144 @@ +graph graph-module.html +graph.accessibility graph.accessibility-module.html +graph.accessibility.connected_components graph.accessibility-module.html#connected_components +graph.accessibility.mutual_accessibility graph.accessibility-module.html#mutual_accessibility +graph.accessibility.accessibility graph.accessibility-module.html#accessibility +graph.accessibility._dfs graph.accessibility-module.html#_dfs +graph.accessibility._cut_dfs graph.accessibility-module.html#_cut_dfs +graph.accessibility.cut_edges graph.accessibility-module.html#cut_edges +graph.accessibility.cut_nodes graph.accessibility-module.html#cut_nodes +graph.generators graph.generators-module.html +graph.generators.generate graph.generators-module.html#generate +graph.minmax graph.minmax-module.html +graph.minmax._first_unvisited graph.minmax-module.html#_first_unvisited +graph.minmax.minimal_spanning_tree graph.minmax-module.html#minimal_spanning_tree +graph.minmax.shortest_path graph.minmax-module.html#shortest_path +graph.minmax._lightest_edge graph.minmax-module.html#_lightest_edge +graph.readwrite graph.readwrite-module.html +graph.readwrite.read_xml_hypergraph graph.readwrite-module.html#read_xml_hypergraph +graph.readwrite._dot_edge_str graph.readwrite-module.html#_dot_edge_str +graph.readwrite.write_dot_graph graph.readwrite-module.html#write_dot_graph +graph.readwrite.read_xml graph.readwrite-module.html#read_xml +graph.readwrite.write_xml graph.readwrite-module.html#write_xml +graph.readwrite.write_dot_hypergraph graph.readwrite-module.html#write_dot_hypergraph +graph.readwrite._dot_node_str graph.readwrite-module.html#_dot_node_str +graph.readwrite.colors graph.readwrite-module.html#colors +graph.readwrite.write_dot_digraph graph.readwrite-module.html#write_dot_digraph +graph.readwrite._dot_arrow_str graph.readwrite-module.html#_dot_arrow_str +graph.readwrite.write_xml_hypergraph graph.readwrite-module.html#write_xml_hypergraph +graph.searching graph.searching-module.html +graph.searching._dfs graph.searching-module.html#_dfs +graph.searching.breadth_first_search graph.searching-module.html#breadth_first_search +graph.searching.depth_first_search graph.searching-module.html#depth_first_search +graph.searching._bfs graph.searching-module.html#_bfs +graph.sorting graph.sorting-module.html +graph.sorting.topological_sorting graph.sorting-module.html#topological_sorting +graph.traversal graph.traversal-module.html +graph.traversal._dfs graph.traversal-module.html#_dfs +graph.traversal.traversal graph.traversal-module.html#traversal +graph.digraph graph.digraph-class.html +graph.digraph.neighbors graph.digraph-class.html#neighbors +graph.digraph.shortest_path graph.digraph-class.html#shortest_path +graph.digraph.get_node_attributes graph.digraph-class.html#get_node_attributes +graph.digraph.add_node graph.digraph-class.html#add_node +graph.digraph.__str__ graph.digraph-class.html#__str__ +graph.digraph.has_edge graph.digraph-class.html#has_edge +graph.digraph.accessibility graph.digraph-class.html#accessibility +graph.digraph.depth_first_search graph.digraph-class.html#depth_first_search +graph.digraph.del_node graph.digraph-class.html#del_node +graph.digraph.get_edge_attributes graph.digraph-class.html#get_edge_attributes +graph.digraph.__init__ graph.digraph-class.html#__init__ +graph.digraph.inverse graph.digraph-class.html#inverse +graph.digraph.degree graph.digraph-class.html#degree +graph.digraph.topological_sorting graph.digraph-class.html#topological_sorting +graph.digraph.breadth_first_search graph.digraph-class.html#breadth_first_search +graph.digraph.set_edge_label graph.digraph-class.html#set_edge_label +graph.digraph.write graph.digraph-class.html#write +graph.digraph.get_edge_weight graph.digraph-class.html#get_edge_weight +graph.digraph.nodes graph.digraph-class.html#nodes +graph.digraph.__len__ graph.digraph-class.html#__len__ +graph.digraph.complete graph.digraph-class.html#complete +graph.digraph.__getitem__ graph.digraph-class.html#__getitem__ +graph.digraph.has_node graph.digraph-class.html#has_node +graph.digraph.read graph.digraph-class.html#read +graph.digraph.get_edge_label graph.digraph-class.html#get_edge_label +graph.digraph.traversal graph.digraph-class.html#traversal +graph.digraph.add_spanning_tree graph.digraph-class.html#add_spanning_tree +graph.digraph.__iter__ graph.digraph-class.html#__iter__ +graph.digraph.edges graph.digraph-class.html#edges +graph.digraph.add_edge_attribute graph.digraph-class.html#add_edge_attribute +graph.digraph.add_edge graph.digraph-class.html#add_edge +graph.digraph.minimal_spanning_tree graph.digraph-class.html#minimal_spanning_tree +graph.digraph.generate graph.digraph-class.html#generate +graph.digraph.cut_edges graph.digraph-class.html#cut_edges +graph.digraph.mutual_accessibility graph.digraph-class.html#mutual_accessibility +graph.digraph.add_graph graph.digraph-class.html#add_graph +graph.digraph.add_node_attribute graph.digraph-class.html#add_node_attribute +graph.digraph.incidents graph.digraph-class.html#incidents +graph.digraph.set_edge_weight graph.digraph-class.html#set_edge_weight +graph.digraph.add_nodes graph.digraph-class.html#add_nodes +graph.digraph.cut_nodes graph.digraph-class.html#cut_nodes +graph.digraph.order graph.digraph-class.html#order +graph.digraph.del_edge graph.digraph-class.html#del_edge +graph.graph graph.graph-class.html +graph.graph.neighbors graph.graph-class.html#neighbors +graph.graph.connected_components graph.graph-class.html#connected_components +graph.graph.shortest_path graph.graph-class.html#shortest_path +graph.graph.get_node_attributes graph.graph-class.html#get_node_attributes +graph.graph.add_node graph.graph-class.html#add_node +graph.graph.__str__ graph.graph-class.html#__str__ +graph.graph.has_edge graph.graph-class.html#has_edge +graph.graph.accessibility graph.graph-class.html#accessibility +graph.graph.depth_first_search graph.graph-class.html#depth_first_search +graph.graph.del_node graph.graph-class.html#del_node +graph.graph.get_edge_attributes graph.graph-class.html#get_edge_attributes +graph.graph.__init__ graph.graph-class.html#__init__ +graph.graph.inverse graph.graph-class.html#inverse +graph.graph.breadth_first_search graph.graph-class.html#breadth_first_search +graph.graph.set_edge_label graph.graph-class.html#set_edge_label +graph.graph.write graph.graph-class.html#write +graph.graph.nodes graph.graph-class.html#nodes +graph.graph.__len__ graph.graph-class.html#__len__ +graph.graph.complete graph.graph-class.html#complete +graph.graph.__getitem__ graph.graph-class.html#__getitem__ +graph.graph.has_node graph.graph-class.html#has_node +graph.graph.read graph.graph-class.html#read +graph.graph.get_edge_label graph.graph-class.html#get_edge_label +graph.graph.traversal graph.graph-class.html#traversal +graph.graph.add_spanning_tree graph.graph-class.html#add_spanning_tree +graph.graph.__iter__ graph.graph-class.html#__iter__ +graph.graph.edges graph.graph-class.html#edges +graph.graph.add_edge_attribute graph.graph-class.html#add_edge_attribute +graph.graph.add_edge graph.graph-class.html#add_edge +graph.graph.minimal_spanning_tree graph.graph-class.html#minimal_spanning_tree +graph.graph.generate graph.graph-class.html#generate +graph.graph.cut_edges graph.graph-class.html#cut_edges +graph.graph.add_graph graph.graph-class.html#add_graph +graph.graph.add_node_attribute graph.graph-class.html#add_node_attribute +graph.graph.get_edge_weight graph.graph-class.html#get_edge_weight +graph.graph.set_edge_weight graph.graph-class.html#set_edge_weight +graph.graph.add_nodes graph.graph-class.html#add_nodes +graph.graph.cut_nodes graph.graph-class.html#cut_nodes +graph.graph.order graph.graph-class.html#order +graph.graph.del_edge graph.graph-class.html#del_edge +graph.hypergraph graph.hypergraph-class.html +graph.hypergraph.connected_components graph.hypergraph-class.html#connected_components +graph.hypergraph.cut_hyperedges graph.hypergraph-class.html#cut_hyperedges +graph.hypergraph.links graph.hypergraph-class.html#links +graph.hypergraph.add_node graph.hypergraph-class.html#add_node +graph.hypergraph.__str__ graph.hypergraph-class.html#__str__ +graph.hypergraph.accessibility graph.hypergraph-class.html#accessibility +graph.hypergraph.rank graph.hypergraph-class.html#rank +graph.hypergraph.__init__ graph.hypergraph-class.html#__init__ +graph.hypergraph.add_hyperedge graph.hypergraph-class.html#add_hyperedge +graph.hypergraph.write graph.hypergraph-class.html#write +graph.hypergraph.nodes graph.hypergraph-class.html#nodes +graph.hypergraph.__len__ graph.hypergraph-class.html#__len__ +graph.hypergraph.has_node graph.hypergraph-class.html#has_node +graph.hypergraph.read graph.hypergraph-class.html#read +graph.hypergraph.add_hyperedges graph.hypergraph-class.html#add_hyperedges +graph.hypergraph.link graph.hypergraph-class.html#link +graph.hypergraph.unlink graph.hypergraph-class.html#unlink +graph.hypergraph.hyperedges graph.hypergraph-class.html#hyperedges +graph.hypergraph.add_nodes graph.hypergraph-class.html#add_nodes +graph.hypergraph.cut_nodes graph.hypergraph-class.html#cut_nodes diff -r 01f8c7aabb7e -r 06c2228e39cb thirdparty/python-graph/docs/class-tree.html --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/thirdparty/python-graph/docs/class-tree.html Wed Nov 26 23:56:19 2008 +0000 @@ -0,0 +1,122 @@ + + + + + Class Hierarchy + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
  + + +
+
+
+ [ Module Hierarchy + | Class Hierarchy ] +

+

Class Hierarchy

+ + + + + + + + + + + + + + + + + + + + + + + + + +
+ + + + diff -r 01f8c7aabb7e -r 06c2228e39cb thirdparty/python-graph/docs/crarr.png Binary file thirdparty/python-graph/docs/crarr.png has changed diff -r 01f8c7aabb7e -r 06c2228e39cb thirdparty/python-graph/docs/epydoc.css --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/thirdparty/python-graph/docs/epydoc.css Wed Nov 26 23:56:19 2008 +0000 @@ -0,0 +1,322 @@ + + +/* Epydoc CSS Stylesheet + * + * This stylesheet can be used to customize the appearance of epydoc's + * HTML output. + * + */ + +/* Default Colors & Styles + * - Set the default foreground & background color with 'body'; and + * link colors with 'a:link' and 'a:visited'. + * - Use bold for decision list terms. + * - The heading styles defined here are used for headings *within* + * docstring descriptions. All headings used by epydoc itself use + * either class='epydoc' or class='toc' (CSS styles for both + * defined below). + */ +body { background: #ffffff; color: #000000; } +p { margin-top: 0.5em; margin-bottom: 0.5em; } +a:link { color: #0000ff; } +a:visited { color: #204080; } +dt { font-weight: bold; } +h1 { font-size: +140%; font-style: italic; + font-weight: bold; } +h2 { font-size: +125%; font-style: italic; + font-weight: bold; } +h3 { font-size: +110%; + font-weight: normal; } +code { font-size: 100%; } +/* N.B.: class, not pseudoclass */ +a.link { font-family: monospace; } + +/* Page Header & Footer + * - The standard page header consists of a navigation bar (with + * pointers to standard pages such as 'home' and 'trees'); a + * breadcrumbs list, which can be used to navigate to containing + * classes or modules; options links, to show/hide private + * variables and to show/hide frames; and a page title (using + *

). The page title may be followed by a link to the + * corresponding source code (using 'span.codelink'). + * - The footer consists of a navigation bar, a timestamp, and a + * pointer to epydoc's homepage. + */ +h1.epydoc { margin: 0; font-size: +140%; font-weight: bold; } +h2.epydoc { font-size: +130%; font-weight: bold; } +h3.epydoc { font-size: +115%; font-weight: bold; + margin-top: 0.2em; } +td h3.epydoc { font-size: +115%; font-weight: bold; + margin-bottom: 0; } +table.navbar { background: #a0c0ff; color: #000000; + border: 2px groove #c0d0d0; } +table.navbar table { color: #000000; } +th.navbar-select { background: #70b0ff; + color: #000000; } +table.navbar a { text-decoration: none; } +table.navbar a:link { color: #0000ff; } +table.navbar a:visited { color: #204080; } +span.breadcrumbs { font-size: 85%; font-weight: bold; } +span.options { font-size: 70%; } +span.codelink { font-size: 85%; } +td.footer { font-size: 85%; } + +/* Table Headers + * - Each summary table and details section begins with a 'header' + * row. This row contains a section title (marked by + * 'span.table-header') as well as a show/hide private link + * (marked by 'span.options', defined above). + * - Summary tables that contain user-defined groups mark those + * groups using 'group header' rows. + */ +td.table-header { background: #70b0ff; color: #000000; + border: 1px solid #608090; } +td.table-header table { color: #000000; } +td.table-header table a:link { color: #0000ff; } +td.table-header table a:visited { color: #204080; } +span.table-header { font-size: 120%; font-weight: bold; } +th.group-header { background: #c0e0f8; color: #000000; + text-align: left; font-style: italic; + font-size: 115%; + border: 1px solid #608090; } + +/* Summary Tables (functions, variables, etc) + * - Each object is described by a single row of the table with + * two cells. The left cell gives the object's type, and is + * marked with 'code.summary-type'. The right cell gives the + * object's name and a summary description. + * - CSS styles for the table's header and group headers are + * defined above, under 'Table Headers' + */ +table.summary { border-collapse: collapse; + background: #e8f0f8; color: #000000; + border: 1px solid #608090; + margin-bottom: 0.5em; } +td.summary { border: 1px solid #608090; } +code.summary-type { font-size: 85%; } +table.summary a:link { color: #0000ff; } +table.summary a:visited { color: #204080; } + + +/* Details Tables (functions, variables, etc) + * - Each object is described in its own div. + * - A single-row summary table w/ table-header is used as + * a header for each details section (CSS style for table-header + * is defined above, under 'Table Headers'). + */ +table.details { border-collapse: collapse; + background: #e8f0f8; color: #000000; + border: 1px solid #608090; + margin: .2em 0 0 0; } +table.details table { color: #000000; } +table.details a:link { color: #0000ff; } +table.details a:visited { color: #204080; } + +/* Fields */ +dl.fields { margin-left: 2em; margin-top: 1em; + margin-bottom: 1em; } +dl.fields dd ul { margin-left: 0em; padding-left: 0em; } +dl.fields dd ul li ul { margin-left: 2em; padding-left: 0em; } +div.fields { margin-left: 2em; } +div.fields p { margin-bottom: 0.5em; } + +/* Index tables (identifier index, term index, etc) + * - link-index is used for indices containing lists of links + * (namely, the identifier index & term index). + * - index-where is used in link indices for the text indicating + * the container/source for each link. + * - metadata-index is used for indices containing metadata + * extracted from fields (namely, the bug index & todo index). + */ +table.link-index { border-collapse: collapse; + background: #e8f0f8; color: #000000; + border: 1px solid #608090; } +td.link-index { border-width: 0px; } +table.link-index a:link { color: #0000ff; } +table.link-index a:visited { color: #204080; } +span.index-where { font-size: 70%; } +table.metadata-index { border-collapse: collapse; + background: #e8f0f8; color: #000000; + border: 1px solid #608090; + margin: .2em 0 0 0; } +td.metadata-index { border-width: 1px; border-style: solid; } +table.metadata-index a:link { color: #0000ff; } +table.metadata-index a:visited { color: #204080; } + +/* Function signatures + * - sig* is used for the signature in the details section. + * - .summary-sig* is used for the signature in the summary + * table, and when listing property accessor functions. + * */ +.sig-name { color: #006080; } +.sig-arg { color: #008060; } +.sig-default { color: #602000; } +.summary-sig { font-family: monospace; } +.summary-sig-name { color: #006080; font-weight: bold; } +table.summary a.summary-sig-name:link + { color: #006080; font-weight: bold; } +table.summary a.summary-sig-name:visited + { color: #006080; font-weight: bold; } +.summary-sig-arg { color: #006040; } +.summary-sig-default { color: #501800; } + +/* Subclass list + */ +ul.subclass-list { display: inline; } +ul.subclass-list li { display: inline; } + +/* To render variables, classes etc. like functions */ +table.summary .summary-name { color: #006080; font-weight: bold; + font-family: monospace; } +table.summary + a.summary-name:link { color: #006080; font-weight: bold; + font-family: monospace; } +table.summary + a.summary-name:visited { color: #006080; font-weight: bold; + font-family: monospace; } + +/* Variable values + * - In the 'variable details' sections, each varaible's value is + * listed in a 'pre.variable' box. The width of this box is + * restricted to 80 chars; if the value's repr is longer than + * this it will be wrapped, using a backslash marked with + * class 'variable-linewrap'. If the value's repr is longer + * than 3 lines, the rest will be ellided; and an ellipsis + * marker ('...' marked with 'variable-ellipsis') will be used. + * - If the value is a string, its quote marks will be marked + * with 'variable-quote'. + * - If the variable is a regexp, it is syntax-highlighted using + * the re* CSS classes. + */ +pre.variable { padding: .5em; margin: 0; + background: #dce4ec; color: #000000; + border: 1px solid #708890; } +.variable-linewrap { color: #604000; font-weight: bold; } +.variable-ellipsis { color: #604000; font-weight: bold; } +.variable-quote { color: #604000; font-weight: bold; } +.variable-group { color: #008000; font-weight: bold; } +.variable-op { color: #604000; font-weight: bold; } +.variable-string { color: #006030; } +.variable-unknown { color: #a00000; font-weight: bold; } +.re { color: #000000; } +.re-char { color: #006030; } +.re-op { color: #600000; } +.re-group { color: #003060; } +.re-ref { color: #404040; } + +/* Base tree + * - Used by class pages to display the base class hierarchy. + */ +pre.base-tree { font-size: 80%; margin: 0; } + +/* Frames-based table of contents headers + * - Consists of two frames: one for selecting modules; and + * the other listing the contents of the selected module. + * - h1.toc is used for each frame's heading + * - h2.toc is used for subheadings within each frame. + */ +h1.toc { text-align: center; font-size: 105%; + margin: 0; font-weight: bold; + padding: 0; } +h2.toc { font-size: 100%; font-weight: bold; + margin: 0.5em 0 0 -0.3em; } + +/* Syntax Highlighting for Source Code + * - doctest examples are displayed in a 'pre.py-doctest' block. + * If the example is in a details table entry, then it will use + * the colors specified by the 'table pre.py-doctest' line. + * - Source code listings are displayed in a 'pre.py-src' block. + * Each line is marked with 'span.py-line' (used to draw a line + * down the left margin, separating the code from the line + * numbers). Line numbers are displayed with 'span.py-lineno'. + * The expand/collapse block toggle button is displayed with + * 'a.py-toggle' (Note: the CSS style for 'a.py-toggle' should not + * modify the font size of the text.) + * - If a source code page is opened with an anchor, then the + * corresponding code block will be highlighted. The code + * block's header is highlighted with 'py-highlight-hdr'; and + * the code block's body is highlighted with 'py-highlight'. + * - The remaining py-* classes are used to perform syntax + * highlighting (py-string for string literals, py-name for names, + * etc.) + */ +pre.py-doctest { padding: .5em; margin: 1em; + background: #e8f0f8; color: #000000; + border: 1px solid #708890; } +table pre.py-doctest { background: #dce4ec; + color: #000000; } +pre.py-src { border: 2px solid #000000; + background: #f0f0f0; color: #000000; } +.py-line { border-left: 2px solid #000000; + margin-left: .2em; padding-left: .4em; } +.py-lineno { font-style: italic; font-size: 90%; + padding-left: .5em; } +a.py-toggle { text-decoration: none; } +div.py-highlight-hdr { border-top: 2px solid #000000; + border-bottom: 2px solid #000000; + background: #d8e8e8; } +div.py-highlight { border-bottom: 2px solid #000000; + background: #d0e0e0; } +.py-prompt { color: #005050; font-weight: bold;} +.py-more { color: #005050; font-weight: bold;} +.py-string { color: #006030; } +.py-comment { color: #003060; } +.py-keyword { color: #600000; } +.py-output { color: #404040; } +.py-name { color: #000050; } +.py-name:link { color: #000050 !important; } +.py-name:visited { color: #000050 !important; } +.py-number { color: #005000; } +.py-defname { color: #000060; font-weight: bold; } +.py-def-name { color: #000060; font-weight: bold; } +.py-base-class { color: #000060; } +.py-param { color: #000060; } +.py-docstring { color: #006030; } +.py-decorator { color: #804020; } +/* Use this if you don't want links to names underlined: */ +/*a.py-name { text-decoration: none; }*/ + +/* Graphs & Diagrams + * - These CSS styles are used for graphs & diagrams generated using + * Graphviz dot. 'img.graph-without-title' is used for bare + * diagrams (to remove the border created by making the image + * clickable). + */ +img.graph-without-title { border: none; } +img.graph-with-title { border: 1px solid #000000; } +span.graph-title { font-weight: bold; } +span.graph-caption { } + +/* General-purpose classes + * - 'p.indent-wrapped-lines' defines a paragraph whose first line + * is not indented, but whose subsequent lines are. + * - The 'nomargin-top' class is used to remove the top margin (e.g. + * from lists). The 'nomargin' class is used to remove both the + * top and bottom margin (but not the left or right margin -- + * for lists, that would cause the bullets to disappear.) + */ +p.indent-wrapped-lines { padding: 0 0 0 7em; text-indent: -7em; + margin: 0; } +.nomargin-top { margin-top: 0; } +.nomargin { margin-top: 0; margin-bottom: 0; } + +/* HTML Log */ +div.log-block { padding: 0; margin: .5em 0 .5em 0; + background: #e8f0f8; color: #000000; + border: 1px solid #000000; } +div.log-error { padding: .1em .3em .1em .3em; margin: 4px; + background: #ffb0b0; color: #000000; + border: 1px solid #000000; } +div.log-warning { padding: .1em .3em .1em .3em; margin: 4px; + background: #ffffb0; color: #000000; + border: 1px solid #000000; } +div.log-info { padding: .1em .3em .1em .3em; margin: 4px; + background: #b0ffb0; color: #000000; + border: 1px solid #000000; } +h2.log-hdr { background: #70b0ff; color: #000000; + margin: 0; padding: 0em 0.5em 0em 0.5em; + border-bottom: 1px solid #000000; font-size: 110%; } +p.log { font-weight: bold; margin: .5em 0 .5em 0; } +tr.opt-changed { color: #000000; font-weight: bold; } +tr.opt-default { color: #606060; } +pre.log { margin: 0; padding: 0; padding-left: 1em; } diff -r 01f8c7aabb7e -r 06c2228e39cb thirdparty/python-graph/docs/epydoc.js --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/thirdparty/python-graph/docs/epydoc.js Wed Nov 26 23:56:19 2008 +0000 @@ -0,0 +1,293 @@ +function toggle_private() { + // Search for any private/public links on this page. Store + // their old text in "cmd," so we will know what action to + // take; and change their text to the opposite action. + var cmd = "?"; + var elts = document.getElementsByTagName("a"); + for(var i=0; i...
"; + elt.innerHTML = s; + } +} + +function toggle(id) { + elt = document.getElementById(id+"-toggle"); + if (elt.innerHTML == "-") + collapse(id); + else + expand(id); + return false; +} + +function highlight(id) { + var elt = document.getElementById(id+"-def"); + if (elt) elt.className = "py-highlight-hdr"; + var elt = document.getElementById(id+"-expanded"); + if (elt) elt.className = "py-highlight"; + var elt = document.getElementById(id+"-collapsed"); + if (elt) elt.className = "py-highlight"; +} + +function num_lines(s) { + var n = 1; + var pos = s.indexOf("\n"); + while ( pos > 0) { + n += 1; + pos = s.indexOf("\n", pos+1); + } + return n; +} + +// Collapse all blocks that mave more than `min_lines` lines. +function collapse_all(min_lines) { + var elts = document.getElementsByTagName("div"); + for (var i=0; i 0) + if (elt.id.substring(split, elt.id.length) == "-expanded") + if (num_lines(elt.innerHTML) > min_lines) + collapse(elt.id.substring(0, split)); + } +} + +function expandto(href) { + var start = href.indexOf("#")+1; + if (start != 0 && start != href.length) { + if (href.substring(start, href.length) != "-") { + collapse_all(4); + pos = href.indexOf(".", start); + while (pos != -1) { + var id = href.substring(start, pos); + expand(id); + pos = href.indexOf(".", pos+1); + } + var id = href.substring(start, href.length); + expand(id); + highlight(id); + } + } +} + +function kill_doclink(id) { + var parent = document.getElementById(id); + parent.removeChild(parent.childNodes.item(0)); +} +function auto_kill_doclink(ev) { + if (!ev) var ev = window.event; + if (!this.contains(ev.toElement)) { + var parent = document.getElementById(this.parentID); + parent.removeChild(parent.childNodes.item(0)); + } +} + +function doclink(id, name, targets_id) { + var elt = document.getElementById(id); + + // If we already opened the box, then destroy it. + // (This case should never occur, but leave it in just in case.) + if (elt.childNodes.length > 1) { + elt.removeChild(elt.childNodes.item(0)); + } + else { + // The outer box: relative + inline positioning. + var box1 = document.createElement("div"); + box1.style.position = "relative"; + box1.style.display = "inline"; + box1.style.top = 0; + box1.style.left = 0; + + // A shadow for fun + var shadow = document.createElement("div"); + shadow.style.position = "absolute"; + shadow.style.left = "-1.3em"; + shadow.style.top = "-1.3em"; + shadow.style.background = "#404040"; + + // The inner box: absolute positioning. + var box2 = document.createElement("div"); + box2.style.position = "relative"; + box2.style.border = "1px solid #a0a0a0"; + box2.style.left = "-.2em"; + box2.style.top = "-.2em"; + box2.style.background = "white"; + box2.style.padding = ".3em .4em .3em .4em"; + box2.style.fontStyle = "normal"; + box2.onmouseout=auto_kill_doclink; + box2.parentID = id; + + // Get the targets + var targets_elt = document.getElementById(targets_id); + var targets = targets_elt.getAttribute("targets"); + var links = ""; + target_list = targets.split(","); + for (var i=0; i" + + target[0] + ""; + } + + // Put it all together. + elt.insertBefore(box1, elt.childNodes.item(0)); + //box1.appendChild(box2); + box1.appendChild(shadow); + shadow.appendChild(box2); + box2.innerHTML = + "Which "+name+" do you want to see documentation for?" + + ""; + } + return false; +} + +function get_anchor() { + var href = location.href; + var start = href.indexOf("#")+1; + if ((start != 0) && (start != href.length)) + return href.substring(start, href.length); + } +function redirect_url(dottedName) { + // Scan through each element of the "pages" list, and check + // if "name" matches with any of them. + for (var i=0; i-m" or "-c"; + // extract the portion & compare it to dottedName. + var pagename = pages[i].substring(0, pages[i].length-2); + if (pagename == dottedName.substring(0,pagename.length)) { + + // We've found a page that matches `dottedName`; + // construct its URL, using leftover `dottedName` + // content to form an anchor. + var pagetype = pages[i].charAt(pages[i].length-1); + var url = pagename + ((pagetype=="m")?"-module.html": + "-class.html"); + if (dottedName.length > pagename.length) + url += "#" + dottedName.substring(pagename.length+1, + dottedName.length); + return url; + } + } + } diff -r 01f8c7aabb7e -r 06c2228e39cb thirdparty/python-graph/docs/graph-module.html --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/thirdparty/python-graph/docs/graph-module.html Wed Nov 26 23:56:19 2008 +0000 @@ -0,0 +1,168 @@ + + + + + graph + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
+ + Package graph + + + + +
+
+ +

Package graph

+

python-graph

+

A library for working with graphs in Python.

+ +
+

Version: + 1.3.1 +

+
+ + + + + + +
+ Submodules
+
+ +
+ + + + + + + + + + + + + + + +
+ Classes
+   + + graph
+ Graph class. +
+   + + digraph
+ Digraph class. +
+   + + hypergraph
+ Hypergraph class. +
+ + + + + + + + + + + + + + + + + + + + + + + + +
+ + + + diff -r 01f8c7aabb7e -r 06c2228e39cb thirdparty/python-graph/docs/graph.accessibility-module.html --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/thirdparty/python-graph/docs/graph.accessibility-module.html Wed Nov 26 23:56:19 2008 +0000 @@ -0,0 +1,335 @@ + + + + + graph.accessibility + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
+ + Package graph :: + Module accessibility + + + + +
+
+ +

Module accessibility

+

Accessibility algorithms for python-graph.

+ + + + + + + + + + + + + + + + + + + + + + +
+ Functions
+ dictionary + + + + + + +
accessibility(graph)
+ Accessibility matrix (transitive closure).
+ + +
+ +
+ dictionary + + + + + + +
connected_components(graph)
+ Connected components.
+ + +
+ +
+ list + + + + + + +
cut_edges(graph)
+ Return the cut-edges of the given graph.
+ + +
+ +
+ list + + + + + + +
cut_nodes(graph)
+ Return the cut-nodes of the given graph.
+ + +
+ +
+ dictionary + + + + + + +
mutual_accessibility(graph)
+ Mutual-accessibility matrix (strongly connected components).
+ + +
+ +
+ + + + + + +
+ Function Details
+ +
+ +
+ + +
+

accessibility(graph) +

+
  +
+ +

Accessibility matrix (transitive closure).

+
+
Parameters:
+
    +
  • graph (graph) - Graph.
  • +
+
Returns: dictionary
+
Accessibility information for each node.
+
+
+
+ +
+ +
+ + +
+

connected_components(graph) +

+
  +
+ +

Connected components.

+
+
Parameters:
+
    +
  • graph (graph) - Graph.
  • +
+
Returns: dictionary
+
Pairing that associates each node to its connected component.
+
+

Attention: + Indentification of connected components is meaningful only for + non-directed graphs. +

+
+
+ +
+ +
+ + +
+

cut_edges(graph) +

+
  +
+ +

Return the cut-edges of the given graph.

+
+
Returns: list
+
List of cut-edges.
+
+
+
+ +
+ +
+ + +
+

cut_nodes(graph) +

+
  +
+ +

Return the cut-nodes of the given graph.

+
+
Returns: list
+
List of cut-nodes.
+
+
+
+ +
+ +
+ + +
+

mutual_accessibility(graph) +

+
  +
+ +

Mutual-accessibility matrix (strongly connected components).

+
+
Parameters:
+
    +
  • graph (graph) - Graph.
  • +
+
Returns: dictionary
+
Mutual-accessibility information for each node.
+
+
+
+
+ + + + + + + + + + + + + + + + + + + + + + + + +
+ + + + diff -r 01f8c7aabb7e -r 06c2228e39cb thirdparty/python-graph/docs/graph.digraph-class.html --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/thirdparty/python-graph/docs/graph.digraph-class.html Wed Nov 26 23:56:19 2008 +0000 @@ -0,0 +1,2103 @@ + + + + + graph.digraph + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
+ + Package graph :: + Class digraph + + + + +
+
+ +

Class digraph

+
+object --+
+         |
+        digraph
+
+ +
+

Digraph class.

+

Digraphs are built of nodes and directed edges.

+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
+ Instance Methods
+   + + + + + + +
__init__(self)
+ Initialize a digraph.
+ + +
+ +
+ iterator + + + + + + +
__getitem__(self, + node)
+ Return a iterator passing through all neighbors of the given node.
+ + +
+ +
+ iterator + + + + + + +
__iter__(self)
+ Return a iterator passing through all nodes in the digraph.
+ + +
+ +
+ number + + + + + + +
__len__(self)
+ Return the order of the digraph when requested by len().
+ + +
+ +
+ string + + + + + + +
__str__(self)
+ Return a string representing the digraph when requested by str() (or + print).
+ + +
+ +
+   + + + + + + +
add_edge(self, + u, + v, + wt=1, + label='', + attrs=[])
+ Add an directed edge (u,v) to the graph connecting nodes u to v.
+ + +
+ +
+   + + + + + + +
add_edge_attribute(self, + u, + v, + attr)
+ Add attribute to the given edge.
+ + +
+ +
+   + + + + + + +
add_graph(self, + graph)
+ Add other graph to the graph.
+ + +
+ +
+   + + + + + + +
add_node(self, + node, + attrs=[])
+ Add given node to the graph.
+ + +
+ +
+   + + + + + + +
add_node_attribute(self, + node, + attr)
+ Add attribute to the given node.
+ + +
+ +
+   + + + + + + +
add_nodes(self, + nodelist)
+ Add given nodes to the graph.
+ + +
+ +
+   + + + + + + +
add_spanning_tree(self, + st)
+ Add a spanning tree to the graph.
+ + +
+ +
+   + + + + + + +
complete(self)
+ Make the graph a complete graph.
+ + +
+ +
+ number + + + + + + +
degree(self, + node)
+ Return the degree of the given node.
+ + +
+ +
+   + + + + + + +
del_edge(self, + u, + v)
+ Remove an directed edge (u, v) from the graph.
+ + +
+ +
+   + + + + + + +
del_node(self, + node)
+ Remove a node from the graph.
+ + +
+ +
+ list + + + + + + +
edges(self)
+ Return all edges in the graph.
+ + +
+ +
+ list + + + + + + +
get_edge_attributes(self, + u, + v)
+ Return the attributes of the given edge.
+ + +
+ +
+ string + + + + + + +
get_edge_label(self, + u, + v)
+ Get the label of an edge.
+ + +
+ +
+ number + + + + + + +
get_edge_weight(self, + u, + v)
+ Get the weight of an edge.
+ + +
+ +
+ list + + + + + + +
get_node_attributes(self, + node)
+ Return the attributes of the given node.
+ + +
+ +
+ boolean + + + + + + +
has_edge(self, + u, + v)
+ Return whether an edge between nodes u and v exists.
+ + +
+ +
+ boolean + + + + + + +
has_node(self, + node)
+ Return whether the requested node exists.
+ + +
+ +
+ list + + + + + + +
incidents(self, + node)
+ Return all nodes that are incident to the given node.
+ + +
+ +
+ graph + + + + + + +
inverse(self)
+ Return the inverse of the graph.
+ + +
+ +
+ list + + + + + + +
neighbors(self, + node)
+ Return all nodes that are directly accessible from given node.
+ + +
+ +
+ list + + + + + + +
nodes(self)
+ Return node list.
+ + +
+ +
+ number + + + + + + +
order(self, + node)
+ Return the order of the given node.
+ + +
+ +
+   + + + + + + +
set_edge_label(self, + u, + v, + label)
+ Set the label of an edge.
+ + +
+ +
+   + + + + + + +
set_edge_weight(self, + u, + v, + wt)
+ Set the weight of an edge.
+ + +
+ +
+ iterator + + + + + + +
traversal(self, + node, + order='pre')
+ Graph traversal iterator.
+ + +
+ +
+   + + + + + + +
generate(self, + num_nodes, + num_edges, + weight_range=(1, 1))
+ Add nodes and random edges to the graph.
+ + +
+ +
+   + + + + + + +
read(self, + string, + fmt='xml')
+ Read a graph from a string.
+ + +
+ +
+ string + + + + + + +
write(self, + fmt='xml')
+ Write the graph to a string.
+ + +
+ +
+ dictionary + + + + + + +
accessibility(self)
+ Accessibility matrix (transitive closure).
+ + +
+ +
+ dictionary + + + + + + +
breadth_first_search(self, + root=None)
+ Breadth-first search.
+ + +
+ +
+ list + + + + + + +
cut_edges(self)
+ Return the cut-edges of the given graph.
+ + +
+ +
+ list + + + + + + +
cut_nodes(self)
+ Return the cut-nodes of the given graph.
+ + +
+ +
+ tuple + + + + + + +
depth_first_search(self, + root=None)
+ Depht-first search.
+ + +
+ +
+ list + + + + + + +
minimal_spanning_tree(self, + root=None)
+ Minimal spanning tree.
+ + +
+ +
+ list + + + + + + +
mutual_accessibility(self)
+ Mutual-accessibility matrix (strongly connected components).
+ + +
+ +
+ tuple + + + + + + +
shortest_path(self, + source)
+ Return the shortest path distance between source node and all other + nodes using Dijkstra's algorithm.
+ + +
+ +
+ list + + + + + + +
topological_sorting(self)
+ Topological sorting.
+ + +
+ +
+

Inherited from object: + __delattr__, + __getattribute__, + __hash__, + __new__, + __reduce__, + __reduce_ex__, + __repr__, + __setattr__ +

+
+ + + + + + + + + +
+ Properties
+

Inherited from object: + __class__ +

+
+ + + + + + +
+ Method Details
+ +
+ +
+ + +
+

__init__(self) +
(Constructor) +

+
  +
+ +

Initialize a digraph.

+
+
Overrides: + object.__init__ +
+
+
+
+ +
+ +
+ + +
+

__getitem__(self, + node) +
(Indexing operator) +

+
  +
+ +

Return a iterator passing through all neighbors of the given node.

+
+
Returns: iterator
+
Iterator passing through all neighbors of the given node.
+
+
+
+ +
+ +
+ + +
+

__iter__(self) +

+
  +
+ +

Return a iterator passing through all nodes in the digraph.

+
+
Returns: iterator
+
Iterator passing through all nodes in the digraph.
+
+
+
+ +
+ +
+ + +
+

__len__(self) +
(Length operator) +

+
  +
+ +

Return the order of the digraph when requested by len().

+
+
Returns: number
+
Size of the graph.
+
+
+
+ +
+ +
+ + +
+

__str__(self) +
(Informal representation operator) +

+
  +
+ +

Return a string representing the digraph when requested by str() (or + print).

+
+
Returns: string
+
String representing the graph.
+
Overrides: + object.__str__ +
+
+
+
+ +
+ +
+ + +
+

add_edge(self, + u, + v, + wt=1, + label='', + attrs=[]) +

+
  +
+ +

Add an directed edge (u,v) to the graph connecting nodes u to v.

+
+
Parameters:
+
    +
  • u (node) - One node.
  • +
  • v (node) - Other node.
  • +
  • wt (number) - Edge weight.
  • +
  • label (string) - Edge label.
  • +
  • attrs (list) - List of node attributes specified as (attribute, value) tuples.
  • +
+
+
+
+ +
+ +
+ + +
+

add_edge_attribute(self, + u, + v, + attr) +

+
  +
+ +

Add attribute to the given edge.

+
+
Parameters:
+
    +
  • u (node) - One node.
  • +
  • v (node) - Other node.
  • +
  • attr (tuple) - Node attribute specified as a tuple in the form (attribute, + value).
  • +
+
+
+
+ +
+ +
+ + +
+

add_graph(self, + graph) +

+
  +
+ +

Add other graph to the graph.

+
+
Parameters:
+
    +
  • graph (graph) - Graph
  • +
+
+

Attention: + Attributes and labels are not preserved. +

+
+
+ +
+ +
+ + +
+

add_node(self, + node, + attrs=[]) +

+
  +
+ +

Add given node to the graph.

+
+
Parameters:
+
    +
  • node (node) - Node identifier.
  • +
  • attrs (list) - List of node attributes specified as (attribute, value) tuples.
  • +
+
+

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(). +

+
+
+ +
+ +
+ + +
+

add_node_attribute(self, + node, + attr) +

+
  +
+ +

Add attribute to the given node.

+
+
Parameters:
+
    +
  • node (node) - Node identifier
  • +
  • attr (tuple) - Node attribute specified as a tuple in the form (attribute, + value).
  • +
+
+
+
+ +
+ +
+ + +
+

add_nodes(self, + nodelist) +

+
  +
+ +

Add given nodes to the graph.

+
+
Parameters:
+
    +
  • nodelist (list) - List of nodes to be added 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(). +

+
+
+ +
+ +
+ + +
+

add_spanning_tree(self, + st) +

+
  +
+ +

Add a spanning tree to the graph.

+
+
Parameters:
+
    +
  • st (dictionary) - Spanning tree.
  • +
+
+
+
+ +
+ +
+ + +
+

complete(self) +

+
  +
+ +

Make the graph a complete graph.

+
+
+

Attention: + This will modify the current graph. +

+
+
+ +
+ +
+ + +
+

degree(self, + node) +

+
  +
+ +

Return the degree of the given node.

+
+
Returns: number
+
Order of the given node.
+
+
+
+ +
+ +
+ + +
+

del_edge(self, + u, + v) +

+
  +
+ +

Remove an directed edge (u, v) from the graph.

+
+
Parameters:
+
    +
  • u (node) - One node.
  • +
  • v (node) - Other node.
  • +
+
+
+
+ +
+ +
+ + +
+

del_node(self, + node) +

+
  +
+ +

Remove a node from the graph.

+
+
Parameters:
+
    +
  • node (node) - Node identifier.
  • +
+
+
+
+ +
+ +
+ + +
+

edges(self) +

+
  +
+ +

Return all edges in the graph.

+
+
Returns: list
+
List of all edges in the graph.
+
+
+
+ +
+ +
+ + +
+

get_edge_attributes(self, + u, + v) +

+
  +
+ +

Return the attributes of the given edge.

+
+
Parameters:
+
    +
  • u (node) - One node.
  • +
  • v (node) - Other node.
  • +
+
Returns: list
+
List of attributes specified tuples in the form (attribute, + value).
+
+
+
+ +
+ +
+ + +
+

get_edge_label(self, + u, + v) +

+
  +
+ +

Get the label of an edge.

+
+
Parameters:
+
    +
  • u (node) - One node.
  • +
  • v (node) - Other node.
  • +
+
Returns: string
+
Edge label
+
+
+
+ +
+ +
+ + +
+

get_edge_weight(self, + u, + v) +

+
  +
+ +

Get the weight of an edge.

+
+
Parameters:
+
    +
  • u (node) - One node.
  • +
  • v (node) - Other node.
  • +
+
Returns: number
+
Edge weight.
+
+
+
+ +
+ +
+ + +
+

get_node_attributes(self, + node) +

+
  +
+ +

Return the attributes of the given node.

+
+
Parameters:
+
    +
  • node (node) - Node identifier
  • +
+
Returns: list
+
List of attributes specified tuples in the form (attribute, + value).
+
+
+
+ +
+ +
+ + +
+

has_edge(self, + u, + v) +

+
  +
+ +

Return whether an edge between nodes u and v exists.

+
+
Parameters:
+
    +
  • u (node) - One node.
  • +
  • v (node) - Other node.
  • +
+
Returns: boolean
+
Truth-value for edge existence.
+
+
+
+ +
+ +
+ + +
+

has_node(self, + node) +

+
  +
+ +

Return whether the requested node exists.

+
+
Parameters:
+
    +
  • node (node) - Node identifier
  • +
+
Returns: boolean
+
Truth-value for node existence.
+
+
+
+ +
+ +
+ + +
+

incidents(self, + node) +

+
  +
+ +

Return all nodes that are incident to the given node.

+
+
Parameters:
+
    +
  • node (node) - Node identifier
  • +
+
Returns: list
+
List of nodes directly accessible from given node.
+
+
+
+ +
+ +
+ + +
+

inverse(self) +

+
  +
+ +

Return the inverse of the graph.

+
+
Returns: graph
+
Complement graph for the graph.
+
+
+
+ +
+ +
+ + +
+

neighbors(self, + node) +

+
  +
+ +

Return all nodes that are directly accessible from given node.

+
+
Parameters:
+
    +
  • node (node) - Node identifier
  • +
+
Returns: list
+
List of nodes directly accessible from given node.
+
+
+
+ +
+ +
+ + +
+

nodes(self) +

+
  +
+ +

Return node list.

+
+
Returns: list
+
Node list.
+
+
+
+ +
+ +
+ + +
+

order(self, + node) +

+
  +
+ +

Return the order of the given node.

+
+
Returns: number
+
Order of the given node.
+
+
+
+ +
+ +
+ + +
+

set_edge_label(self, + u, + v, + label) +

+
  +
+ +

Set the label of an edge.

+
+
Parameters:
+
    +
  • u (node) - One node.
  • +
  • v (node) - Other node.
  • +
  • label (string) - Edge label.
  • +
+
+
+
+ +
+ +
+ + +
+

set_edge_weight(self, + u, + v, + wt) +

+
  +
+ +

Set the weight of an edge.

+
+
Parameters:
+
    +
  • u (node) - One node.
  • +
  • v (node) - Other node.
  • +
  • wt (number) - Edge weight.
  • +
+
+
+
+ +
+ +
+ + +
+

traversal(self, + node, + order='pre') +

+
  +
+ +

Graph traversal iterator.

+
+
Parameters:
+
    +
  • node (node) - Node.
  • +
  • order (string) - traversal ordering. Possible values are: +
      +
    1. + 'pre' - Preordering (default) +
    2. +
    +
      +
    1. + 'post' - Postordering +
    2. +
  • +
+
Returns: iterator
+
Traversal iterator.
+
+
+
+ +
+ +
+ + +
+

generate(self, + num_nodes, + num_edges, + weight_range=(1, 1)) +

+
  +
+ +

Add nodes and random edges to the graph.

+
+
Parameters:
+
    +
  • num_nodes (number) - Number of nodes.
  • +
  • num_edges (number) - Number of edges.
  • +
  • weight_range (tuple) - tuple of two integers as lower and upper limits on randomly + generated weights (uniform distribution).
  • +
+
+
+
+ +
+ +
+ + +
+

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.

+
+
Parameters:
+
    +
  • string (string) - Input string specifying a graph.
  • +
  • fmt (string) - Input format. Possible formats are: +
      +
    1. + 'xml' - XML (default) +
    2. +
  • +
+
+
+
+ +
+ +
+ + +
+

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.

+
+
Parameters:
+
    +
  • fmt (string) - Output format. Possible formats are: +
      +
    1. + 'xml' - XML (default) +
    2. +
    3. + 'dot' - DOT Language (for GraphViz) +
    4. +
    5. + 'dotwt' - DOT Language with weight information +
    6. +
  • +
+
Returns: string
+
String specifying the graph.
+
+
+
+ +
+ +
+ + +
+

accessibility(self) +

+
  +
+ +

Accessibility matrix (transitive closure).

+
+
Returns: dictionary
+
Accessibility information for each node.
+
+
+
+ +
+ +
+ + +
+

breadth_first_search(self, + root=None) +

+
  +
+ +

Breadth-first search.

+
+
Parameters:
+
    +
  • root (node) - Optional root node (will explore only root's connected component)
  • +
+
Returns: dictionary
+
A tuple containing a dictionary and a list. +
    +
  1. + Generated spanning tree +
  2. +
  3. + Graph's level-based ordering +
  4. +
+
+
+
+ +
+ +
+ + +
+

cut_edges(self) +

+
  +
+ +

Return the cut-edges of the given graph.

+
+
Returns: list
+
List of cut-edges.
+
+
+
+ +
+ +
+ + +
+

cut_nodes(self) +

+
  +
+ +

Return the cut-nodes of the given graph.

+
+
Returns: list
+
List of cut-nodes.
+
+
+
+ +
+ +
+ + +
+

depth_first_search(self, + root=None) +

+
  +
+ +

Depht-first search.

+
+
Parameters:
+
    +
  • root (node) - Optional root node (will explore only root's connected component)
  • +
+
Returns: tuple
+
tupple containing a dictionary and two lists: +
    +
  1. + Generated spanning tree +
  2. +
  3. + Graph's preordering +
  4. +
  5. + Graph's postordering +
  6. +
+
+
+
+ +
+ +
+ + +
+

minimal_spanning_tree(self, + root=None) +

+
  +
+ +

Minimal spanning tree.

+
+
Parameters:
+
    +
  • root (node) - Optional root node (will explore only root's connected component)
  • +
+
Returns: list
+
Generated spanning tree.
+
+

Attention: + Minimal spanning tree meaningful only for weighted graphs. +

+
+
+ +
+ +
+ + +
+

mutual_accessibility(self) +

+
  +
+ +

Mutual-accessibility matrix (strongly connected components).

+
+
Returns: list
+
Mutual-accessibility information for each node.
+
+
+
+ +
+ +
+ + +
+

shortest_path(self, + source) +

+
  +
+ +

Return the shortest path distance between source node and all other + nodes using Dijkstra's algorithm.

+
+
Parameters:
+
    +
  • source (node) - Node from which to start the search.
  • +
+
Returns: tuple
+
A tuple containing two dictionaries, each keyed by target nodes. +
    +
  1. + Shortest path spanning tree +
  2. +
  3. + Shortest distance from given source to each target node +
  4. +
+

Inaccessible target nodes do not appear in either + dictionary.

+
+

Attention: + All weights must be nonnegative. +

+
+
+ +
+ +
+ + +
+

topological_sorting(self) +

+
  +
+ +

Topological sorting.

+
+
Returns: list
+
Topological sorting for the graph.
+
+

Attention: + Topological sorting is meaningful only for directed acyclic graphs. +

+
+
+
+ + + + + + + + + + + + + + + + + + + + + + + + +
+ + + + diff -r 01f8c7aabb7e -r 06c2228e39cb thirdparty/python-graph/docs/graph.generators-module.html --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/thirdparty/python-graph/docs/graph.generators-module.html Wed Nov 26 23:56:19 2008 +0000 @@ -0,0 +1,179 @@ + + + + + graph.generators + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
+ + Package graph :: + Module generators + + + + +
+
+ +

Module generators

+

Random graph generators for python-graph.

+ + + + + + + + + + +
+ Functions
+   + + + + + + +
generate(graph, + num_nodes, + num_edges, + weight_range=(1, 1))
+ Add nodes and random edges to the graph.
+ + +
+ +
+ + + + + + +
+ Function Details
+ +
+ +
+ + +
+

generate(graph, + num_nodes, + num_edges, + weight_range=(1, 1)) +

+
  +
+ +

Add nodes and random edges to the graph.

+
+
Parameters:
+
    +
  • graph (graph) - Graph.
  • +
  • num_nodes (number) - Number of nodes.
  • +
  • num_edges (number) - Number of edges.
  • +
  • weight_range (tuple) - tuple of two integers as lower and upper limits on randomly + generated weights (uniform distribution).
  • +
+
+
+
+
+ + + + + + + + + + + + + + + + + + + + + + + + +
+ + + + diff -r 01f8c7aabb7e -r 06c2228e39cb thirdparty/python-graph/docs/graph.graph-class.html --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/thirdparty/python-graph/docs/graph.graph-class.html Wed Nov 26 23:56:19 2008 +0000 @@ -0,0 +1,1982 @@ + + + + + graph.graph + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
+ + Package graph :: + Class graph + + + + +
+
+ +

Class graph

+
+object --+
+         |
+        graph
+
+ +
+

Graph class.

+

Graphs are built of nodes and edges.

+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
+ Instance Methods
+   + + + + + + +
__init__(self)
+ Initialize a graph.
+ + +
+ +
+ iterator + + + + + + +
__getitem__(self, + node)
+ Return a iterator passing through all neighbors of the given node.
+ + +
+ +
+ iterator + + + + + + +
__iter__(self)
+ Return a iterator passing through all nodes in the graph.
+ + +
+ +
+ number + + + + + + +
__len__(self)
+ Return the order of the graph when requested by len().
+ + +
+ +
+ string + + + + + + +
__str__(self)
+ Return a string representing the graph when requested by str() (or + print).
+ + +
+ +
+   + + + + + + +
add_edge(self, + u, + v, + wt=1, + label='', + attrs=[])
+ Add an edge (u,v) to the graph connecting nodes u and v.
+ + +
+ +
+   + + + + + + +
add_edge_attribute(self, + u, + v, + attr)
+ Add attribute to the given edge.
+ + +
+ +
+   + + + + + + +
add_graph(self, + graph)
+ Add other graph to the graph.
+ + +
+ +
+   + + + + + + +
add_node(self, + node, + attrs=[])
+ Add given node to the graph.
+ + +
+ +
+   + + + + + + +
add_node_attribute(self, + node, + attr)
+ Add attribute to the given node.
+ + +
+ +
+   + + + + + + +
add_nodes(self, + nodelist)
+ Add given nodes to the graph.
+ + +
+ +
+   + + + + + + +
add_spanning_tree(self, + st)
+ Add a spanning tree to the graph.
+ + +
+ +
+   + + + + + + +
complete(self)
+ Make the graph a complete graph.
+ + +
+ +
+   + + + + + + +
del_edge(self, + u, + v)
+ Remove an edge (u, v) from the graph.
+ + +
+ +
+   + + + + + + +
del_node(self, + node)
+ Remove a node from the graph.
+ + +
+ +
+ list + + + + + + +
edges(self)
+ Return all edges in the graph.
+ + +
+ +
+ list + + + + + + +
get_edge_attributes(self, + u, + v)
+ Return the attributes of the given edge.
+ + +
+ +
+ string + + + + + + +
get_edge_label(self, + u, + v)
+ Get the label of an edge.
+ + +
+ +
+ number + + + + + + +
get_edge_weight(self, + u, + v)
+ Get the weight of an edge.
+ + +
+ +
+ list + + + + + + +
get_node_attributes(self, + node)
+ Return the attributes of the given node.
+ + +
+ +
+ boolean + + + + + + +
has_edge(self, + u, + v)
+ Return whether an edge between nodes u and v exists.
+ + +
+ +
+ boolean + + + + + + +
has_node(self, + node)
+ Return whether the requested node exists.
+ + +
+ +
+ graph + + + + + + +
inverse(self)
+ Return the inverse of the graph.
+ + +
+ +
+ list + + + + + + +
neighbors(self, + node)
+ Return all nodes that are directly accessible from given node.
+ + +
+ +
+ list + + + + + + +
nodes(self)
+ Return node list.
+ + +
+ +
+ number + + + + + + +
order(self, + node)
+ Return the order of the given node.
+ + +
+ +
+   + + + + + + +
set_edge_label(self, + u, + v, + label)
+ Set the label of an edge.
+ + +
+ +
+   + + + + + + +
set_edge_weight(self, + u, + v, + wt)
+ Set the weight of an edge.
+ + +
+ +
+ iterator + + + + + + +
traversal(self, + node, + order='pre')
+ Graph traversal iterator.
+ + +
+ +
+   + + + + + + +
generate(self, + num_nodes, + num_edges, + weight_range=(1, 1))
+ Add nodes and random edges to the graph.
+ + +
+ +
+   + + + + + + +
read(self, + string, + fmt='xml')
+ Read a graph from a string.
+ + +
+ +
+ string + + + + + + +
write(self, + fmt='xml')
+ Write the graph to a string.
+ + +
+ +
+ dictionary + + + + + + +
accessibility(self)
+ Accessibility matrix (transitive closure).
+ + +
+ +
+ dictionary + + + + + + +
breadth_first_search(self, + root=None)
+ Breadth-first search.
+ + +
+ +
+ dictionary + + + + + + +
connected_components(self)
+ Connected components.
+ + +
+ +
+ list + + + + + + +
cut_edges(self)
+ Return the cut-edges of the given graph.
+ + +
+ +
+ list + + + + + + +
cut_nodes(self)
+ Return the cut-nodes of the given graph.
+ + +
+ +
+ tuple + + + + + + +
depth_first_search(self, + root=None)
+ Depht-first search.
+ + +
+ +
+ list + + + + + + +
minimal_spanning_tree(self, + root=None)
+ Minimal spanning tree.
+ + +
+ +
+ tuple + + + + + + +
shortest_path(self, + source)
+ Return the shortest path distance between source node and all other + nodes using Dijkstra's algorithm.
+ + +
+ +
+

Inherited from object: + __delattr__, + __getattribute__, + __hash__, + __new__, + __reduce__, + __reduce_ex__, + __repr__, + __setattr__ +

+
+ + + + + + + + + +
+ Properties
+

Inherited from object: + __class__ +

+
+ + + + + + +
+ Method Details
+ +
+ +
+ + +
+

__init__(self) +
(Constructor) +

+
  +
+ +

Initialize a graph.

+
+
Overrides: + object.__init__ +
+
+
+
+ +
+ +
+ + +
+

__getitem__(self, + node) +
(Indexing operator) +

+
  +
+ +

Return a iterator passing through all neighbors of the given node.

+
+
Returns: iterator
+
Iterator passing through all neighbors of the given node.
+
+
+
+ +
+ +
+ + +
+

__iter__(self) +

+
  +
+ +

Return a iterator passing through all nodes in the graph.

+
+
Returns: iterator
+
Iterator passing through all nodes in the graph.
+
+
+
+ +
+ +
+ + +
+

__len__(self) +
(Length operator) +

+
  +
+ +

Return the order of the graph when requested by len().

+
+
Returns: number
+
Size of the graph.
+
+
+
+ +
+ +
+ + +
+

__str__(self) +
(Informal representation operator) +

+
  +
+ +

Return a string representing the graph when requested by str() (or + print).

+
+
Returns: string
+
String representing the graph.
+
Overrides: + object.__str__ +
+
+
+
+ +
+ +
+ + +
+

add_edge(self, + u, + v, + wt=1, + label='', + attrs=[]) +

+
  +
+ +

Add an edge (u,v) to the graph connecting nodes u and v.

+
+
Parameters:
+
    +
  • u (node) - One node.
  • +
  • v (node) - Other node.
  • +
  • wt (number) - Edge weight.
  • +
  • label (string) - Edge label.
  • +
  • attrs (list) - List of node attributes specified as (attribute, value) tuples.
  • +
+
+
+
+ +
+ +
+ + +
+

add_edge_attribute(self, + u, + v, + attr) +

+
  +
+ +

Add attribute to the given edge.

+
+
Parameters:
+
    +
  • u (node) - One node.
  • +
  • v (node) - Other node.
  • +
  • attr (tuple) - Node attribute specified as a tuple in the form (attribute, + value).
  • +
+
+
+
+ +
+ +
+ + +
+

add_graph(self, + graph) +

+
  +
+ +

Add other graph to the graph.

+
+
Parameters:
+
    +
  • graph (graph) - Graph
  • +
+
+

Attention: + Attributes and labels are not preserved. +

+
+
+ +
+ +
+ + +
+

add_node(self, + node, + attrs=[]) +

+
  +
+ +

Add given node to the graph.

+
+
Parameters:
+
    +
  • node (node) - Node identifier.
  • +
  • attrs (list) - List of node attributes specified as (attribute, value) tuples.
  • +
+
+

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(). +

+
+
+ +
+ +
+ + +
+

add_node_attribute(self, + node, + attr) +

+
  +
+ +

Add attribute to the given node.

+
+
Parameters:
+
    +
  • node (node) - Node identifier
  • +
  • attr (tuple) - Node attribute specified as a tuple in the form (attribute, + value).
  • +
+
+
+
+ +
+ +
+ + +
+

add_nodes(self, + nodelist) +

+
  +
+ +

Add given nodes to the graph.

+
+
Parameters:
+
    +
  • nodelist (list) - List of nodes to be added 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(). +

+
+
+ +
+ +
+ + +
+

add_spanning_tree(self, + st) +

+
  +
+ +

Add a spanning tree to the graph.

+
+
Parameters:
+
    +
  • st (dictionary) - Spanning tree.
  • +
+
+
+
+ +
+ +
+ + +
+

complete(self) +

+
  +
+ +

Make the graph a complete graph.

+
+
+

Attention: + This will modify the current graph. +

+
+
+ +
+ +
+ + +
+

del_edge(self, + u, + v) +

+
  +
+ +

Remove an edge (u, v) from the graph.

+
+
Parameters:
+
    +
  • u (node) - One node.
  • +
  • v (node) - Other node.
  • +
+
+
+
+ +
+ +
+ + +
+

del_node(self, + node) +

+
  +
+ +

Remove a node from the graph.

+
+
Parameters:
+
    +
  • node (node) - Node identifier.
  • +
+
+
+
+ +
+ +
+ + +
+

edges(self) +

+
  +
+ +

Return all edges in the graph.

+
+
Returns: list
+
List of all edges in the graph.
+
+
+
+ +
+ +
+ + +
+

get_edge_attributes(self, + u, + v) +

+
  +
+ +

Return the attributes of the given edge.

+
+
Parameters:
+
    +
  • u (node) - One node.
  • +
  • v (node) - Other node.
  • +
+
Returns: list
+
List of attributes specified tuples in the form (attribute, + value).
+
+
+
+ +
+ +
+ + +
+

get_edge_label(self, + u, + v) +

+
  +
+ +

Get the label of an edge.

+
+
Parameters:
+
    +
  • u (node) - One node.
  • +
  • v (node) - Other node.
  • +
+
Returns: string
+
Edge label
+
+
+
+ +
+ +
+ + +
+

get_edge_weight(self, + u, + v) +

+
  +
+ +

Get the weight of an edge.

+
+
Parameters:
+
    +
  • u (node) - One node.
  • +
  • v (node) - Other node.
  • +
+
Returns: number
+
Edge weight.
+
+
+
+ +
+ +
+ + +
+

get_node_attributes(self, + node) +

+
  +
+ +

Return the attributes of the given node.

+
+
Parameters:
+
    +
  • node (node) - Node identifier
  • +
+
Returns: list
+
List of attributes specified tuples in the form (attribute, + value).
+
+
+
+ +
+ +
+ + +
+

has_edge(self, + u, + v) +

+
  +
+ +

Return whether an edge between nodes u and v exists.

+
+
Parameters:
+
    +
  • u (node) - One node.
  • +
  • v (node) - Other node.
  • +
+
Returns: boolean
+
Truth-value for edge existence.
+
+
+
+ +
+ +
+ + +
+

has_node(self, + node) +

+
  +
+ +

Return whether the requested node exists.

+
+
Parameters:
+
    +
  • node (node) - Node identifier
  • +
+
Returns: boolean
+
Truth-value for node existence.
+
+
+
+ +
+ +
+ + +
+

inverse(self) +

+
  +
+ +

Return the inverse of the graph.

+
+
Returns: graph
+
Complement graph for the graph.
+
+
+
+ +
+ +
+ + +
+

neighbors(self, + node) +

+
  +
+ +

Return all nodes that are directly accessible from given node.

+
+
Parameters:
+
    +
  • node (node) - Node identifier
  • +
+
Returns: list
+
List of nodes directly accessible from given node.
+
+
+
+ +
+ +
+ + +
+

nodes(self) +

+
  +
+ +

Return node list.

+
+
Returns: list
+
Node list.
+
+
+
+ +
+ +
+ + +
+

order(self, + node) +

+
  +
+ +

Return the order of the given node.

+
+
Returns: number
+
Order of the given node.
+
+
+
+ +
+ +
+ + +
+

set_edge_label(self, + u, + v, + label) +

+
  +
+ +

Set the label of an edge.

+
+
Parameters:
+
    +
  • u (node) - One node.
  • +
  • v (node) - Other node.
  • +
  • label (string) - Edge label.
  • +
+
+
+
+ +
+ +
+ + +
+

set_edge_weight(self, + u, + v, + wt) +

+
  +
+ +

Set the weight of an edge.

+
+
Parameters:
+
    +
  • u (node) - One node.
  • +
  • v (node) - Other node.
  • +
  • wt (number) - Edge weight.
  • +
+
+
+
+ +
+ +
+ + +
+

traversal(self, + node, + order='pre') +

+
  +
+ +

Graph traversal iterator.

+
+
Parameters:
+
    +
  • node (node) - Node.
  • +
  • order (string) - traversal ordering. Possible values are: +
      +
    1. + 'pre' - Preordering (default) +
    2. +
    +
      +
    1. + 'post' - Postordering +
    2. +
  • +
+
Returns: iterator
+
Traversal iterator.
+
+
+
+ +
+ +
+ + +
+

generate(self, + num_nodes, + num_edges, + weight_range=(1, 1)) +

+
  +
+ +

Add nodes and random edges to the graph.

+
+
Parameters:
+
    +
  • num_nodes (number) - Number of nodes.
  • +
  • num_edges (number) - Number of edges.
  • +
  • weight_range (tuple) - tuple of two integers as lower and upper limits on randomly + generated weights (uniform distribution).
  • +
+
+
+
+ +
+ +
+ + +
+

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.

+
+
Parameters:
+
    +
  • string (string) - Input string specifying a graph.
  • +
  • fmt (string) - Input format. Possible formats are: +
      +
    1. + 'xml' - XML (default) +
    2. +
  • +
+
+
+
+ +
+ +
+ + +
+

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.

+
+
Parameters:
+
    +
  • fmt (string) - Output format. Possible formats are: +
      +
    1. + 'xml' - XML (default) +
    2. +
    3. + 'dot' - DOT Language (for GraphViz) +
    4. +
    5. + 'dotwt' - DOT Language with weight information +
    6. +
  • +
+
Returns: string
+
String specifying the graph.
+
+
+
+ +
+ +
+ + +
+

accessibility(self) +

+
  +
+ +

Accessibility matrix (transitive closure).

+
+
Returns: dictionary
+
Accessibility information for each node.
+
+
+
+ +
+ +
+ + +
+

breadth_first_search(self, + root=None) +

+
  +
+ +

Breadth-first search.

+
+
Parameters:
+
    +
  • root (node) - Optional root node (will explore only root's connected component)
  • +
+
Returns: dictionary
+
A tuple containing a dictionary and a list. +
    +
  1. + Generated spanning tree +
  2. +
  3. + Graph's level-based ordering +
  4. +
+
+
+
+ +
+ +
+ + +
+

connected_components(self) +

+
  +
+ +

Connected components.

+
+
Returns: dictionary
+
Pairing that associates each node to its connected component.
+
+

Attention: + Indentification of connected components is meaningful only for + non-directed graphs. +

+
+
+ +
+ +
+ + +
+

cut_edges(self) +

+
  +
+ +

Return the cut-edges of the given graph.

+
+
Returns: list
+
List of cut-edges.
+
+
+
+ +
+ +
+ + +
+

cut_nodes(self) +

+
  +
+ +

Return the cut-nodes of the given graph.

+
+
Returns: list
+
List of cut-nodes.
+
+
+
+ +
+ +
+ + +
+

depth_first_search(self, + root=None) +

+
  +
+ +

Depht-first search.

+
+
Parameters:
+
    +
  • root (node) - Optional root node (will explore only root's connected component)
  • +
+
Returns: tuple
+
tupple containing a dictionary and two lists: +
    +
  1. + Generated spanning tree +
  2. +
  3. + Graph's preordering +
  4. +
  5. + Graph's postordering +
  6. +
+
+
+
+ +
+ +
+ + +
+

minimal_spanning_tree(self, + root=None) +

+
  +
+ +

Minimal spanning tree.

+
+
Parameters:
+
    +
  • root (node) - Optional root node (will explore only root's connected component)
  • +
+
Returns: list
+
Generated spanning tree.
+
+

Attention: + Minimal spanning tree meaningful only for weighted graphs. +

+
+
+ +
+ +
+ + +
+

shortest_path(self, + source) +

+
  +
+ +

Return the shortest path distance between source node and all other + nodes using Dijkstra's algorithm.

+
+
Parameters:
+
    +
  • source (node) - Node from which to start the search.
  • +
+
Returns: tuple
+
A tuple containing two dictionaries, each keyed by target nodes. +
    +
  1. + Shortest path spanning tree +
  2. +
  3. + Shortest distance from given source to each target node +
  4. +
+

Inaccessible target nodes do not appear in either + dictionary.

+
+

Attention: + All weights must be nonnegative. +

+
+
+
+ + + + + + + + + + + + + + + + + + + + + + + + +
+ + + + diff -r 01f8c7aabb7e -r 06c2228e39cb thirdparty/python-graph/docs/graph.hypergraph-class.html --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/thirdparty/python-graph/docs/graph.hypergraph-class.html Wed Nov 26 23:56:19 2008 +0000 @@ -0,0 +1,1032 @@ + + + + + graph.hypergraph + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
+ + Package graph :: + Class hypergraph + + + + +
+
+ +

Class hypergraph

+
+object --+
+         |
+        hypergraph
+
+ +
+

Hypergraph class.

+

Hypergraphs are a generalization of graphs where an edge (called + hyperedge) can connect more than two nodes.

+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
+ Instance Methods
+   + + + + + + +
__init__(self)
+ Initialize a hypergraph.
+ + +
+ +
+ number + + + + + + +
__len__(self)
+ Return the size of the hypergraph when requested by len().
+ + +
+ +
+ string + + + + + + +
__str__(self)
+ Return a string representing the hypergraph when requested by str() + (or print).
+ + +
+ +
+   + + + + + + +
add_hyperedge(self, + hyperedge)
+ Add given hyperedge to the hypergraph.
+ + +
+ +
+   + + + + + + +
add_hyperedges(self, + edgelist)
+ Add given hyperedges to the hypergraph.
+ + +
+ +
+   + + + + + + +
add_node(self, + node)
+ Add given node to the hypergraph.
+ + +
+ +
+   + + + + + + +
add_nodes(self, + nodelist)
+ Add given nodes to the hypergraph.
+ + +
+ +
+ boolean + + + + + + +
has_node(self, + node)
+ Return whether the requested node exists.
+ + +
+ +
+ list + + + + + + +
hyperedges(self)
+ Return hyperedge list.
+ + +
+ +
+   + + + + + + +
link(self, + node, + hyperedge)
+ Link given node and hyperedge.
+ + +
+ +
+ list + + + + + + +
links(self, + obj)
+ Return all objects linked to the given one.
+ + +
+ +
+ list + + + + + + +
nodes(self)
+ Return node list.
+ + +
+ +
+   + + + + + + +
unlink(self, + node, + hyperedge)
+ Unlink given node and hyperedge.
+ + +
+ +
+   + + + + + + +
read(self, + string, + fmt='xml')
+ Read a hypergraph from a string.
+ + +
+ +
+ string + + + + + + +
write(self, + fmt='xml')
+ Write the hypergraph to a string.
+ + +
+ +
+ dictionary + + + + + + +
accessibility(self)
+ Accessibility matrix (transitive closure).
+ + +
+ +
+ dictionary + + + + + + +
connected_components(self)
+ Connected components.
+ + +
+ +
+ list + + + + + + +
cut_hyperedges(self)
+ Return the cut-hyperedges of the given hypergraph.
+ + +
+ +
+ list + + + + + + +
cut_nodes(self)
+ Return the cut-nodes of the given hypergraph.
+ + +
+ +
+ int + + + + + + +
rank(self)
+ Return the rank of the given hypergraph.
+ + +
+ +
+

Inherited from object: + __delattr__, + __getattribute__, + __hash__, + __new__, + __reduce__, + __reduce_ex__, + __repr__, + __setattr__ +

+
+ + + + + + + + + +
+ Properties
+

Inherited from object: + __class__ +

+
+ + + + + + +
+ Method Details
+ +
+ +
+ + +
+

__init__(self) +
(Constructor) +

+
  +
+ +

Initialize a hypergraph.

+
+
Overrides: + object.__init__ +
+
+
+
+ +
+ +
+ + +
+

__len__(self) +
(Length operator) +

+
  +
+ +

Return the size of the hypergraph when requested by len().

+
+
Returns: number
+
Size of the hypergraph.
+
+
+
+ +
+ +
+ + +
+

__str__(self) +
(Informal representation operator) +

+
  +
+ +

Return a string representing the hypergraph when requested by str() + (or print).

+
+
Returns: string
+
String representing the hypergraph.
+
Overrides: + object.__str__ +
+
+
+
+ +
+ +
+ + +
+

add_hyperedge(self, + hyperedge) +

+
  +
+ +

Add given hyperedge to the hypergraph.

+
+
Parameters:
+
    +
  • hyperedge (hyperedge) - Hyperedge identifier.
  • +
+
+

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(). +

+
+
+ +
+ +
+ + +
+

add_hyperedges(self, + edgelist) +

+
  +
+ +

Add given hyperedges to the hypergraph.

+
+
Parameters:
+
    +
  • edgelist (list) - List of hyperedge-nodes to be added to the graph.
  • +
+
+

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(). +

+
+
+ +
+ +
+ + +
+

add_node(self, + node) +

+
  +
+ +

Add given node to the hypergraph.

+
+
Parameters:
+
    +
  • node (node) - Node identifier.
  • +
+
+

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(). +

+
+
+ +
+ +
+ + +
+

add_nodes(self, + nodelist) +

+
  +
+ +

Add given nodes to the hypergraph.

+
+
Parameters:
+
    +
  • nodelist (list) - List of nodes to be added 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(). +

+
+
+ +
+ +
+ + +
+

has_node(self, + node) +

+
  +
+ +

Return whether the requested node exists.

+
+
Parameters:
+
    +
  • node (node) - Node identifier
  • +
+
Returns: boolean
+
Truth-value for node existence.
+
+
+
+ +
+ +
+ + +
+

hyperedges(self) +

+
  +
+ +

Return hyperedge list.

+
+
Returns: list
+
List of hyperedges linked to the given node.
+
+
+
+ +
+ +
+ + +
+

link(self, + node, + hyperedge) +

+
  +
+ +

Link given node and hyperedge.

+
+
Parameters:
+
    +
  • node (node) - Node.
  • +
  • hyperedge (node) - Hyperedge.
  • +
+
+
+
+ +
+ +
+ + +
+

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.

+
+
Parameters:
+
    +
  • obj (node or hyperedge) - Object identifier.
  • +
+
Returns: list
+
List of objects linked to the given one.
+
+
+
+ +
+ +
+ + +
+

nodes(self) +

+
  +
+ +

Return node list.

+
+
Returns: list
+
Node list.
+
+
+
+ +
+ +
+ + +
+

unlink(self, + node, + hyperedge) +

+
  +
+ +

Unlink given node and hyperedge.

+
+
Parameters:
+
    +
  • node (node) - Node.
  • +
  • hyperedge (hyperedge) - Hyperedge.
  • +
+
+
+
+ +
+ +
+ + +
+

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.

+
+
Parameters:
+
    +
  • string (string) - Input string specifying a graph.
  • +
  • fmt (string) - Input format. Possible formats are: +
      +
    1. + 'xml' - XML (default) +
    2. +
  • +
+
+
+
+ +
+ +
+ + +
+

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.

+
+
Parameters:
+
    +
  • fmt (string) - Output format. Possible formats are: +
      +
    1. + 'xml' - XML (default) +
    2. +
    3. + 'dot' - DOT Language (for GraphViz) +
    4. +
    5. + 'dotclr' - DOT Language, coloured +
    6. +
  • +
+
Returns: string
+
String specifying the graph.
+
+
+
+ +
+ +
+ + +
+

accessibility(self) +

+
  +
+ +

Accessibility matrix (transitive closure).

+
+
Returns: dictionary
+
Accessibility information for each node.
+
+
+
+ +
+ +
+ + +
+

connected_components(self) +

+
  +
+ +

Connected components.

+
+
Returns: dictionary
+
Pairing that associates each node to its connected component.
+
+
+
+ +
+ +
+ + +
+

cut_hyperedges(self) +

+
  +
+ +

Return the cut-hyperedges of the given hypergraph.

+
+
Returns: list
+
List of cut-nodes.
+
+
+
+ +
+ +
+ + +
+

cut_nodes(self) +

+
  +
+ +

Return the cut-nodes of the given hypergraph.

+
+
Returns: list
+
List of cut-nodes.
+
+
+
+ +
+ +
+ + +
+

rank(self) +

+
  +
+ +

Return the rank of the given hypergraph.

+
+
Returns: int
+
Rank of graph.
+
+
+
+
+ + + + + + + + + + + + + + + + + + + + + + + + +
+ + + + diff -r 01f8c7aabb7e -r 06c2228e39cb thirdparty/python-graph/docs/graph.minmax-module.html --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/thirdparty/python-graph/docs/graph.minmax-module.html Wed Nov 26 23:56:19 2008 +0000 @@ -0,0 +1,237 @@ + + + + + graph.minmax + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
+ + Package graph :: + Module minmax + + + + +
+
+ +

Module minmax

+

Minimization and maximization algorithms for python-graph.

+ + + + + + + + + + + + + +
+ Functions
+ dictionary + + + + + + +
minimal_spanning_tree(graph, + root=None)
+ Minimal spanning tree.
+ + +
+ +
+ tuple + + + + + + +
shortest_path(graph, + source)
+ Return the shortest path distance between source and all other nodes + using Dijkstra's algorithm.
+ + +
+ +
+ + + + + + +
+ Function Details
+ +
+ +
+ + +
+

minimal_spanning_tree(graph, + root=None) +

+
  +
+ +

Minimal spanning tree.

+
+
Parameters:
+
    +
  • graph (graph) - Graph.
  • +
  • root (node) - Optional root node (will explore only root's connected component)
  • +
+
Returns: dictionary
+
Generated spanning tree.
+
+

Attention: + Minimal spanning tree meaningful only for weighted graphs. +

+
+
+ +
+ +
+ + +
+

shortest_path(graph, + source) +

+
  +
+ +

Return the shortest path distance between source and all other nodes + using Dijkstra's algorithm.

+
+
Parameters:
+
    +
  • graph (graph) - Graph.
  • +
  • source (node) - Node from which to start the search.
  • +
+
Returns: tuple
+
A tuple containing two dictionaries, each keyed by target nodes. +
    +
  1. + Shortest path spanning tree +
  2. +
  3. + Shortest distance from given source to each target node +
  4. +
+

Inaccessible target nodes do not appear in either + dictionary.

+
+

Attention: + All weights must be nonnegative. +

+
+
+
+ + + + + + + + + + + + + + + + + + + + + + + + +
+ + + + diff -r 01f8c7aabb7e -r 06c2228e39cb thirdparty/python-graph/docs/graph.readwrite-module.html --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/thirdparty/python-graph/docs/graph.readwrite-module.html Wed Nov 26 23:56:19 2008 +0000 @@ -0,0 +1,496 @@ + + + + + graph.readwrite + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
+ + Package graph :: + Module readwrite + + + + +
+
+ +

Module readwrite

+

Functions for reading and writing graphs.

+ + + + + + + + + + + + + + + + + + + + + + + + + + + + +
+ Functions
+   + + + + + + +
read_xml(graph, + string)
+ Read a graph from a XML document.
+ + +
+ +
+ string + + + + + + +
write_xml(graph)
+ Return a string specifying the given graph as a XML document.
+ + +
+ +
+ string + + + + + + +
write_dot_graph(graph, + wt)
+ Return a string specifying the given graph in DOT Language.
+ + +
+ +
+ string + + + + + + +
write_dot_digraph(graph, + wt)
+ Return a string specifying the given digraph in DOT Language.
+ + +
+ +
+ string + + + + + + +
write_dot_hypergraph(hypergraph, + coloured=False)
+ Return a string specifying the given hypergraph in DOT Language.
+ + +
+ +
+ string + + + + + + +
write_xml_hypergraph(hypergraph)
+ Return a string specifying the given hypergraph as a XML document.
+ + +
+ +
+   + + + + + + +
read_xml_hypergraph(hypergraph, + string)
+ Read a graph from a XML document.
+ + +
+ +
+ + + + + + + + + +
+ Variables
+   + + colors = ['aquamarine4', 'blue4', 'brown4', 'cornflowerblue', ... +
+ + + + + + +
+ Function Details
+ +
+ +
+ + +
+

read_xml(graph, + string) +

+
  +
+ +

Read a graph from a XML document. Nodes and edges specified in the + input will be added to the current graph.

+
+
Parameters:
+
    +
  • graph (graph) - Graph
  • +
  • string (string) - Input string in XML format specifying a graph.
  • +
+
+
+
+ +
+ +
+ + +
+

write_xml(graph) +

+
  +
+ +

Return a string specifying the given graph as a XML document.

+
+
Parameters:
+
    +
  • graph (graph) - Graph.
  • +
+
Returns: string
+
String specifying the graph as a XML document.
+
+
+
+ +
+ +
+ + +
+

write_dot_graph(graph, + wt) +

+
  +
+ +

Return a string specifying the given graph in DOT Language.

+
+
Parameters:
+
    +
  • graph (graph) - Graph.
  • +
  • wt (boolean) - Whether edges should be labelled with its weight.
  • +
+
Returns: string
+
String specifying the graph in DOT Language.
+
+
+
+ +
+ +
+ + +
+

write_dot_digraph(graph, + wt) +

+
  +
+ +

Return a string specifying the given digraph in DOT Language.

+
+
Parameters:
+
    +
  • graph (graph) - Graph.
  • +
  • wt (boolean) - Whether arrows should be labelled with its weight.
  • +
+
Returns: string
+
String specifying the graph in DOT Language.
+
+
+
+ +
+ +
+ + +
+

write_dot_hypergraph(hypergraph, + coloured=False) +

+
  +
+ +

Return a string specifying the given hypergraph in DOT Language.

+
+
Parameters:
+
    +
  • hypergraph (hypergraph) - Hypergraph.
  • +
  • coloured (boolean) - Whether hyperedges should be coloured.
  • +
+
Returns: string
+
String specifying the hypergraph in DOT Language.
+
+
+
+ +
+ +
+ + +
+

write_xml_hypergraph(hypergraph) +

+
  +
+ +

Return a string specifying the given hypergraph as a XML document.

+
+
Parameters:
+
    +
  • hypergraph (hypergraph) - Hypergraph.
  • +
+
Returns: string
+
String specifying the graph as a XML document.
+
+
+
+ +
+ +
+ + +
+

read_xml_hypergraph(hypergraph, + string) +

+
  +
+ +

Read a graph from a XML document. Nodes and hyperedges specified in + the input will be added to the current graph.

+
+
Parameters:
+
    +
  • hypergraph (hypergraph) - Hypergraph
  • +
  • string (string) - Input string in XML format specifying a graph.
  • +
+
+
+
+
+ + + + + + +
+ Variables Details
+ +
+ +
+

colors

+ +
+
+
+
Value:
+
+['aquamarine4',
+ 'blue4',
+ 'brown4',
+ 'cornflowerblue',
+ 'cyan4',
+ 'darkgreen',
+ 'darkorange3',
+ 'darkorchid4',
+...
+
+
+
+
+
+
+ + + + + + + + + + + + + + + + + + + + + + + + +
+ + + + diff -r 01f8c7aabb7e -r 06c2228e39cb thirdparty/python-graph/docs/graph.searching-module.html --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/thirdparty/python-graph/docs/graph.searching-module.html Wed Nov 26 23:56:19 2008 +0000 @@ -0,0 +1,238 @@ + + + + + graph.searching + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
+ + Package graph :: + Module searching + + + + +
+
+ +

Module searching

+

Search algorithms for python-graph.

+ + + + + + + + + + + + + +
+ Functions
+ tuple + + + + + + +
breadth_first_search(graph, + root=None)
+ Breadth-first search.
+ + +
+ +
+ tuple + + + + + + +
depth_first_search(graph, + root=None)
+ Depth-first search.
+ + +
+ +
+ + + + + + +
+ Function Details
+ +
+ +
+ + +
+

breadth_first_search(graph, + root=None) +

+
  +
+ +

Breadth-first search.

+
+
Parameters:
+
    +
  • graph (graph) - Graph.
  • +
  • root (node) - Optional root node (will explore only root's connected component)
  • +
+
Returns: tuple
+
A tuple containing a dictionary and a list. +
    +
  1. + Generated spanning tree +
  2. +
  3. + Graph's level-based ordering +
  4. +
+
+
+
+ +
+ +
+ + +
+

depth_first_search(graph, + root=None) +

+
  +
+ +

Depth-first search.

+
+
Parameters:
+
    +
  • graph (graph) - Graph.
  • +
  • root (node) - Optional root node (will explore only root's connected component)
  • +
+
Returns: tuple
+
A tupple containing a dictionary and two lists: +
    +
  1. + Generated spanning tree +
  2. +
  3. + Graph's preordering +
  4. +
  5. + Graph's postordering +
  6. +
+
+
+
+
+ + + + + + + + + + + + + + + + + + + + + + + + +
+ + + + diff -r 01f8c7aabb7e -r 06c2228e39cb thirdparty/python-graph/docs/graph.sorting-module.html --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/thirdparty/python-graph/docs/graph.sorting-module.html Wed Nov 26 23:56:19 2008 +0000 @@ -0,0 +1,174 @@ + + + + + graph.sorting + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
+ + Package graph :: + Module sorting + + + + +
+
+ +

Module sorting

+

Sorting algorithms for python-graph.

+ + + + + + + + + + +
+ Functions
+ list + + + + + + +
topological_sorting(graph)
+ Topological sorting.
+ + +
+ +
+ + + + + + +
+ Function Details
+ +
+ +
+ + +
+

topological_sorting(graph) +

+
  +
+ +

Topological sorting.

+
+
Parameters:
+
    +
  • graph (graph) - Graph.
  • +
+
Returns: list
+
Topological sorting for the graph.
+
+

Attention: + Topological sorting is meaningful only for directed acyclic graphs. +

+
+
+
+ + + + + + + + + + + + + + + + + + + + + + + + +
+ + + + diff -r 01f8c7aabb7e -r 06c2228e39cb thirdparty/python-graph/docs/graph.traversal-module.html --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/thirdparty/python-graph/docs/graph.traversal-module.html Wed Nov 26 23:56:19 2008 +0000 @@ -0,0 +1,186 @@ + + + + + graph.traversal + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
+ + Package graph :: + Module traversal + + + + +
+
+ +

Module traversal

+

Traversal algorithms for python-graph.

+ + + + + + + + + + +
+ Functions
+ iterator + + + + + + +
traversal(graph, + node, + order)
+ Graph traversal iterator.
+ + +
+ +
+ + + + + + +
+ Function Details
+ +
+ +
+ + +
+

traversal(graph, + node, + order) +

+
  +
+ +

Graph traversal iterator.

+
+
Parameters:
+
    +
  • node (node) - Node.
  • +
  • order (string) - traversal ordering. Possible values are: +
      +
    1. + 'pre' - Preordering (default) +
    2. +
    +
      +
    1. + 'post' - Postordering +
    2. +
  • +
+
Returns: iterator
+
Traversal iterator.
+
+
+
+
+ + + + + + + + + + + + + + + + + + + + + + + + +
+ + + + diff -r 01f8c7aabb7e -r 06c2228e39cb thirdparty/python-graph/docs/help.html --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/thirdparty/python-graph/docs/help.html Wed Nov 26 23:56:19 2008 +0000 @@ -0,0 +1,272 @@ + + + + + Help + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
  + + +
+
+ +

API Documentation

+ +

This document contains the API (Application Programming Interface) +documentation for python-graph. Documentation for the Python +objects defined by the project is divided into separate pages for each +package, module, and class. The API documentation also includes two +pages containing information about the project as a whole: a trees +page, and an index page.

+ +

Object Documentation

+ +

Each Package Documentation page contains:

+
    +
  • A description of the package.
  • +
  • A list of the modules and sub-packages contained by the + package.
  • +
  • A summary of the classes defined by the package.
  • +
  • A summary of the functions defined by the package.
  • +
  • A summary of the variables defined by the package.
  • +
  • A detailed description of each function defined by the + package.
  • +
  • A detailed description of each variable defined by the + package.
  • +
+ +

Each Module Documentation page contains:

+
    +
  • A description of the module.
  • +
  • A summary of the classes defined by the module.
  • +
  • A summary of the functions defined by the module.
  • +
  • A summary of the variables defined by the module.
  • +
  • A detailed description of each function defined by the + module.
  • +
  • A detailed description of each variable defined by the + module.
  • +
+ +

Each Class Documentation page contains:

+
    +
  • A class inheritance diagram.
  • +
  • A list of known subclasses.
  • +
  • A description of the class.
  • +
  • A summary of the methods defined by the class.
  • +
  • A summary of the instance variables defined by the class.
  • +
  • A summary of the class (static) variables defined by the + class.
  • +
  • A detailed description of each method defined by the + class.
  • +
  • A detailed description of each instance variable defined by the + class.
  • +
  • A detailed description of each class (static) variable defined + by the class.
  • +
+ +

Project Documentation

+ +

The Trees page contains the module and class hierarchies:

+
    +
  • The module hierarchy lists every package and module, with + modules grouped into packages. At the top level, and within each + package, modules and sub-packages are listed alphabetically.
  • +
  • The class hierarchy lists every class, grouped by base + class. If a class has more than one base class, then it will be + listed under each base class. At the top level, and under each base + class, classes are listed alphabetically.
  • +
+ +

The Index page contains indices of terms and + identifiers:

+
    +
  • The term index lists every term indexed by any object's + documentation. For each term, the index provides links to each + place where the term is indexed.
  • +
  • The identifier index lists the (short) name of every package, + module, class, method, function, variable, and parameter. For each + identifier, the index provides a short description, and a link to + its documentation.
  • +
+ +

The Table of Contents

+ +

The table of contents occupies the two frames on the left side of +the window. The upper-left frame displays the project +contents, and the lower-left frame displays the module +contents:

+ + + + + + + + + +
+ Project
Contents
...
+ API
Documentation
Frame


+
+ Module
Contents
 
...
  +

+ +

The project contents frame contains a list of all packages +and modules that are defined by the project. Clicking on an entry +will display its contents in the module contents frame. Clicking on a +special entry, labeled "Everything," will display the contents of +the entire project.

+ +

The module contents frame contains a list of every +submodule, class, type, exception, function, and variable defined by a +module or package. Clicking on an entry will display its +documentation in the API documentation frame. Clicking on the name of +the module, at the top of the frame, will display the documentation +for the module itself.

+ +

The "frames" and "no frames" buttons below the top +navigation bar can be used to control whether the table of contents is +displayed or not.

+ +

The Navigation Bar

+ +

A navigation bar is located at the top and bottom of every page. +It indicates what type of page you are currently viewing, and allows +you to go to related pages. The following table describes the labels +on the navigation bar. Note that not some labels (such as +[Parent]) are not displayed on all pages.

+ + + + + + + + + + + + + + + + + + + + + + + + + + + + +
LabelHighlighted when...Links to...
[Parent](never highlighted) the parent of the current package
[Package]viewing a packagethe package containing the current object +
[Module]viewing a modulethe module containing the current object +
[Class]viewing a class the class containing the current object
[Trees]viewing the trees page the trees page
[Index]viewing the index page the index page
[Help]viewing the help page the help page
+ +

The "show private" and "hide private" buttons below +the top navigation bar can be used to control whether documentation +for private objects is displayed. Private objects are usually defined +as objects whose (short) names begin with a single underscore, but do +not end with an underscore. For example, "_x", +"__pprint", and "epydoc.epytext._tokenize" +are private objects; but "re.sub", +"__init__", and "type_" are not. However, +if a module defines the "__all__" variable, then its +contents are used to decide which objects are private.

+ +

A timestamp below the bottom navigation bar indicates when each +page was last updated.

+ + + + + + + + + + + + + + + + + + + + + + + + +
+ + + + diff -r 01f8c7aabb7e -r 06c2228e39cb thirdparty/python-graph/docs/identifier-index.html --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/thirdparty/python-graph/docs/identifier-index.html Wed Nov 26 23:56:19 2008 +0000 @@ -0,0 +1,616 @@ + + + + + Identifier Index + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
  + + +
+
+ +
+

Identifier Index

+
+[ + A + B + C + D + E + F + G + H + I + J + K + L + M + N + O + P + Q + R + S + T + U + V + W + X + Y + Z + _ +] +
+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +

A

+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +

B

+ + + + + + + + +

C

+ + + + + + + + + + + + + + + + + + + + + + + + + + + +

D

+ + + + + + + + + + + + + + + + + +

E

+ + + + + + + + +

G

+ + + + + + + + + + + + + + + + + + + + + + + + + + + +

H

+ + + + + + + + + + + + + + + + + +

I

+ + + + + + + + +

L

+ + + + + + + + +

M

+ + + + + + + + + + + + +

N

+ + + + + + + + + + + + +

O

+ + + + + + + + +

R

+ + + + + + + + + + + + + + + + + +

S

+ + + + + + + + + + + + + + + + + +

T

+ + + + + + + + + + + + +

U

+ + + + + + + + +

W

+ + + + + + + + + + + + + + + + + +

_

+ + + + + + + + + + + + + + + + + + + + + + + + + + + +
+

+ + + + + + + + + + + + + + + + + + + + + + + +
+ + + + diff -r 01f8c7aabb7e -r 06c2228e39cb thirdparty/python-graph/docs/index.html --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/thirdparty/python-graph/docs/index.html Wed Nov 26 23:56:19 2008 +0000 @@ -0,0 +1,168 @@ + + + + + graph + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
+ + Package graph + + + + +
+
+ +

Package graph

+

python-graph

+

A library for working with graphs in Python.

+ +
+

Version: + 1.3.1 +

+
+ + + + + + +
+ Submodules
+
+ +
+ + + + + + + + + + + + + + + +
+ Classes
+   + + graph
+ Graph class. +
+   + + digraph
+ Digraph class. +
+   + + hypergraph
+ Hypergraph class. +
+ + + + + + + + + + + + + + + + + + + + + + + + +
+ + + + diff -r 01f8c7aabb7e -r 06c2228e39cb thirdparty/python-graph/docs/module-tree.html --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/thirdparty/python-graph/docs/module-tree.html Wed Nov 26 23:56:19 2008 +0000 @@ -0,0 +1,119 @@ + + + + + Module Hierarchy + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
  + + +
+
+
+ [ Module Hierarchy + | Class Hierarchy ] +

+

Module Hierarchy

+ + + + + + + + + + + + + + + + + + + + + + + + + +
+ + + + diff -r 01f8c7aabb7e -r 06c2228e39cb thirdparty/python-graph/docs/redirect.html --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/thirdparty/python-graph/docs/redirect.html Wed Nov 26 23:56:19 2008 +0000 @@ -0,0 +1,38 @@ +Epydoc Redirect Page + + + + + + + + +

Epydoc Auto-redirect page

+ +

When javascript is enabled, this page will redirect URLs of +the form redirect.html#dotted.name to the +documentation for the object with the given fully-qualified +dotted name.

+

 

+ + + + + diff -r 01f8c7aabb7e -r 06c2228e39cb thirdparty/python-graph/examples/draw.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/thirdparty/python-graph/examples/draw.py Wed Nov 26 23:56:19 2008 +0000 @@ -0,0 +1,41 @@ +#!/usr/bin/env python + +# Copyright (c) 2007-2008 Pedro Matiello +# License: MIT (see COPYING file) + +import sys +sys.path.append('..') +sys.path.append('/usr/lib/graphviz/python/') +import graph +import gv + +# Graph creation +gr = graph.graph() + +# Add nodes and edges +gr.add_nodes(["Portugal","Spain","France","Germany","Belgium","Netherlands","Italy"]) +gr.add_node("England") +gr.add_node("Ireland") +gr.add_node("Scotland") +gr.add_node("Wales") + +gr.add_edge("Portugal", "Spain") +gr.add_edge("Spain","France") +gr.add_edge("France","Belgium") +gr.add_edge("France","Germany") +gr.add_edge("France","Italy",) +gr.add_edge("Belgium","Netherlands") +gr.add_edge("Germany","Belgium") +gr.add_edge("Germany","Netherlands") +gr.add_edge("England","Wales") +gr.add_edge("England","Scotland") +gr.add_edge("Scotland","Wales") + +# Print to DOT Language +dot = gr.write(fmt='dot') +print dot + +# Print graph as PNG image +gvv = gv.readstring(dot) +gv.layout(gvv,'neato') +gv.render(gvv,'png','graph.png') diff -r 01f8c7aabb7e -r 06c2228e39cb thirdparty/python-graph/examples/drawhyper.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/thirdparty/python-graph/examples/drawhyper.py Wed Nov 26 23:56:19 2008 +0000 @@ -0,0 +1,37 @@ +#!/usr/bin/env python + +# Copyright (c) 2007-2008 Pedro Matiello +# License: MIT (see COPYING file) + +import sys +sys.path.append('..') +sys.path.append('/usr/lib/graphviz/python/') +import graph +import gv + +# Graph creation +hgr = graph.hypergraph() + +# Add nodes and edges +hgr.add_nodes([1,2,3,4,5,6,7,8,9]) +hgr.add_hyperedges(['A','B','C','J']) +hgr.link(1,'A') +hgr.link(2,'A') +hgr.link(3,'A') +hgr.link(4,'A') +hgr.link(4,'B') +hgr.link(5,'B') +hgr.link(6,'B') +hgr.link(7,'C') +hgr.link(8,'C') +hgr.link(9,'C') +hgr.link(1,'J') +hgr.link(2,'J') +hgr.link(3,'J') +hgr.link(4,'J') + +# Print graph as PNG image +dot = hgr.write(fmt='dotclr') +gvv = gv.readstring(dot) +gv.layout(gvv,'neato') +gv.render(gvv,'png','hypergraph.png') diff -r 01f8c7aabb7e -r 06c2228e39cb thirdparty/python-graph/examples/ex1.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/thirdparty/python-graph/examples/ex1.py Wed Nov 26 23:56:19 2008 +0000 @@ -0,0 +1,65 @@ +#!/usr/bin/env python + +# Copyright (c) 2007-2008 Pedro Matiello +# License: MIT (see COPYING file) + +import sys +sys.path.append('..') +import graph +sys.path.append('/usr/lib/graphviz/python/') +import gv + +# Graph creation +gr = graph.graph() + +# Add nodes and edges +gr.add_nodes(["Portugal","Spain","France","Germany","Belgium","Netherlands","Italy"]) +gr.add_nodes(["Switzerland","Austria","Denmark","Poland","Czech Republic","Slovakia","Hungary"]) +gr.add_nodes(["England","Ireland","Scotland","Wales"]) + +gr.add_edge("Portugal", "Spain") +gr.add_edge("Spain","France") +gr.add_edge("France","Belgium") +gr.add_edge("France","Germany") +gr.add_edge("France","Italy",) +gr.add_edge("Belgium","Netherlands") +gr.add_edge("Germany","Belgium") +gr.add_edge("Germany","Netherlands") +gr.add_edge("England","Wales") +gr.add_edge("England","Scotland") +gr.add_edge("Scotland","Wales") +gr.add_edge("Switzerland","Austria") +gr.add_edge("Switzerland","Germany") +gr.add_edge("Switzerland","France") +gr.add_edge("Switzerland","Italy") +gr.add_edge("Austria","Germany") +gr.add_edge("Austria","Italy") +gr.add_edge("Austria","Czech Republic") +gr.add_edge("Austria","Slovakia") +gr.add_edge("Austria","Hungary") +gr.add_edge("Denmark","Germany") +gr.add_edge("Poland","Czech Republic") +gr.add_edge("Poland","Slovakia") +gr.add_edge("Poland","Germany") +gr.add_edge("Czech Republic","Slovakia") +gr.add_edge("Czech Republic","Germany") +gr.add_edge("Slovakia","Hungary") + +# Draw as PNG +dot = gr.write(fmt='dot') +gvv = gv.readstring(dot) +gv.layout(gvv,'dot') +gv.render(gvv,'png','europe.png') + +# Then, draw the breadth first search spanning tree rooted in Switzerland +st, order = gr.breadth_first_search(root="Switzerland") +gst = graph.digraph() +gst.add_spanning_tree(st) + +dot = gst.write(fmt='dot') +gvv = gv.readstring(dot) + +gv.layout(gvv,'dot') +gv.render(gvv,'png','europe-st.png') + + diff -r 01f8c7aabb7e -r 06c2228e39cb thirdparty/python-graph/examples/example.tls --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/thirdparty/python-graph/examples/example.tls Wed Nov 26 23:56:19 2008 +0000 @@ -0,0 +1,12 @@ +Q 0 1 2 3 +A a b +s 0 +F 1 3 +t a 0 1 +t b 0 2 +t a 1 3 +t b 1 3 +t a 2 0 +t b 2 1 +t a 3 2 +t b 3 3 diff -r 01f8c7aabb7e -r 06c2228e39cb thirdparty/python-graph/examples/graph.xml --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/thirdparty/python-graph/examples/graph.xml Wed Nov 26 23:56:19 2008 +0000 @@ -0,0 +1,37 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + diff -r 01f8c7aabb7e -r 06c2228e39cb thirdparty/python-graph/examples/lts2graph.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/thirdparty/python-graph/examples/lts2graph.py Wed Nov 26 23:56:19 2008 +0000 @@ -0,0 +1,115 @@ +#!/usr/bin/env python + +# Copyright (c) 2007-2008 Pedro Matiello +# +# Permission is hereby granted, free of charge, to any person +# obtaining a copy of this software and associated documentation +# files (the "Software"), to deal in the Software without +# restriction, including without limitation the rights to use, +# copy, modify, merge, publish, distribute, sublicense, and/or sell +# copies of the Software, and to permit persons to whom the +# Software is furnished to do so, subject to the following +# conditions: + +# The above copyright notice and this permission notice shall be +# included in all copies or substantial portions of the Software. + +# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES +# OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND +# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT +# HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, +# WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR +# OTHER DEALINGS IN THE SOFTWARE. + + +""" +This small application will build and draw a graph for a given finite definite automaton described +as a labelled transition system. + +This is a very naive, probably useless, possibly incorrect, barely tested implementation. No +validation is ever performed. Take care or it will burn your house and kill your cat. +""" + + +# Module metadata +__authors__ = "Pedro Matiello" +__license__ = "MIT" + + +# Imports +import sys +sys.path.append('..') +import graph +sys.path.append('/usr/lib/graphviz/python/') +import gv + + +def load_automaton(filename): + """ + Read a automaton described as a labelled transition system and build the equivalent graph. + + @type filename: string + @param filename: Name of the file containing the LTS-described automaton. + + @rtype: graph + @return: Automaton's graph. + """ + gr = graph.digraph() + infile = file(filename,'r') + line = infile.readline() + final = [] + while (line): + line = line.replace("\n",'').split(' ') + datatype = line[0] + data = line[1:] + if (datatype == 'Q'): + # States + for each in data: + gr.add_node(each) + if (datatype == 'A'): + # Alphabet + pass + if (datatype == 'F'): + # Final states + final = final + data + if (datatype == 's'): + # Initial state + gr.add_node('.',attrs=[('shape','point')]) + gr.add_edge('.',data[0]) + if (datatype == 't'): + # Transitions + if (gr.has_edge(data[1], data[2])): + gr.set_edge_label(data[1], data[2], \ + gr.get_edge_label(data[1], data[2]) + ', ' + data[0]) + else: + gr.add_edge(data[1], data[2], label=data[0]) + line = infile.readline() + + for node in gr: + if (node in final and node != '.'): + gr.add_node_attribute(node, ('shape','doublecircle')) + elif (node != '.'): + gr.add_node_attribute(node, ('shape','circle')) + + return gr, final + + +# Main +try: + filename = sys.argv[1] + gr, final = load_automaton(sys.argv[1]) + dot = gr.write(fmt='dot') +except IndexError: + print "Syntax: %s filename" % sys.argv[0] + sys.exit(1) +except IOError: + print "Can't open file %s" % filename + sys.exit(2) + + +# Print graph as PNG image +gvv = gv.readstring(dot) +gv.layout(gvv,'circo') +gv.render(gvv,'png',filename + '.png') diff -r 01f8c7aabb7e -r 06c2228e39cb thirdparty/python-graph/examples/read.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/thirdparty/python-graph/examples/read.py Wed Nov 26 23:56:19 2008 +0000 @@ -0,0 +1,17 @@ +#!/usr/bin/env python + +# Copyright (c) 2007-2008 Pedro Matiello +# License: MIT (see COPYING file) + +import sys +sys.path.append('..') +import graph + +gr = graph.graph() + +inputfile = file('graph.xml','r') +string = inputfile.read() +inputfile.close() + +gr.read(string) +print gr.write() diff -r 01f8c7aabb7e -r 06c2228e39cb thirdparty/python-graph/examples/write.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/thirdparty/python-graph/examples/write.py Wed Nov 26 23:56:19 2008 +0000 @@ -0,0 +1,35 @@ +#!/usr/bin/env python + +# Copyright (c) 2007-2008 Pedro Matiello +# License: MIT (see COPYING file) + +import sys +sys.path.append('..') +sys.path.append('/usr/lib/graphviz/python/') +import graph +import gv + +# Graph creation +gr = graph.graph() + +# Add nodes and edges +gr.add_nodes(["Portugal","Spain","France","Germany","Belgium","Netherlands","Italy"]) +gr.add_node("England") +gr.add_node("Ireland") +gr.add_node("Scotland") +gr.add_node("Wales") + +gr.add_edge("Portugal", "Spain") +gr.add_edge("Spain","France") +gr.add_edge("France","Belgium") +gr.add_edge("France","Germany") +gr.add_edge("France","Italy",) +gr.add_edge("Belgium","Netherlands") +gr.add_edge("Germany","Belgium") +gr.add_edge("Germany","Netherlands") +gr.add_edge("England","Wales") +gr.add_edge("England","Scotland") +gr.add_edge("Scotland","Wales") + +# Print to DOT Language +print gr.write(fmt='xml') 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 diff -r 01f8c7aabb7e -r 06c2228e39cb thirdparty/python-graph/graph/accessibility.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/thirdparty/python-graph/graph/accessibility.py Wed Nov 26 23:56:19 2008 +0000 @@ -0,0 +1,228 @@ +# Copyright (c) 2007-2008 Pedro Matiello +# +# Permission is hereby granted, free of charge, to any person +# obtaining a copy of this software and associated documentation +# files (the "Software"), to deal in the Software without +# restriction, including without limitation the rights to use, +# copy, modify, merge, publish, distribute, sublicense, and/or sell +# copies of the Software, and to permit persons to whom the +# Software is furnished to do so, subject to the following +# conditions: + +# The above copyright notice and this permission notice shall be +# included in all copies or substantial portions of the Software. + +# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES +# OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND +# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT +# HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, +# WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR +# OTHER DEALINGS IN THE SOFTWARE. + + +""" +Accessibility algorithms for python-graph. + +@sort: accessibility, connected_components, cut_edges, cut_nodes, mutual_accessibility +""" + + +# Transitive-closure + +def accessibility(graph): + """ + Accessibility matrix (transitive closure). + + @type graph: graph + @param graph: Graph. + + @rtype: dictionary + @return: Accessibility information for each node. + """ + accessibility = {} # Accessibility matrix + + # For each node i, mark each node j if that exists a path from i to j. + for each in graph: + access = {} + # Perform DFS to explore all reachable nodes + _dfs(graph, access, 1, each) + accessibility[each] = access.keys() + return accessibility + + +# Strongly connected components + +def mutual_accessibility(graph): + """ + Mutual-accessibility matrix (strongly connected components). + + @type graph: graph + @param graph: Graph. + + @rtype: dictionary + @return: Mutual-accessibility information for each node. + """ + mutual_access = {} + access = graph.accessibility() + + for i in graph: + mutual_access[i] = [] + for j in graph: + if (i in access[j] and j in access[i]): + mutual_access[i].append(j) + + return mutual_access + + +# Connected components + +def connected_components(graph): + """ + Connected components. + + @attention: Indentification of connected components is meaningful only for non-directed graphs. + + @type graph: graph + @param graph: Graph. + + @rtype: dictionary + @return: Pairing that associates each node to its connected component. + """ + visited = {} + count = 1 + + # For 'each' node not found to belong to a connected component, find its connected component. + for each in graph: + if (each not in visited): + _dfs(graph, visited, count, each) + count = count + 1 + + return visited + + +# Limited DFS implementations used by algorithms here + +def _dfs(graph, visited, count, node): + """ + Depht-first search subfunction adapted for accessibility algorithms. + + @type graph: graph + @param graph: Graph. + + @type visited: dictionary + @param visited: List of nodes (visited nodes are marked non-zero). + + @type count: number + @param count: Counter of connected components. + + @type node: number + @param node: Node to be explored by DFS. + """ + visited[node] = count + # Explore recursively the connected component + for each in graph[node]: + if (each not in visited): + _dfs(graph, visited, count, each) + + +# Cut-Edge and Cut-Vertex identification + +def cut_edges(graph): + """ + Return the cut-edges of the given graph. + + @rtype: list + @return: List of cut-edges. + """ + pre = {} + low = {} + spanning_tree = {} + reply = [] + pre[None] = 0 + + for each in graph: + if (not pre.has_key(each)): + spanning_tree[each] = None + _cut_dfs(graph, spanning_tree, pre, low, reply, each) + return reply + + +def cut_nodes(graph): + """ + Return the cut-nodes of the given graph. + + @rtype: list + @return: List of cut-nodes. + """ + pre = {} # Pre-ordering + low = {} # Lowest pre[] reachable from this node going down the spanning tree + one backedge + reply = {} + spanning_tree = {} + pre[None] = 0 + + # Create spanning trees, calculate pre[], low[] + for each in graph: + if (not pre.has_key(each)): + spanning_tree[each] = None + _cut_dfs(graph, spanning_tree, pre, low, [], each) + + # Find cuts + for each in graph: + # If node is not a root + if (spanning_tree[each] is not None): + for other in graph[each]: + # If there is no back-edge from descendent to a ancestral of each + if (low[other] >= pre[each] and spanning_tree[other] == each): + reply[each] = 1 + # If node is a root + else: + children = 0 + for other in graph: + if (spanning_tree[other] == each): + children = children + 1 + # root is cut-vertex iff it has two or more children + if (children >= 2): + reply[each] = 1 + + return reply.keys() + + +def _cut_dfs(graph, spanning_tree, pre, low, reply, node): + """ + Depth first search adapted for identification of cut-edges and cut-nodes. + + @type graph: graph + @param graph: Graph + + @type spanning_tree: dictionary + @param spanning_tree: Spanning tree being built for the graph by DFS. + + @type pre: dictionary + @param pre: Graph's preordering. + + @type low: dictionary + @param low: Associates to each node, the preordering index of the node of lowest preordering + accessible from the given node. + + @type reply: list + @param reply: List of cut-edges. + + @type node: node + @param node: Node to be explored by DFS. + """ + pre[node] = pre[None] + low[node] = pre[None] + pre[None] = pre[None] + 1 + + for each in graph[node]: + if (not pre.has_key(each)): + spanning_tree[each] = node + _cut_dfs(graph, spanning_tree, pre, low, reply, each) + if (low[node] > low[each]): + low[node] = low[each] + if (low[each] == pre[each]): + reply.append((node, each)) + elif (low[node] > pre[each] and spanning_tree[node] != each): + low[node] = pre[each] diff -r 01f8c7aabb7e -r 06c2228e39cb thirdparty/python-graph/graph/generators.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/thirdparty/python-graph/graph/generators.py Wed Nov 26 23:56:19 2008 +0000 @@ -0,0 +1,82 @@ +# Copyright (c) 2007-2008 Pedro Matiello +# 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. + + +""" +Random graph generators for python-graph. + +@sort: generate +""" + + +# Imports +import graph as classes +from random import randint + + +# Generator + +def generate(graph, num_nodes, num_edges, weight_range=(1, 1)): + """ + Add nodes and random edges to the graph. + + @type graph: graph + @param graph: 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). + """ + # Discover if graph is directed or not + directed = (type(graph) == classes.digraph) + + # Nodes first + nodes = xrange(num_nodes) + graph.add_nodes(nodes) + + # Build a list of all possible edges + edges = [] + edges_append = edges.append + for x in nodes: + for y in nodes: + if ((directed and x != y) or (x > y)): + edges_append((x, y)) + + # Randomize the list + for i in xrange(len(edges)): + r = randint(0, len(edges)-1) + edges[i], edges[r] = edges[r], edges[i] + + # Add edges to the graph + min_wt = min(weight_range) + max_wt = max(weight_range) + for i in xrange(num_edges): + each = edges[i] + graph.add_edge(each[0], each[1], wt = randint(min_wt, max_wt)) diff -r 01f8c7aabb7e -r 06c2228e39cb thirdparty/python-graph/graph/minmax.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/thirdparty/python-graph/graph/minmax.py Wed Nov 26 23:56:19 2008 +0000 @@ -0,0 +1,168 @@ +# Copyright (c) 2007-2008 Pedro Matiello +# Rhys Ulerich +# +# 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. + + +""" +Minimization and maximization algorithms for python-graph. + +@sort: minimal_spanning_tree, shortest_path, _first_unvisited, _lightest_edge +""" + + +# Minimal spanning tree + +def minimal_spanning_tree(graph, root=None): + """ + Minimal spanning tree. + + @attention: Minimal spanning tree meaningful only for weighted graphs. + + @type graph: graph + @param graph: Graph. + + @type root: node + @param root: Optional root node (will explore only root's connected component) + + @rtype: dictionary + @return: Generated spanning tree. + """ + visited = [] # List for marking visited and non-visited nodes + spanning_tree = {} # MInimal Spanning tree + + # Initialization + if (root is not None): + visited.append(root) + nroot = root + spanning_tree[root] = None + else: + nroot = 1 + + # Algorithm loop + while (nroot is not None): + ledge = _lightest_edge(graph, visited) + if (ledge == (-1, -1)): + if (root is not None): + break + nroot = _first_unvisited(graph, visited) + if (nroot is not None): + spanning_tree[nroot] = None + visited.append(nroot) + else: + spanning_tree[ledge[1]] = ledge[0] + visited.append(ledge[1]) + + return spanning_tree + + +def _first_unvisited(graph, visited): + """ + Return first unvisited node. + + @type graph: graph + @param graph: Graph. + + @type visited: list + @param visited: List of nodes. + + @rtype: node + @return: First unvisited node. + """ + for each in graph: + if (each not in visited): + return each + return None + + +def _lightest_edge(graph, visited): + """ + Return the lightest edge in graph going from a visited node to an unvisited one. + + @type graph: graph + @param graph: Graph. + + @type visited: list + @param visited: List of nodes. + + @rtype: tuple + @return: Lightest edge in graph going from a visited node to an unvisited one. + """ + lightest_edge = (-1, -1) + weight = -1 + for each in visited: + for other in graph[each]: + if (other not in visited): + w = graph.get_edge_weight(each, other) + if (w < weight or weight < 0): + lightest_edge = (each, other) + weight = w + return lightest_edge + + +# Shortest Path +# Code donated by Rhys Ulerich + +def shortest_path(graph, source): + """ + Return the shortest path distance between source and all other nodes using Dijkstra's algorithm. + + @attention: All weights must be nonnegative. + + @type graph: graph + @param graph: Graph. + + @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. + """ + # Initialization + dist = { source: 0 } + previous = { source: None} + q = graph.nodes() + + # Algorithm loop + while q: + # examine_min process performed using O(nodes) pass here. + # May be improved using another examine_min data structure. + u = q[0] + for node in q[1:]: + if ((not dist.has_key(u)) + or (dist.has_key(node) and dist[node] < dist[u])): + u = node + q.remove(u) + + # Process reachable, remaining nodes from u + if (dist.has_key(u)): + for v in graph[u]: + if v in q: + alt = dist[u] + graph.get_edge_weight(u, v) + if (not dist.has_key(v)) or (alt < dist[v]): + dist[v] = alt + previous[v] = u + + return previous, dist diff -r 01f8c7aabb7e -r 06c2228e39cb thirdparty/python-graph/graph/readwrite.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/thirdparty/python-graph/graph/readwrite.py Wed Nov 26 23:56:19 2008 +0000 @@ -0,0 +1,302 @@ +# Copyright (c) 2007-2008 Pedro Matiello +# +# Permission is hereby granted, free of charge, to any person +# obtaining a copy of this software and associated documentation +# files (the "Software"), to deal in the Software without +# restriction, including without limitation the rights to use, +# copy, modify, merge, publish, distribute, sublicense, and/or sell +# copies of the Software, and to permit persons to whom the +# Software is furnished to do so, subject to the following +# conditions: + +# The above copyright notice and this permission notice shall be +# included in all copies or substantial portions of the Software. + +# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES +# OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND +# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT +# HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, +# WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR +# OTHER DEALINGS IN THE SOFTWARE. + + +""" +Functions for reading and writing graphs. + +@sort: read_xml, write_xml, write_dot_graph, write_dot_digraph, write_dot_hypergraph +""" + + +# Imports +from xml.dom.minidom import Document, parseString + + +# Values +colors = ['aquamarine4', 'blue4', 'brown4', 'cornflowerblue', 'cyan4', + 'darkgreen', 'darkorange3', 'darkorchid4', 'darkseagreen4', 'darkslategray', + 'deeppink4', 'deepskyblue4', 'firebrick3', 'hotpink3', 'indianred3', + 'indigo', 'lightblue4', 'lightseagreen', 'lightskyblue4', 'magenta4', + 'maroon', 'palevioletred3', 'steelblue', 'violetred3'] + + +# XML + +def write_xml(graph): + """ + Return a string specifying the given graph as a XML document. + + @type graph: graph + @param graph: Graph. + + @rtype: string + @return: String specifying the graph as a XML document. + """ + + # Document root + grxml = Document() + grxmlr = grxml.createElement('graph') + grxml.appendChild(grxmlr) + + # Each node... + for each_node in graph.nodes(): + node = grxml.createElement('node') + node.setAttribute('id',str(each_node)) + grxmlr.appendChild(node) + for each_attr in graph.get_node_attributes(each_node): + attr = grxml.createElement('attribute') + attr.setAttribute('attr', each_attr[0]) + attr.setAttribute('value', each_attr[1]) + node.appendChild(attr) + + # Each edge... + for edge_from, edge_to in graph.edges(): + edge = grxml.createElement('edge') + edge.setAttribute('from',str(edge_from)) + edge.setAttribute('to',str(edge_to)) + edge.setAttribute('wt',str(graph.get_edge_weight(edge_from, edge_to))) + edge.setAttribute('label',str(graph.get_edge_label(edge_from, edge_to))) + grxmlr.appendChild(edge) + for attr_name, attr_value in graph.get_edge_attributes(edge_from, edge_to): + attr = grxml.createElement('attribute') + attr.setAttribute('attr', attr_name) + attr.setAttribute('value', attr_value) + edge.appendChild(attr) + + return grxml.toprettyxml() + + +def write_xml_hypergraph(hypergraph): + """ + Return a string specifying the given hypergraph as a XML document. + + @type hypergraph: hypergraph + @param hypergraph: Hypergraph. + + @rtype: string + @return: String specifying the graph as a XML document. + """ + + # Document root + grxml = Document() + grxmlr = grxml.createElement('hypergraph') + grxml.appendChild(grxmlr) + + # Each node... + nodes = hypergraph.nodes() + hyperedges = hypergraph.get_hyperedges() + for each_node in (nodes + hyperedges): + if (each_node in nodes): + node = grxml.createElement('node') + else: + node = grxml.createElement('hyperedge') + node.setAttribute('id',str(each_node)) + grxmlr.appendChild(node) + + # and its outgoing edge + for each_edge in hypergraph.get_links(each_node): + edge = grxml.createElement('link') + edge.setAttribute('to',str(each_edge)) + node.appendChild(edge) + + return grxml.toprettyxml() + + +def read_xml(graph, string): + """ + Read a graph from a XML document. Nodes and edges specified in the input will be added to the current graph. + + @type graph: graph + @param graph: Graph + + @type string: string + @param string: Input string in XML format specifying a graph. + """ + dom = parseString(string) + + # Read nodes... + for each_node in dom.getElementsByTagName("node"): + graph.add_node(each_node.getAttribute('id')) + for each_attr in each_node.getElementsByTagName("attribute"): + graph.add_node_attribute(each_node.getAttribute('id'), (each_attr.getAttribute('attr'), + each_attr.getAttribute('value'))) + + # Read edges... + for each_edge in dom.getElementsByTagName("edge"): + graph.add_edge(each_edge.getAttribute('from'), each_edge.getAttribute('to'), \ + wt=float(each_edge.getAttribute('wt')), label=each_edge.getAttribute('label')) + for each_attr in each_edge.getElementsByTagName("attribute"): + attr_tuple = (each_attr.getAttribute('attr'), each_attr.getAttribute('value')) + if (attr_tuple not in graph.get_edge_attributes(each_edge.getAttribute('from'), \ + each_edge.getAttribute('to'))): + graph.add_edge_attribute(each_edge.getAttribute('from'), \ + each_edge.getAttribute('to'), attr_tuple) + + +def read_xml_hypergraph(hypergraph, string): + """ + Read a graph from a XML document. Nodes and hyperedges specified in the input will be added to the current graph. + + @type hypergraph: hypergraph + @param hypergraph: Hypergraph + + @type string: string + @param string: Input string in XML format specifying a graph. + """ + dom = parseString(string) + for each_node in dom.getElementsByTagName("node"): + hypergraph.add_nodes(each_node.getAttribute('id')) + for each_node in dom.getElementsByTagName("hyperedge"): + hypergraph.add_hyperedges(each_node.getAttribute('id')) + dom = parseString(string) + for each_node in dom.getElementsByTagName("node"): + for each_edge in each_node.getElementsByTagName("link"): + hypergraph.link(each_node.getAttribute('id'), each_edge.getAttribute('to')) + + +# DOT Language + +def _dot_node_str(graph, node, wt): + line = '\t"%s" [ ' % str(node) + attrlist = graph.get_node_attributes(node) + for each in attrlist: + attr = '%s="%s" ' % (each[0], each[1]) + line = line + attr + line = line + ']\n' + return line + + +def _dot_edge_str(graph, u, v, wt): + line = '\t"%s" -- "%s" [ ' % (str(u), str(v)) + attrlist = graph.get_edge_attributes(u, v) + [('label',graph.get_edge_label(u, v))] + for each in attrlist: + attr = '%s="%s" ' % (each[0], each[1]) + line = line + attr + line = line + ']\n' + return line + + +def _dot_arrow_str(graph, u, v, wt): + line = '\t"%s" -> "%s" [ ' % (str(u), str(v)) + attrlist = graph.get_edge_attributes(u, v) + [('label',graph.get_edge_label(u, v))] + for each in attrlist: + attr = '%s="%s" ' % (each[0], each[1]) + line = line + attr + line = line + ']\n' + return line + + +def write_dot_graph(graph, wt): + """ + Return a string specifying the given graph in DOT Language. + + @type graph: graph + @param graph: Graph. + + @type wt: boolean + @param wt: Whether edges should be labelled with its weight. + + @rtype: string + @return: String specifying the graph in DOT Language. + """ + doc = 'graph graphname \n{\n' + for node in graph: + doc = doc + _dot_node_str(graph, node, wt) + for edge in graph[node]: + if (node >= edge): + doc = doc + _dot_edge_str(graph, node, edge, wt) + doc = doc + '}' + return doc + + +def write_dot_digraph(graph, wt): + """ + Return a string specifying the given digraph in DOT Language. + + @type graph: graph + @param graph: Graph. + + @type wt: boolean + @param wt: Whether arrows should be labelled with its weight. + + @rtype: string + @return: String specifying the graph in DOT Language. + """ + doc = 'digraph graphname \n{\n' + for node in graph: + doc = doc + _dot_node_str(graph, node, wt) + for edge in graph[node]: + doc = doc + _dot_arrow_str(graph, node, edge, wt) + doc = doc + '}' + return doc + + +def write_dot_hypergraph(hypergraph, coloured=False): + """ + Return a string specifying the given hypergraph in DOT Language. + + @type hypergraph: hypergraph + @param hypergraph: Hypergraph. + + @type coloured: boolean + @param coloured: Whether hyperedges should be coloured. + + @rtype: string + @return: String specifying the hypergraph in DOT Language. + """ + # Start document + doc = "" + doc = doc + "graph graphname" + "\n{\n" + colortable = {} + colorcount = 0 + + + # Add hyperedges + color = '' + for each_hyperedge in hypergraph.hyperedges(): + colortable[each_hyperedge] = colors[colorcount % len(colors)] + colorcount = colorcount + 1 + if (coloured): + color = " color=%s" % colortable[each_hyperedge] + vars = { + 'hyperedge' : str(each_hyperedge), + 'color' : color + } + doc = doc + '\t"%(hyperedge)s" [shape=point %(color)s]\n' % vars + + color = "\n" + # Add nodes and links + for each_node in hypergraph.nodes(): + doc = doc + "\t\"%s\"\n" % str(each_node) + for each_link in hypergraph.links(each_node): + if (coloured): + color = " [color=%s]\n" % colortable[each_link] + linkvars = { + 'node' : str(each_node), + 'hyperedge' : str(each_link) + } + doc = doc + '\t %(node)s -- %(hyperedge)s' % linkvars + color + + doc = doc + "}" + return doc diff -r 01f8c7aabb7e -r 06c2228e39cb thirdparty/python-graph/graph/searching.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/thirdparty/python-graph/graph/searching.py Wed Nov 26 23:56:19 2008 +0000 @@ -0,0 +1,167 @@ +# Copyright (c) 2007-2008 Pedro Matiello +# +# Permission is hereby granted, free of charge, to any person +# obtaining a copy of this software and associated documentation +# files (the "Software"), to deal in the Software without +# restriction, including without limitation the rights to use, +# copy, modify, merge, publish, distribute, sublicense, and/or sell +# copies of the Software, and to permit persons to whom the +# Software is furnished to do so, subject to the following +# conditions: + +# The above copyright notice and this permission notice shall be +# included in all copies or substantial portions of the Software. + +# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES +# OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND +# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT +# HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, +# WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR +# OTHER DEALINGS IN THE SOFTWARE. + + +""" +Search algorithms for python-graph. + +@sort: breadth_first_search, depth_first_search, _bfs, _dfs +""" + + +# Depth-first search + +def depth_first_search(graph, root=None): + """ + Depth-first search. + + @type graph: graph + @param graph: Graph. + + @type root: node + @param root: Optional root node (will explore only root's connected component) + + @rtype: tuple + @return: A tupple containing a dictionary and two lists: + 1. Generated spanning tree + 2. Graph's preordering + 3. Graph's postordering + """ + visited = {} # List for marking visited and non-visited nodes + spanning_tree = {} # Spanning tree + pre = [] # Graph's preordering + post = [] # Graph's postordering + + # DFS from one node only + if (root is not None): + spanning_tree[root] = None + _dfs(graph, visited, spanning_tree, pre, post, root) + return spanning_tree, pre, post + + # Algorithm loop + for each in graph: + # Select a non-visited node + if (each not in visited): + spanning_tree[each] = None + # Explore node's connected component + _dfs(graph, visited, spanning_tree, pre, post, each) + + return spanning_tree, pre, post + + +def _dfs(graph, visited, spanning_tree, pre, post, node): + """ + Depht-first search subfunction. + + @type graph: graph + @param graph: Graph. + + @type visited: dictionary + @param visited: List of nodes (visited nodes are marked non-zero). + + @type spanning_tree: dictionary + @param spanning_tree: Spanning tree being built for the graph by DFS. + + @type pre: list + @param pre: Graph's preordering. + + @type post: list + @param post: Graph's postordering. + + @type node: node + @param node: Node to be explored by DFS. + """ + visited[node] = 1 + pre.append(node) + # Explore recursively the connected component + for each in graph[node]: + if (each not in visited): + spanning_tree[each] = node + _dfs(graph, visited, spanning_tree, pre, post, each) + post.append(node) + + +# Breadth-first search + +def breadth_first_search(graph, root=None): + """ + Breadth-first search. + + @type graph: graph + @param graph: Graph. + + @type root: node + @param root: Optional root node (will explore only root's connected component) + + @rtype: tuple + @return: A tuple containing a dictionary and a list. + 1. Generated spanning tree + 2. Graph's level-based ordering + """ + queue = [] # Visiting queue + spanning_tree = {} # Spanning tree + ordering = [] + + # BFS from one node only + if (root is not None): + queue.append(root) + ordering.append(root) + spanning_tree[root] = None + _bfs(graph, queue, spanning_tree, ordering) + return spanning_tree, ordering + + # Algorithm + for each in graph: + if (each not in spanning_tree): + queue.append(each) + ordering.append(root) + spanning_tree[each] = None + _bfs(graph, queue, spanning_tree, ordering) + + return spanning_tree, ordering[1:] + + +def _bfs(graph, queue, spanning_tree, ordering): + """ + Breadth-first search subfunction. + + @type graph: graph + @param graph: Graph. + + @type spanning_tree: dictionary + @param spanning_tree: Spanning tree being built for the graph by DFS. + + @type ordering: list + @param ordering: Graph's level-based ordering. + + @type queue: list + @param queue: Nodes to be visited (ordered). + """ + while (queue != []): + node = queue.pop(0) + + for other in graph[node]: + if (other not in spanning_tree): + queue.append(other) + ordering.append(other) + spanning_tree[other] = node diff -r 01f8c7aabb7e -r 06c2228e39cb thirdparty/python-graph/graph/sorting.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/thirdparty/python-graph/graph/sorting.py Wed Nov 26 23:56:19 2008 +0000 @@ -0,0 +1,49 @@ +# Copyright (c) 2007-2008 Pedro Matiello +# +# Permission is hereby granted, free of charge, to any person +# obtaining a copy of this software and associated documentation +# files (the "Software"), to deal in the Software without +# restriction, including without limitation the rights to use, +# copy, modify, merge, publish, distribute, sublicense, and/or sell +# copies of the Software, and to permit persons to whom the +# Software is furnished to do so, subject to the following +# conditions: + +# The above copyright notice and this permission notice shall be +# included in all copies or substantial portions of the Software. + +# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES +# OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND +# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT +# HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, +# WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR +# OTHER DEALINGS IN THE SOFTWARE. + + +""" +Sorting algorithms for python-graph. + +@sort: topological_sorting +""" + + +# Topological sorting + +def topological_sorting(graph): + """ + Topological sorting. + + @attention: Topological sorting is meaningful only for directed acyclic graphs. + + @type graph: graph + @param graph: Graph. + + @rtype: list + @return: Topological sorting for the graph. + """ + # The topological sorting of a DAG is equivalent to its reverse postordering. + tmp, tmp, post = graph.depth_first_search() + post.reverse() + return post diff -r 01f8c7aabb7e -r 06c2228e39cb thirdparty/python-graph/graph/traversal.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/thirdparty/python-graph/graph/traversal.py Wed Nov 26 23:56:19 2008 +0000 @@ -0,0 +1,81 @@ +# Copyright (c) 2007-2008 Pedro Matiello +# +# Permission is hereby granted, free of charge, to any person +# obtaining a copy of this software and associated documentation +# files (the "Software"), to deal in the Software without +# restriction, including without limitation the rights to use, +# copy, modify, merge, publish, distribute, sublicense, and/or sell +# copies of the Software, and to permit persons to whom the +# Software is furnished to do so, subject to the following +# conditions: + +# The above copyright notice and this permission notice shall be +# included in all copies or substantial portions of the Software. + +# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES +# OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND +# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT +# HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, +# WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR +# OTHER DEALINGS IN THE SOFTWARE. + + +""" +Traversal algorithms for python-graph. + +@sort: traversal +""" + + +# Minimal spanning tree + +def traversal(graph, node, order): + """ + 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. + """ + visited = {} + if (order == 'pre'): + pre = 1 + post = 0 + elif (order == 'post'): + pre = 0 + post = 1 + + for each in _dfs(graph, visited, node, pre, post): + yield each + + +def _dfs(graph, visited, node, pre, post): + """ + Depht-first search subfunction for traversals. + + @type graph: graph + @param graph: Graph. + + @type visited: dictionary + @param visited: List of nodes (visited nodes are marked non-zero). + + @type node: node + @param node: Node to be explored by DFS. + """ + visited[node] = 1 + if (pre): yield node + # Explore recursively the connected component + for each in graph[node]: + if (each not in visited): + for other in _dfs(graph, visited, each, pre, post): + yield other + if (post): yield node diff -r 01f8c7aabb7e -r 06c2228e39cb thirdparty/python-graph/misc/epydoc.css --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/thirdparty/python-graph/misc/epydoc.css Wed Nov 26 23:56:19 2008 +0000 @@ -0,0 +1,322 @@ + + +/* Epydoc CSS Stylesheet + * + * This stylesheet can be used to customize the appearance of epydoc's + * HTML output. + * + */ + +/* Default Colors & Styles + * - Set the default foreground & background color with 'body'; and + * link colors with 'a:link' and 'a:visited'. + * - Use bold for decision list terms. + * - The heading styles defined here are used for headings *within* + * docstring descriptions. All headings used by epydoc itself use + * either class='epydoc' or class='toc' (CSS styles for both + * defined below). + */ +body { background: #ffffff; color: #000000; } +p { margin-top: 0.5em; margin-bottom: 0.5em; } +a:link { color: #0000ff; } +a:visited { color: #204080; } +dt { font-weight: bold; } +h1 { font-size: +140%; font-style: italic; + font-weight: bold; } +h2 { font-size: +125%; font-style: italic; + font-weight: bold; } +h3 { font-size: +110%; + font-weight: normal; } +code { font-size: 100%; } +/* N.B.: class, not pseudoclass */ +a.link { font-family: monospace; } + +/* Page Header & Footer + * - The standard page header consists of a navigation bar (with + * pointers to standard pages such as 'home' and 'trees'); a + * breadcrumbs list, which can be used to navigate to containing + * classes or modules; options links, to show/hide private + * variables and to show/hide frames; and a page title (using + *

). The page title may be followed by a link to the + * corresponding source code (using 'span.codelink'). + * - The footer consists of a navigation bar, a timestamp, and a + * pointer to epydoc's homepage. + */ +h1.epydoc { margin: 0; font-size: +140%; font-weight: bold; } +h2.epydoc { font-size: +130%; font-weight: bold; } +h3.epydoc { font-size: +115%; font-weight: bold; + margin-top: 0.2em; } +td h3.epydoc { font-size: +115%; font-weight: bold; + margin-bottom: 0; } +table.navbar { background: #a0c0ff; color: #000000; + border: 2px groove #c0d0d0; } +table.navbar table { color: #000000; } +th.navbar-select { background: #70b0ff; + color: #000000; } +table.navbar a { text-decoration: none; } +table.navbar a:link { color: #0000ff; } +table.navbar a:visited { color: #204080; } +span.breadcrumbs { font-size: 85%; font-weight: bold; } +span.options { font-size: 70%; } +span.codelink { font-size: 85%; } +td.footer { font-size: 85%; } + +/* Table Headers + * - Each summary table and details section begins with a 'header' + * row. This row contains a section title (marked by + * 'span.table-header') as well as a show/hide private link + * (marked by 'span.options', defined above). + * - Summary tables that contain user-defined groups mark those + * groups using 'group header' rows. + */ +td.table-header { background: #70b0ff; color: #000000; + border: 1px solid #608090; } +td.table-header table { color: #000000; } +td.table-header table a:link { color: #0000ff; } +td.table-header table a:visited { color: #204080; } +span.table-header { font-size: 120%; font-weight: bold; } +th.group-header { background: #c0e0f8; color: #000000; + text-align: left; font-style: italic; + font-size: 115%; + border: 1px solid #608090; } + +/* Summary Tables (functions, variables, etc) + * - Each object is described by a single row of the table with + * two cells. The left cell gives the object's type, and is + * marked with 'code.summary-type'. The right cell gives the + * object's name and a summary description. + * - CSS styles for the table's header and group headers are + * defined above, under 'Table Headers' + */ +table.summary { border-collapse: collapse; + background: #e8f0f8; color: #000000; + border: 1px solid #608090; + margin-bottom: 0.5em; } +td.summary { border: 1px solid #608090; } +code.summary-type { font-size: 85%; } +table.summary a:link { color: #0000ff; } +table.summary a:visited { color: #204080; } + + +/* Details Tables (functions, variables, etc) + * - Each object is described in its own div. + * - A single-row summary table w/ table-header is used as + * a header for each details section (CSS style for table-header + * is defined above, under 'Table Headers'). + */ +table.details { border-collapse: collapse; + background: #e8f0f8; color: #000000; + border: 1px solid #608090; + margin: .2em 0 0 0; } +table.details table { color: #000000; } +table.details a:link { color: #0000ff; } +table.details a:visited { color: #204080; } + +/* Fields */ +dl.fields { margin-left: 2em; margin-top: 1em; + margin-bottom: 1em; } +dl.fields dd ul { margin-left: 0em; padding-left: 0em; } +dl.fields dd ul li ul { margin-left: 2em; padding-left: 0em; } +div.fields { margin-left: 2em; } +div.fields p { margin-bottom: 0.5em; } + +/* Index tables (identifier index, term index, etc) + * - link-index is used for indices containing lists of links + * (namely, the identifier index & term index). + * - index-where is used in link indices for the text indicating + * the container/source for each link. + * - metadata-index is used for indices containing metadata + * extracted from fields (namely, the bug index & todo index). + */ +table.link-index { border-collapse: collapse; + background: #e8f0f8; color: #000000; + border: 1px solid #608090; } +td.link-index { border-width: 0px; } +table.link-index a:link { color: #0000ff; } +table.link-index a:visited { color: #204080; } +span.index-where { font-size: 70%; } +table.metadata-index { border-collapse: collapse; + background: #e8f0f8; color: #000000; + border: 1px solid #608090; + margin: .2em 0 0 0; } +td.metadata-index { border-width: 1px; border-style: solid; } +table.metadata-index a:link { color: #0000ff; } +table.metadata-index a:visited { color: #204080; } + +/* Function signatures + * - sig* is used for the signature in the details section. + * - .summary-sig* is used for the signature in the summary + * table, and when listing property accessor functions. + * */ +.sig-name { color: #006080; } +.sig-arg { color: #008060; } +.sig-default { color: #602000; } +.summary-sig { font-family: monospace; } +.summary-sig-name { color: #006080; font-weight: bold; } +table.summary a.summary-sig-name:link + { color: #006080; font-weight: bold; } +table.summary a.summary-sig-name:visited + { color: #006080; font-weight: bold; } +.summary-sig-arg { color: #006040; } +.summary-sig-default { color: #501800; } + +/* Subclass list + */ +ul.subclass-list { display: inline; } +ul.subclass-list li { display: inline; } + +/* To render variables, classes etc. like functions */ +table.summary .summary-name { color: #006080; font-weight: bold; + font-family: monospace; } +table.summary + a.summary-name:link { color: #006080; font-weight: bold; + font-family: monospace; } +table.summary + a.summary-name:visited { color: #006080; font-weight: bold; + font-family: monospace; } + +/* Variable values + * - In the 'variable details' sections, each varaible's value is + * listed in a 'pre.variable' box. The width of this box is + * restricted to 80 chars; if the value's repr is longer than + * this it will be wrapped, using a backslash marked with + * class 'variable-linewrap'. If the value's repr is longer + * than 3 lines, the rest will be ellided; and an ellipsis + * marker ('...' marked with 'variable-ellipsis') will be used. + * - If the value is a string, its quote marks will be marked + * with 'variable-quote'. + * - If the variable is a regexp, it is syntax-highlighted using + * the re* CSS classes. + */ +pre.variable { padding: .5em; margin: 0; + background: #dce4ec; color: #000000; + border: 1px solid #708890; } +.variable-linewrap { color: #604000; font-weight: bold; } +.variable-ellipsis { color: #604000; font-weight: bold; } +.variable-quote { color: #604000; font-weight: bold; } +.variable-group { color: #008000; font-weight: bold; } +.variable-op { color: #604000; font-weight: bold; } +.variable-string { color: #006030; } +.variable-unknown { color: #a00000; font-weight: bold; } +.re { color: #000000; } +.re-char { color: #006030; } +.re-op { color: #600000; } +.re-group { color: #003060; } +.re-ref { color: #404040; } + +/* Base tree + * - Used by class pages to display the base class hierarchy. + */ +pre.base-tree { font-size: 80%; margin: 0; } + +/* Frames-based table of contents headers + * - Consists of two frames: one for selecting modules; and + * the other listing the contents of the selected module. + * - h1.toc is used for each frame's heading + * - h2.toc is used for subheadings within each frame. + */ +h1.toc { text-align: center; font-size: 105%; + margin: 0; font-weight: bold; + padding: 0; } +h2.toc { font-size: 100%; font-weight: bold; + margin: 0.5em 0 0 -0.3em; } + +/* Syntax Highlighting for Source Code + * - doctest examples are displayed in a 'pre.py-doctest' block. + * If the example is in a details table entry, then it will use + * the colors specified by the 'table pre.py-doctest' line. + * - Source code listings are displayed in a 'pre.py-src' block. + * Each line is marked with 'span.py-line' (used to draw a line + * down the left margin, separating the code from the line + * numbers). Line numbers are displayed with 'span.py-lineno'. + * The expand/collapse block toggle button is displayed with + * 'a.py-toggle' (Note: the CSS style for 'a.py-toggle' should not + * modify the font size of the text.) + * - If a source code page is opened with an anchor, then the + * corresponding code block will be highlighted. The code + * block's header is highlighted with 'py-highlight-hdr'; and + * the code block's body is highlighted with 'py-highlight'. + * - The remaining py-* classes are used to perform syntax + * highlighting (py-string for string literals, py-name for names, + * etc.) + */ +pre.py-doctest { padding: .5em; margin: 1em; + background: #e8f0f8; color: #000000; + border: 1px solid #708890; } +table pre.py-doctest { background: #dce4ec; + color: #000000; } +pre.py-src { border: 2px solid #000000; + background: #f0f0f0; color: #000000; } +.py-line { border-left: 2px solid #000000; + margin-left: .2em; padding-left: .4em; } +.py-lineno { font-style: italic; font-size: 90%; + padding-left: .5em; } +a.py-toggle { text-decoration: none; } +div.py-highlight-hdr { border-top: 2px solid #000000; + border-bottom: 2px solid #000000; + background: #d8e8e8; } +div.py-highlight { border-bottom: 2px solid #000000; + background: #d0e0e0; } +.py-prompt { color: #005050; font-weight: bold;} +.py-more { color: #005050; font-weight: bold;} +.py-string { color: #006030; } +.py-comment { color: #003060; } +.py-keyword { color: #600000; } +.py-output { color: #404040; } +.py-name { color: #000050; } +.py-name:link { color: #000050 !important; } +.py-name:visited { color: #000050 !important; } +.py-number { color: #005000; } +.py-defname { color: #000060; font-weight: bold; } +.py-def-name { color: #000060; font-weight: bold; } +.py-base-class { color: #000060; } +.py-param { color: #000060; } +.py-docstring { color: #006030; } +.py-decorator { color: #804020; } +/* Use this if you don't want links to names underlined: */ +/*a.py-name { text-decoration: none; }*/ + +/* Graphs & Diagrams + * - These CSS styles are used for graphs & diagrams generated using + * Graphviz dot. 'img.graph-without-title' is used for bare + * diagrams (to remove the border created by making the image + * clickable). + */ +img.graph-without-title { border: none; } +img.graph-with-title { border: 1px solid #000000; } +span.graph-title { font-weight: bold; } +span.graph-caption { } + +/* General-purpose classes + * - 'p.indent-wrapped-lines' defines a paragraph whose first line + * is not indented, but whose subsequent lines are. + * - The 'nomargin-top' class is used to remove the top margin (e.g. + * from lists). The 'nomargin' class is used to remove both the + * top and bottom margin (but not the left or right margin -- + * for lists, that would cause the bullets to disappear.) + */ +p.indent-wrapped-lines { padding: 0 0 0 7em; text-indent: -7em; + margin: 0; } +.nomargin-top { margin-top: 0; } +.nomargin { margin-top: 0; margin-bottom: 0; } + +/* HTML Log */ +div.log-block { padding: 0; margin: .5em 0 .5em 0; + background: #e8f0f8; color: #000000; + border: 1px solid #000000; } +div.log-error { padding: .1em .3em .1em .3em; margin: 4px; + background: #ffb0b0; color: #000000; + border: 1px solid #000000; } +div.log-warning { padding: .1em .3em .1em .3em; margin: 4px; + background: #ffffb0; color: #000000; + border: 1px solid #000000; } +div.log-info { padding: .1em .3em .1em .3em; margin: 4px; + background: #b0ffb0; color: #000000; + border: 1px solid #000000; } +h2.log-hdr { background: #70b0ff; color: #000000; + margin: 0; padding: 0em 0.5em 0em 0.5em; + border-bottom: 1px solid #000000; font-size: 110%; } +p.log { font-weight: bold; margin: .5em 0 .5em 0; } +tr.opt-changed { color: #000000; font-weight: bold; } +tr.opt-default { color: #606060; } +pre.log { margin: 0; padding: 0; padding-left: 1em; } diff -r 01f8c7aabb7e -r 06c2228e39cb thirdparty/python-graph/misc/unittests-digraph.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/thirdparty/python-graph/misc/unittests-digraph.py Wed Nov 26 23:56:19 2008 +0000 @@ -0,0 +1,145 @@ +#!/usr/bin/python + +# Copyright (c) 2007-2008 Pedro Matiello +# +# Permission is hereby granted, free of charge, to any person +# obtaining a copy of this software and associated documentation +# files (the "Software"), to deal in the Software without +# restriction, including without limitation the rights to use, +# copy, modify, merge, publish, distribute, sublicense, and/or sell +# copies of the Software, and to permit persons to whom the +# Software is furnished to do so, subject to the following +# conditions: + +# The above copyright notice and this permission notice shall be +# included in all copies or substantial portions of the Software. + +# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES +# OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND +# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT +# HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, +# WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR +# OTHER DEALINGS IN THE SOFTWARE. + + +""" +python-graph + +Unit tests for python-graph +""" + + +# Imports +import sys +sys.path.append('..') +import copy +import graph +import unittest + + +# Tests +class testGraph(unittest.TestCase): + + def setUp(self): + pass + + def testRandomGraph(self): + gr = graph.digraph() + gr.generate(100, 500) + self.assertEqual(gr.nodes(),range(100)) + self.assertEqual(len(gr.edges()), 500) + for each, other in gr.edges(): + self.assertTrue(each in gr) + self.assertTrue(other in gr) + + def testRandomEmptyGraph(self): + gr = graph.digraph() + gr.generate(0,0) + self.assertTrue(gr.nodes() == []) + self.assertTrue(gr.edges() == []) + + def testNodeRemoval(self): + gr = graph.digraph() + gr.generate(10, 90) + gr.del_node(0) + self.assertTrue(0 not in gr) + for each, other in gr.edges(): + self.assertTrue(each in gr) + self.assertTrue(other in gr) + + def testGraphInverse(self): + gr = graph.digraph() + gr.generate(50, 300) + inv = gr.inverse() + for each in gr.edges(): + self.assertTrue(each not in inv.edges()) + for each in inv.edges(): + self.assertTrue(each not in gr.edges()) + + def testEmptyGraphInverse(self): + gr = graph.digraph() + inv = gr.inverse() + self.assertTrue(gr.nodes() == []) + self.assertTrue(gr.edges() == []) + + def testGraphComplete(self): + gr = graph.digraph() + gr.add_nodes(xrange(10)) + gr.complete() + for i in xrange(10): + for j in range(10): + self.assertTrue((i, j) in gr.edges() or i == j) + + def testEmptyGraphComplete(self): + gr = graph.digraph() + gr.complete() + self.assertTrue(gr.nodes() == []) + self.assertTrue(gr.edges() == []) + + def testGraphWithOneNodeComplete(self): + gr = graph.digraph() + gr.add_node(0) + gr.complete() + self.assertTrue(gr.nodes() == [0]) + self.assertTrue(gr.edges() == []) + + def testAddGraph(self): + gr1 = graph.digraph() + gr1.generate(25, 100) + gr2 = graph.digraph() + gr2.generate(40, 200) + gr1.add_graph(gr2) + for each in gr2.nodes(): + self.assertTrue(each in gr1) + for each in gr2.edges(): + self.assertTrue(each in gr1.edges()) + + def testAddEmptyGraph(self): + gr1 = graph.digraph() + gr1.generate(25, 100) + gr1c = copy.copy(gr1) + gr2 = graph.digraph() + gr1.add_graph(gr2) + self.assertTrue(gr1.nodes() == gr1c.nodes()) + self.assertTrue(gr1.edges() == gr1c.edges()) + + def testAddSpanningTree(self): + gr = graph.digraph() + st = {0: None, 1: 0, 2:0, 3: 1, 4: 2, 5: 3} + gr.add_spanning_tree(st) + for each in st: + self.assertTrue((st[each], each) in gr.edges() or (each, st[each]) == (0, None)) + + def testAddEmptySpanningTree(self): + gr = graph.digraph() + st = {} + gr.add_spanning_tree(st) + self.assertTrue(gr.nodes() == []) + self.assertTrue(gr.edges() == []) + + +# Run tests +if __name__ == '__main__': + unittest.main() diff -r 01f8c7aabb7e -r 06c2228e39cb thirdparty/python-graph/misc/unittests-graph.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/thirdparty/python-graph/misc/unittests-graph.py Wed Nov 26 23:56:19 2008 +0000 @@ -0,0 +1,146 @@ +#!/usr/bin/python + +# Copyright (c) 2007-2008 Pedro Matiello +# +# Permission is hereby granted, free of charge, to any person +# obtaining a copy of this software and associated documentation +# files (the "Software"), to deal in the Software without +# restriction, including without limitation the rights to use, +# copy, modify, merge, publish, distribute, sublicense, and/or sell +# copies of the Software, and to permit persons to whom the +# Software is furnished to do so, subject to the following +# conditions: + +# The above copyright notice and this permission notice shall be +# included in all copies or substantial portions of the Software. + +# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES +# OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND +# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT +# HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, +# WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR +# OTHER DEALINGS IN THE SOFTWARE. + + +""" +python-graph + +Unit tests for python-graph +""" + + +# Imports +import sys +sys.path.append('..') +import copy +import graph +import unittest + + +# Tests +class testGraph(unittest.TestCase): + + def setUp(self): + pass + + def testRandomGraph(self): + gr = graph.graph() + gr.generate(100, 500) + self.assertEqual(gr.nodes(),range(100)) + self.assertEqual(len(gr.edges()), 500*2) + for each, other in gr.edges(): + self.assertTrue(each in gr) + self.assertTrue(other in gr) + + def testRandomEmptyGraph(self): + gr = graph.graph() + gr.generate(0,0) + self.assertTrue(gr.nodes() == []) + self.assertTrue(gr.edges() == []) + + def testNodeRemoval(self): + gr = graph.graph() + gr.generate(10, 30) + gr.del_node(0) + self.assertTrue(0 not in gr) + for each, other in gr.edges(): + self.assertTrue(each in gr) + self.assertTrue(other in gr) + + def testGraphInverse(self): + gr = graph.graph() + gr.generate(50, 300) + inv = gr.inverse() + for each in gr.edges(): + self.assertTrue(each not in inv.edges()) + for each in inv.edges(): + self.assertTrue(each not in gr.edges()) + + def testEmptyGraphInverse(self): + gr = graph.graph() + inv = gr.inverse() + self.assertTrue(gr.nodes() == []) + self.assertTrue(gr.edges() == []) + + def testGraphComplete(self): + gr = graph.graph() + gr.add_nodes(xrange(10)) + gr.complete() + for i in xrange(10): + for j in range(10): + self.assertTrue((i, j) in gr.edges() or i == j) + + def testEmptyGraphComplete(self): + gr = graph.graph() + gr.complete() + self.assertTrue(gr.nodes() == []) + self.assertTrue(gr.edges() == []) + + def testGraphWithOneNodeComplete(self): + gr = graph.graph() + gr.add_node(0) + gr.complete() + self.assertTrue(gr.nodes() == [0]) + self.assertTrue(gr.edges() == []) + + def testAddGraph(self): + gr1 = graph.graph() + gr1.generate(25, 100) + gr2 = graph.graph() + gr2.generate(40, 200) + gr1.add_graph(gr2) + for each in gr2.nodes(): + self.assertTrue(each in gr1) + for each in gr2.edges(): + self.assertTrue(each in gr1.edges()) + + def testAddEmptyGraph(self): + gr1 = graph.graph() + gr1.generate(25, 100) + gr1c = copy.copy(gr1) + gr2 = graph.graph() + gr1.add_graph(gr2) + self.assertTrue(gr1.nodes() == gr1c.nodes()) + self.assertTrue(gr1.edges() == gr1c.edges()) + + def testAddSpanningTree(self): + gr = graph.graph() + st = {0: None, 1: 0, 2:0, 3: 1, 4: 2, 5: 3} + gr.add_spanning_tree(st) + for each in st: + self.assertTrue((each, st[each]) in gr.edges() or (each, st[each]) == (0, None)) + self.assertTrue((st[each], each) in gr.edges() or (each, st[each]) == (0, None)) + + def testAddEmptySpanningTree(self): + gr = graph.graph() + st = {} + gr.add_spanning_tree(st) + self.assertTrue(gr.nodes() == []) + self.assertTrue(gr.edges() == []) + + +# Run tests +if __name__ == '__main__': + unittest.main() diff -r 01f8c7aabb7e -r 06c2228e39cb thirdparty/python-graph/setup.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/thirdparty/python-graph/setup.py Wed Nov 26 23:56:19 2008 +0000 @@ -0,0 +1,34 @@ +#!/usr/bin/env python +# -*- coding: utf-8 -*- + +from distutils.core import setup +import os + +# Startup +appname = "python-graph" +appversion = "1.3.1" +docfolder = 'share/doc/' + appname + '-' + appversion + '/' +docfolder = os.path.normcase(docfolder) +docfiles = os.listdir('docs') +docs = os.path.normcase('docs/') +for i in xrange(len(docfiles)): + docfiles[i] = docs + docfiles[i] + +setup( + name = appname, + version = appversion, + packages = ['graph'], + data_files = [(docfolder, ['README','Changelog','COPYING']), + (docfolder + docs, docfiles), + ], + + # metadata + author = "Pedro Matiello", + author_email = "pmatiello@gmail.com", + description = "A library for working with graphs in Python", + license = "MIT", + keywords = "python graph algorithms library", + url = "http://code.google.com/p/python-graph/", + classifiers = ["License :: OSI Approved :: MIT License","Topic :: Software Development :: Libraries :: Python Modules"], + long_description = "python-graph is a library for working with graphs in Python. This software provides a suitable data structure for representing graphs and a whole set of important algorithms." +)