# HG changeset patch # User Pawel Solyga # Date 1228063467 0 # Node ID 88c486951f10cd314487adc6efa07a0ac2647145 # Parent 342bebadd075f4d4e0cb771f40e5b9e31cf49705 Remove python-graph from thirdparty, remove check_includes script and graph folder from scripts. This functionality is (cyclic imports check) is supported by pylint automatically so we don't need that any more. Patch by: Pawel Solyga Review by: Sverre Rabbelier diff -r 342bebadd075 -r 88c486951f10 scripts/check_includes.py --- a/scripts/check_includes.py Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,216 +0,0 @@ -#!/usr/bin/env python -# -# Copyright 2008 the Melange authors. -# -# Licensed under the Apache License, Version 2.0 (the "License"); -# you may not use this file except in compliance with the License. -# You may obtain a copy of the License at -# -# http://www.apache.org/licenses/LICENSE-2.0 -# -# Unless required by applicable law or agreed to in writing, software -# distributed under the License is distributed on an "AS IS" BASIS, -# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -# See the License for the specific language governing permissions and -# limitations under the License. - -"""TODO(SRabbelier) Update __doc__ string -""" - -__authors__ = [ - '"Sverre Rabbelier" ', - ] - - -import sys - -import cPickle -import os -import graph - - -ROOTDIR = "soc" - - -def parseFile(file_name): - if os.path.exists("imports.dat"): - log = open("imports.dat", "r") - all_imports = cPickle.load(log) - log.close() - else: - all_imports = {} - - if file_name in all_imports: - print "Overwriting previous data on '%s'." % file_name - - imports = [] - - file = open(file_name) - - for line in file: - if line.lstrip().startswith('import soc'): - splitline = line[:-1].split(' ') - mod = splitline[1] - imports.append(mod) - - if line.lstrip().startswith('from soc'): - splitline = line[:-1].split(' ') - mod = splitline[1] + '.' + splitline[3] - imports.append(mod) - - for idx, imp in enumerate(imports): - if imp in set(imports[idx+1:]): - sys.stderr.write("Warning: file '%s' has a redundant import: '%s'.\n" % (file_name, imp)) - - if file_name.endswith("__init__.py"): - normalized = file_name[:-12].replace('/', '.') - else: - normalized = file_name[:-3].replace('/', '.') - - print "Writing imports for file %s (%s)." % (file_name, normalized) - all_imports[normalized] = imports - - log = open("imports.dat", "w") - cPickle.dump(all_imports, log) - log.close() - - return 0 - - -def buildGraph(): - if not os.path.exists("imports.dat"): - sys.stderr.write("Missing imports.dat file, run 'build' first\n") - return - - log = open("imports.dat", "r") - all_imports = cPickle.load(log) - - gr = graph.digraph() - - gr.add_nodes(all_imports.keys()) - - for file_name, imports in all_imports.iteritems(): - for imp in imports: - gr.add_edge(file_name, imp) - - return gr - - -def showGraph(gr): - for node in gr: - print "%s: " % node - for edge in gr[node]: - print "\t%s" % edge - - return 0 - - -def getParents(gst, target): - parents = [] - current = target - - while True: - for node in gst: - if current in gst[node]: - parents.append(node) - current = node - break - else: - break - - return parents - - -def pathFrom(parents, first, target): - idx = parents.index(first) - path = parents[idx::-1] - return [target] + path + [target] - - -def findCycle(gr, gst, target): - parents = getParents(gst, target) - cycles = [] - - for node in gr[target]: - if node in parents: - cycles.append(pathFrom(parents, node, target)) - - return cycles - - -def findCycles(gr): - st, pre, post = gr.depth_first_search() - gst = graph.digraph() - gst.add_spanning_tree(st) - - cycles = [] - - for node in gr: - cycles += findCycle(gr, gst, node) - - return cycles - - -def drawGraph(gr): - st, pre, post = gr.depth_first_search() - gst = graph.digraph() - gst.add_spanning_tree(st) - - sys.path.append('/usr/lib/graphviz/python/') - import gv - dot = gst.write(fmt='dot') - gvv = gv.readstring(dot) - gv.layout(gvv,'dot') - gv.render(gvv,'png','imports.png') - - -def accumulate(arg, dirname, fnames): - for fname in fnames: - if not fname.endswith(".py"): - continue - - arg.append(os.path.join(dirname, fname)) - - -def main(args): - if len(args) != 1: - print "Supported options: 'print', 'build', 'find', and 'draw'." - return -1 - - action = args[0] - - if action == "build": - fnames = [] - os.path.walk(ROOTDIR, accumulate, fnames) - - for fname in fnames: - parseFile(fname) - - print "Done parsing." - return 0 - - gr = buildGraph() - if not gr: - return 1 - - if action == "show": - return showGraph(gr) - - if action == "draw": - return drawGraph(gr) - - if action == "find": - cycles = findCycles(gr) - for cycle in cycles: - print cycle - return 0 - - print "Unknown option." - return -1 - - -if __name__ == '__main__': - import sys - os.chdir("../app") - res = main(sys.argv[1:]) - sys.exit(0) diff -r 342bebadd075 -r 88c486951f10 scripts/graph/__init__.py --- a/scripts/graph/__init__.py Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,1573 +0,0 @@ -# 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 342bebadd075 -r 88c486951f10 scripts/graph/accessibility.py --- a/scripts/graph/accessibility.py Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,228 +0,0 @@ -# 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 342bebadd075 -r 88c486951f10 scripts/graph/generators.py --- a/scripts/graph/generators.py Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,82 +0,0 @@ -# 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 342bebadd075 -r 88c486951f10 scripts/graph/minmax.py --- a/scripts/graph/minmax.py Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,168 +0,0 @@ -# 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 342bebadd075 -r 88c486951f10 scripts/graph/readwrite.py --- a/scripts/graph/readwrite.py Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,302 +0,0 @@ -# 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 342bebadd075 -r 88c486951f10 scripts/graph/searching.py --- a/scripts/graph/searching.py Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,167 +0,0 @@ -# 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 342bebadd075 -r 88c486951f10 scripts/graph/sorting.py --- a/scripts/graph/sorting.py Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,49 +0,0 @@ -# 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 342bebadd075 -r 88c486951f10 scripts/graph/traversal.py --- a/scripts/graph/traversal.py Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,81 +0,0 @@ -# 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 342bebadd075 -r 88c486951f10 thirdparty/python-graph/COPYING --- a/thirdparty/python-graph/COPYING Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,22 +0,0 @@ -# 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 342bebadd075 -r 88c486951f10 thirdparty/python-graph/Changelog --- a/thirdparty/python-graph/Changelog Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,140 +0,0 @@ -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 342bebadd075 -r 88c486951f10 thirdparty/python-graph/MANIFEST --- a/thirdparty/python-graph/MANIFEST Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,34 +0,0 @@ -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 342bebadd075 -r 88c486951f10 thirdparty/python-graph/Makefile --- a/thirdparty/python-graph/Makefile Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,17 +0,0 @@ -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 342bebadd075 -r 88c486951f10 thirdparty/python-graph/README --- a/thirdparty/python-graph/README Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,48 +0,0 @@ -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 342bebadd075 -r 88c486951f10 thirdparty/python-graph/docs/api-objects.txt --- a/thirdparty/python-graph/docs/api-objects.txt Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,144 +0,0 @@ -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 342bebadd075 -r 88c486951f10 thirdparty/python-graph/docs/class-tree.html --- a/thirdparty/python-graph/docs/class-tree.html Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,122 +0,0 @@ - - - - - Class Hierarchy - - - - - - - - - - - - - - - - - - - - - - - -
   Home      Trees      Indices      Help    - - -
python-graph
- - - - - -
  - - -
-
-
- [ Module Hierarchy - | Class Hierarchy ] -

-

Class Hierarchy

- - - - - - - - - - - - - - - - - - - -
   Home      Trees      Indices      Help    - - -
python-graph
- - - - - -
- Generated by Epydoc 3.0.1 on Mon Oct 27 20:36:37 2008 - - http://epydoc.sourceforge.net -
- - - - diff -r 342bebadd075 -r 88c486951f10 thirdparty/python-graph/docs/crarr.png Binary file thirdparty/python-graph/docs/crarr.png has changed diff -r 342bebadd075 -r 88c486951f10 thirdparty/python-graph/docs/epydoc.css --- a/thirdparty/python-graph/docs/epydoc.css Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,322 +0,0 @@ - - -/* 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 342bebadd075 -r 88c486951f10 thirdparty/python-graph/docs/epydoc.js --- a/thirdparty/python-graph/docs/epydoc.js Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,293 +0,0 @@ -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 342bebadd075 -r 88c486951f10 thirdparty/python-graph/docs/graph-module.html --- a/thirdparty/python-graph/docs/graph-module.html Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,168 +0,0 @@ - - - - - graph - - - - - - - - - - - - - - - - - - - - - - - -
   Home      Trees      Indices      Help    - - -
python-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. -
- - - - - - - - - - - - - - - - - - -
   Home      Trees      Indices      Help    - - -
python-graph
- - - - - -
- Generated by Epydoc 3.0.1 on Mon Oct 27 20:36:37 2008 - - http://epydoc.sourceforge.net -
- - - - diff -r 342bebadd075 -r 88c486951f10 thirdparty/python-graph/docs/graph.accessibility-module.html --- a/thirdparty/python-graph/docs/graph.accessibility-module.html Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,335 +0,0 @@ - - - - - graph.accessibility - - - - - - - - - - - - - - - - - - - - - - - -
   Home      Trees      Indices      Help    - - -
python-graph
- - - - - -
- - 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.
-
-
-
-
- - - - - - - - - - - - - - - - - - -
   Home      Trees      Indices      Help    - - -
python-graph
- - - - - -
- Generated by Epydoc 3.0.1 on Mon Oct 27 20:36:37 2008 - - http://epydoc.sourceforge.net -
- - - - diff -r 342bebadd075 -r 88c486951f10 thirdparty/python-graph/docs/graph.digraph-class.html --- a/thirdparty/python-graph/docs/graph.digraph-class.html Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,2103 +0,0 @@ - - - - - graph.digraph - - - - - - - - - - - - - - - - - - - - - - - -
   Home      Trees      Indices      Help    - - -
python-graph
- - - - - -
- - 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. -
    2. - 'dot' - DOT Language (for GraphViz) -
      3. -
    3. - 'dotwt' - DOT Language with weight information -
      4. -
    • -
-
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. -
  2. - Graph's level-based ordering -
    3. -
-
-
-
- -
- -
- - -
-

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. -
  2. - Graph's preordering -
    3. -
  3. - Graph's postordering -
    4. -
-
-
-
- -
- -
- - -
-

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. -
  2. - Shortest distance from given source to each target node -
    3. -
-

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. -

-
-
-
- - - - - - - - - - - - - - - - - - -
   Home      Trees      Indices      Help    - - -
python-graph
- - - - - -
- Generated by Epydoc 3.0.1 on Mon Oct 27 20:36:37 2008 - - http://epydoc.sourceforge.net -
- - - - diff -r 342bebadd075 -r 88c486951f10 thirdparty/python-graph/docs/graph.generators-module.html --- a/thirdparty/python-graph/docs/graph.generators-module.html Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,179 +0,0 @@ - - - - - graph.generators - - - - - - - - - - - - - - - - - - - - - - - -
   Home      Trees      Indices      Help    - - -
python-graph
- - - - - -
- - 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).
    • -
-
-
-
-
- - - - - - - - - - - - - - - - - - -
   Home      Trees      Indices      Help    - - -
python-graph
- - - - - -
- Generated by Epydoc 3.0.1 on Mon Oct 27 20:36:37 2008 - - http://epydoc.sourceforge.net -
- - - - diff -r 342bebadd075 -r 88c486951f10 thirdparty/python-graph/docs/graph.graph-class.html --- a/thirdparty/python-graph/docs/graph.graph-class.html Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,1982 +0,0 @@ - - - - - graph.graph - - - - - - - - - - - - - - - - - - - - - - - -
   Home      Trees      Indices      Help    - - -
python-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. -
    2. - 'dot' - DOT Language (for GraphViz) -
      3. -
    3. - 'dotwt' - DOT Language with weight information -
      4. -
    • -
-
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. -
  2. - Graph's level-based ordering -
    3. -
-
-
-
- -
- -
- - -
-

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. -
  2. - Graph's preordering -
    3. -
  3. - Graph's postordering -
    4. -
-
-
-
- -
- -
- - -
-

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. -
  2. - Shortest distance from given source to each target node -
    3. -
-

Inaccessible target nodes do not appear in either - dictionary.

-
-

Attention: - All weights must be nonnegative. -

-
-
-
- - - - - - - - - - - - - - - - - - -
   Home      Trees      Indices      Help    - - -
python-graph
- - - - - -
- Generated by Epydoc 3.0.1 on Mon Oct 27 20:36:37 2008 - - http://epydoc.sourceforge.net -
- - - - diff -r 342bebadd075 -r 88c486951f10 thirdparty/python-graph/docs/graph.hypergraph-class.html --- a/thirdparty/python-graph/docs/graph.hypergraph-class.html Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,1032 +0,0 @@ - - - - - graph.hypergraph - - - - - - - - - - - - - - - - - - - - - - - -
   Home      Trees      Indices      Help    - - -
python-graph
- - - - - -
- - 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. -
    2. - 'dot' - DOT Language (for GraphViz) -
      3. -
    3. - 'dotclr' - DOT Language, coloured -
      4. -
    • -
-
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.
-
-
-
-
- - - - - - - - - - - - - - - - - - -
   Home      Trees      Indices      Help    - - -
python-graph
- - - - - -
- Generated by Epydoc 3.0.1 on Mon Oct 27 20:36:38 2008 - - http://epydoc.sourceforge.net -
- - - - diff -r 342bebadd075 -r 88c486951f10 thirdparty/python-graph/docs/graph.minmax-module.html --- a/thirdparty/python-graph/docs/graph.minmax-module.html Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,237 +0,0 @@ - - - - - graph.minmax - - - - - - - - - - - - - - - - - - - - - - - -
   Home      Trees      Indices      Help    - - -
python-graph
- - - - - -
- - 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. -
  2. - Shortest distance from given source to each target node -
    3. -
-

Inaccessible target nodes do not appear in either - dictionary.

-
-

Attention: - All weights must be nonnegative. -

-
-
-
- - - - - - - - - - - - - - - - - - -
   Home      Trees      Indices      Help    - - -
python-graph
- - - - - -
- Generated by Epydoc 3.0.1 on Mon Oct 27 20:36:37 2008 - - http://epydoc.sourceforge.net -
- - - - diff -r 342bebadd075 -r 88c486951f10 thirdparty/python-graph/docs/graph.readwrite-module.html --- a/thirdparty/python-graph/docs/graph.readwrite-module.html Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,496 +0,0 @@ - - - - - graph.readwrite - - - - - - - - - - - - - - - - - - - - - - - -
   Home      Trees      Indices      Help    - - -
python-graph
- - - - - -
- - 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',
-...
-
-
-
-
-
-
- - - - - - - - - - - - - - - - - - -
   Home      Trees      Indices      Help    - - -
python-graph
- - - - - -
- Generated by Epydoc 3.0.1 on Mon Oct 27 20:36:37 2008 - - http://epydoc.sourceforge.net -
- - - - diff -r 342bebadd075 -r 88c486951f10 thirdparty/python-graph/docs/graph.searching-module.html --- a/thirdparty/python-graph/docs/graph.searching-module.html Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,238 +0,0 @@ - - - - - graph.searching - - - - - - - - - - - - - - - - - - - - - - - -
   Home      Trees      Indices      Help    - - -
python-graph
- - - - - -
- - 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. -
  2. - Graph's level-based ordering -
    3. -
-
-
-
- -
- -
- - -
-

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. -
  2. - Graph's preordering -
    3. -
  3. - Graph's postordering -
    4. -
-
-
-
-
- - - - - - - - - - - - - - - - - - -
   Home      Trees      Indices      Help    - - -
python-graph
- - - - - -
- Generated by Epydoc 3.0.1 on Mon Oct 27 20:36:37 2008 - - http://epydoc.sourceforge.net -
- - - - diff -r 342bebadd075 -r 88c486951f10 thirdparty/python-graph/docs/graph.sorting-module.html --- a/thirdparty/python-graph/docs/graph.sorting-module.html Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,174 +0,0 @@ - - - - - graph.sorting - - - - - - - - - - - - - - - - - - - - - - - -
   Home      Trees      Indices      Help    - - -
python-graph
- - - - - -
- - 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. -

-
-
-
- - - - - - - - - - - - - - - - - - -
   Home      Trees      Indices      Help    - - -
python-graph
- - - - - -
- Generated by Epydoc 3.0.1 on Mon Oct 27 20:36:37 2008 - - http://epydoc.sourceforge.net -
- - - - diff -r 342bebadd075 -r 88c486951f10 thirdparty/python-graph/docs/graph.traversal-module.html --- a/thirdparty/python-graph/docs/graph.traversal-module.html Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,186 +0,0 @@ - - - - - graph.traversal - - - - - - - - - - - - - - - - - - - - - - - -
   Home      Trees      Indices      Help    - - -
python-graph
- - - - - -
- - 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.
-
-
-
-
- - - - - - - - - - - - - - - - - - -
   Home      Trees      Indices      Help    - - -
python-graph
- - - - - -
- Generated by Epydoc 3.0.1 on Mon Oct 27 20:36:37 2008 - - http://epydoc.sourceforge.net -
- - - - diff -r 342bebadd075 -r 88c486951f10 thirdparty/python-graph/docs/help.html --- a/thirdparty/python-graph/docs/help.html Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,272 +0,0 @@ - - - - - Help - - - - - - - - - - - - - - - - - - - - - - - -
   Home      Trees      Indices      Help    - - -
python-graph
- - - - - -
  - - -
-
- -

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.

- - - - - - - - - - - - - - - - - - -
   Home      Trees      Indices      Help    - - -
python-graph
- - - - - -
- Generated by Epydoc 3.0.1 on Mon Oct 27 20:36:37 2008 - - http://epydoc.sourceforge.net -
- - - - diff -r 342bebadd075 -r 88c486951f10 thirdparty/python-graph/docs/identifier-index.html --- a/thirdparty/python-graph/docs/identifier-index.html Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,616 +0,0 @@ - - - - - Identifier Index - - - - - - - - - - - - - - - - - - - - - - - -
   Home      Trees      Indices      Help    - - -
python-graph
- - - - - -
  - - -
-
- -
-

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

 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
accessibility
-(in graph)		add_edge_attribute()
-(in graph)		add_node_attribute()
-(in digraph)
accessibility()
-(in graph.accessibility)		add_graph()
-(in digraph)		add_node_attribute()
-(in graph)
accessibility()
-(in digraph)		add_graph()
-(in graph)		add_nodes()
-(in digraph)
accessibility()
-(in graph)		add_hyperedge()
-(in hypergraph)		add_nodes()
-(in graph)
accessibility()
-(in hypergraph)		add_hyperedges()
-(in hypergraph)		add_nodes()
-(in hypergraph)
add_edge()
-(in digraph)		add_node()
-(in digraph)		add_spanning_tree()
-(in digraph)
add_edge()
-(in graph)		add_node()
-(in graph)		add_spanning_tree()
-(in graph)
add_edge_attribute()
-(in digraph)		add_node()
-(in hypergraph)		 
-

B

 - - - - - - - -
breadth_first_search()
-(in digraph)		breadth_first_search()
-(in graph)		breadth_first_search()
-(in graph.searching)
   
-

C

 - - - - - - - - - - - - - - - - - - - - - - - - - - -
colors
-(in graph.readwrite)		connected_components()
-(in hypergraph)		cut_nodes()
-(in graph.accessibility)
complete()
-(in digraph)		cut_edges()
-(in graph.accessibility)		cut_nodes()
-(in digraph)
complete()
-(in graph)		cut_edges()
-(in digraph)		cut_nodes()
-(in graph)
connected_components()
-(in graph.accessibility)		cut_edges()
-(in graph)		cut_nodes()
-(in hypergraph)
connected_components()
-(in graph)		cut_hyperedges()
-(in hypergraph)		 
-

D

 - - - - - - - - - - - - - - - - -
degree()
-(in digraph)		del_node()
-(in digraph)		depth_first_search()
-(in graph)
del_edge()
-(in digraph)		del_node()
-(in graph)		depth_first_search()
-(in graph.searching)
del_edge()
-(in graph)		depth_first_search()
-(in digraph)		digraph
-(in graph)
-

E

 - - - - - - - -
edges()
-(in digraph)		edges()
-(in graph)		 
   
-

G

 - - - - - - - - - - - - - - - - - - - - - - - - - - -
generate()
-(in digraph)		get_edge_attributes()
-(in graph)		get_node_attributes()
-(in digraph)
generate()
-(in graph.generators)		get_edge_label()
-(in digraph)		get_node_attributes()
-(in graph)
generate()
-(in graph)		get_edge_label()
-(in graph)		graph
generators
-(in graph)		get_edge_weight()
-(in digraph)		graph
-(in graph)
get_edge_attributes()
-(in digraph)		get_edge_weight()
-(in graph)		 
-

H

 - - - - - - - - - - - - - - - - -
has_edge()
-(in digraph)		has_node()
-(in graph)		hypergraph
-(in graph)
has_edge()
-(in graph)		has_node()
-(in hypergraph)		 
has_node()
-(in digraph)		hyperedges()
-(in hypergraph)		 
-

I

 - - - - - - - -
incidents()
-(in digraph)		inverse()
-(in digraph)		inverse()
-(in graph)
   
-

L

 - - - - - - - -
link()
-(in hypergraph)		links()
-(in hypergraph)		 
   
-

M

 - - - - - - - - - - - -
minimal_spanning_tree()
-(in digraph)		minimal_spanning_tree()
-(in graph.minmax)		mutual_accessibility()
-(in graph.accessibility)
minimal_spanning_tree()
-(in graph)		minmax
-(in graph)		mutual_accessibility()
-(in digraph)
-

N

 - - - - - - - - - - - -
neighbors()
-(in digraph)		nodes()
-(in digraph)		nodes()
-(in hypergraph)
neighbors()
-(in graph)		nodes()
-(in graph)		 
-

O

 - - - - - - - -
order()
-(in digraph)		order()
-(in graph)		 
   
-

R

 - - - - - - - - - - - - - - - - -
rank()
-(in hypergraph)		read()
-(in hypergraph)		readwrite
-(in graph)
read()
-(in digraph)		read_xml()
-(in graph.readwrite)		 
read()
-(in graph)		read_xml_hypergraph()
-(in graph.readwrite)		 
-

S

 - - - - - - - - - - - - - - - - -
searching
-(in graph)		set_edge_weight()
-(in digraph)		shortest_path()
-(in graph)
set_edge_label()
-(in digraph)		set_edge_weight()
-(in graph)		shortest_path()
-(in graph.minmax)
set_edge_label()
-(in graph)		shortest_path()
-(in digraph)		sorting
-(in graph)
-

T

 - - - - - - - - - - - -
topological_sorting()
-(in digraph)		traversal
-(in graph)		traversal()
-(in graph)
topological_sorting()
-(in graph.sorting)		traversal()
-(in digraph)		traversal()
-(in graph.traversal)
-

U

 - - - - - - - -
unlink()
-(in hypergraph)		  
   
-

W

 - - - - - - - - - - - - - - - - -
write()
-(in digraph)		write_dot_digraph()
-(in graph.readwrite)		write_xml()
-(in graph.readwrite)
write()
-(in graph)		write_dot_graph()
-(in graph.readwrite)		write_xml_hypergraph()
-(in graph.readwrite)
write()
-(in hypergraph)		write_dot_hypergraph()
-(in graph.readwrite)		 
-

_

 - - - - - - - - - - - - - - - - - - - - - - - - - - -
__getitem__()
-(in digraph)		__iter__()
-(in digraph)		__str__()
-(in digraph)
__getitem__()
-(in graph)		__iter__()
-(in graph)		__str__()
-(in graph)
__init__()
-(in digraph)		__len__()
-(in digraph)		__str__()
-(in hypergraph)
__init__()
-(in graph)		__len__()
-(in graph)		 
__init__()
-(in hypergraph)		__len__()
-(in hypergraph)		 
-
-

- - - - - - - - - - - - - - - - - -
   Home      Trees      Indices      Help    - - -
python-graph
- - - - - -
- Generated by Epydoc 3.0.1 on Mon Oct 27 20:36:37 2008 - - http://epydoc.sourceforge.net -
- - - - diff -r 342bebadd075 -r 88c486951f10 thirdparty/python-graph/docs/index.html --- a/thirdparty/python-graph/docs/index.html Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,168 +0,0 @@ - - - - - graph - - - - - - - - - - - - - - - - - - - - - - - -
   Home      Trees      Indices      Help    - - -
python-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. -
- - - - - - - - - - - - - - - - - - -
   Home      Trees      Indices      Help    - - -
python-graph
- - - - - -
- Generated by Epydoc 3.0.1 on Mon Oct 27 20:36:37 2008 - - http://epydoc.sourceforge.net -
- - - - diff -r 342bebadd075 -r 88c486951f10 thirdparty/python-graph/docs/module-tree.html --- a/thirdparty/python-graph/docs/module-tree.html Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,119 +0,0 @@ - - - - - Module Hierarchy - - - - - - - - - - - - - - - - - - - - - - - -
   Home      Trees      Indices      Help    - - -
python-graph
- - - - - -
  - - -
-
-
- [ Module Hierarchy - | Class Hierarchy ] -

-

Module Hierarchy

- - - - - - - - - - - - - - - - - - - -
   Home      Trees      Indices      Help    - - -
python-graph
- - - - - -
- Generated by Epydoc 3.0.1 on Mon Oct 27 20:36:37 2008 - - http://epydoc.sourceforge.net -
- - - - diff -r 342bebadd075 -r 88c486951f10 thirdparty/python-graph/docs/redirect.html --- a/thirdparty/python-graph/docs/redirect.html Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,38 +0,0 @@ -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 342bebadd075 -r 88c486951f10 thirdparty/python-graph/examples/draw.py --- a/thirdparty/python-graph/examples/draw.py Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,41 +0,0 @@ -#!/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 342bebadd075 -r 88c486951f10 thirdparty/python-graph/examples/drawhyper.py --- a/thirdparty/python-graph/examples/drawhyper.py Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,37 +0,0 @@ -#!/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 342bebadd075 -r 88c486951f10 thirdparty/python-graph/examples/ex1.py --- a/thirdparty/python-graph/examples/ex1.py Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,65 +0,0 @@ -#!/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 342bebadd075 -r 88c486951f10 thirdparty/python-graph/examples/example.tls --- a/thirdparty/python-graph/examples/example.tls Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,12 +0,0 @@ -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 342bebadd075 -r 88c486951f10 thirdparty/python-graph/examples/graph.xml --- a/thirdparty/python-graph/examples/graph.xml Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,37 +0,0 @@ - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - diff -r 342bebadd075 -r 88c486951f10 thirdparty/python-graph/examples/lts2graph.py --- a/thirdparty/python-graph/examples/lts2graph.py Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,115 +0,0 @@ -#!/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 342bebadd075 -r 88c486951f10 thirdparty/python-graph/examples/read.py --- a/thirdparty/python-graph/examples/read.py Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,17 +0,0 @@ -#!/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 342bebadd075 -r 88c486951f10 thirdparty/python-graph/examples/write.py --- a/thirdparty/python-graph/examples/write.py Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,35 +0,0 @@ -#!/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 342bebadd075 -r 88c486951f10 thirdparty/python-graph/graph/__init__.py --- a/thirdparty/python-graph/graph/__init__.py Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,1573 +0,0 @@ -# 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 342bebadd075 -r 88c486951f10 thirdparty/python-graph/graph/accessibility.py --- a/thirdparty/python-graph/graph/accessibility.py Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,228 +0,0 @@ -# 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 342bebadd075 -r 88c486951f10 thirdparty/python-graph/graph/generators.py --- a/thirdparty/python-graph/graph/generators.py Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,82 +0,0 @@ -# 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 342bebadd075 -r 88c486951f10 thirdparty/python-graph/graph/minmax.py --- a/thirdparty/python-graph/graph/minmax.py Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,168 +0,0 @@ -# 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 342bebadd075 -r 88c486951f10 thirdparty/python-graph/graph/readwrite.py --- a/thirdparty/python-graph/graph/readwrite.py Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,302 +0,0 @@ -# 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 342bebadd075 -r 88c486951f10 thirdparty/python-graph/graph/searching.py --- a/thirdparty/python-graph/graph/searching.py Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,167 +0,0 @@ -# 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 342bebadd075 -r 88c486951f10 thirdparty/python-graph/graph/sorting.py --- a/thirdparty/python-graph/graph/sorting.py Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,49 +0,0 @@ -# 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 342bebadd075 -r 88c486951f10 thirdparty/python-graph/graph/traversal.py --- a/thirdparty/python-graph/graph/traversal.py Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,81 +0,0 @@ -# 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 342bebadd075 -r 88c486951f10 thirdparty/python-graph/misc/epydoc.css --- a/thirdparty/python-graph/misc/epydoc.css Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,322 +0,0 @@ - - -/* 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 342bebadd075 -r 88c486951f10 thirdparty/python-graph/misc/unittests-digraph.py --- a/thirdparty/python-graph/misc/unittests-digraph.py Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,145 +0,0 @@ -#!/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 342bebadd075 -r 88c486951f10 thirdparty/python-graph/misc/unittests-graph.py --- a/thirdparty/python-graph/misc/unittests-graph.py Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,146 +0,0 @@ -#!/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 342bebadd075 -r 88c486951f10 thirdparty/python-graph/setup.py --- a/thirdparty/python-graph/setup.py Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,34 +0,0 @@ -#!/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." -)