# HG changeset patch # User Sverre Rabbelier # Date 1227829268 0 # Node ID 32a30f6095301dc5d12bfe5753443c66bb1eb1b3 # Parent c1f9435bb645615123a2c51593a8dd8114812232 Moved check_includes and graph from app to scripts Patch by: Sverre Rabbelier diff -r c1f9435bb645 -r 32a30f609530 app/check_includes.py --- a/app/check_includes.py Thu Nov 27 23:40:30 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,194 +0,0 @@ -#!/usr/bin/env python - -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 c1f9435bb645 -r 32a30f609530 app/graph/__init__.py --- a/app/graph/__init__.py Thu Nov 27 23:40:30 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 c1f9435bb645 -r 32a30f609530 app/graph/accessibility.py --- a/app/graph/accessibility.py Thu Nov 27 23:40:30 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 c1f9435bb645 -r 32a30f609530 app/graph/generators.py --- a/app/graph/generators.py Thu Nov 27 23:40:30 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 c1f9435bb645 -r 32a30f609530 app/graph/minmax.py --- a/app/graph/minmax.py Thu Nov 27 23:40:30 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 c1f9435bb645 -r 32a30f609530 app/graph/readwrite.py --- a/app/graph/readwrite.py Thu Nov 27 23:40:30 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 c1f9435bb645 -r 32a30f609530 app/graph/searching.py --- a/app/graph/searching.py Thu Nov 27 23:40:30 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 c1f9435bb645 -r 32a30f609530 app/graph/sorting.py --- a/app/graph/sorting.py Thu Nov 27 23:40:30 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 c1f9435bb645 -r 32a30f609530 app/graph/traversal.py --- a/app/graph/traversal.py Thu Nov 27 23:40:30 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 c1f9435bb645 -r 32a30f609530 scripts/check_includes.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/scripts/check_includes.py Thu Nov 27 23:41:08 2008 +0000 @@ -0,0 +1,194 @@ +#!/usr/bin/env python + +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 c1f9435bb645 -r 32a30f609530 scripts/graph/__init__.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/scripts/graph/__init__.py Thu Nov 27 23:41:08 2008 +0000 @@ -0,0 +1,1573 @@ +# Copyright (c) 2007-2008 Pedro Matiello +# Christian Muise +# Nathan Davis +# Zsolt Haraszti +# +# Permission is hereby granted, free of charge, to any person +# obtaining a copy of this software and associated documentation +# files (the "Software"), to deal in the Software without +# restriction, including without limitation the rights to use, +# copy, modify, merge, publish, distribute, sublicense, and/or sell +# copies of the Software, and to permit persons to whom the +# Software is furnished to do so, subject to the following +# conditions: + +# The above copyright notice and this permission notice shall be +# included in all copies or substantial portions of the Software. + +# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES +# OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND +# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT +# HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, +# WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR +# OTHER DEALINGS IN THE SOFTWARE. + + +""" +python-graph + +A library for working with graphs in Python. + +@version: 1.3.1 +""" + + +# Imports +import accessibility +import generators +import minmax +import searching +import sorting +import readwrite +import traversal + + +# Graph class -------------------------------------------------------------------------------------- + +class graph (object): + """ + Graph class. + + Graphs are built of nodes and edges. + + @sort: __init__, __getitem__, __iter__, __len__, __str__, add_edge, add_edge_attribute, + add_graph, add_node, add_node_attribute, add_nodes, add_spanning_tree, complete, del_edge, + del_node, edges, get_edge_attributes, get_edge_label, get_edge_weight, get_node_attributes, + has_edge, has_node, inverse, neighbors, nodes, order, set_edge_label, set_edge_weight, + traversal, generate, read, write, accessibility, breadth_first_search, connected_components, + cut_edges, cut_nodes, depth_first_search, minimal_spanning_tree, shortest_path + """ + + + def __init__(self): + """ + Initialize a graph. + """ + self.node_neighbors = {} # Pairing: Node -> Neighbors + self.edge_properties = {} # Pairing: Edge -> (Label, Weight) + self.node_attr = {} # Pairing: Node -> Attributes + self.edge_attr = {} # Pairing: Edge -> Attributes + + + def __str__(self): + """ + Return a string representing the graph when requested by str() (or print). + + @rtype: string + @return: String representing the graph. + """ + return "" + + + def __len__(self): + """ + Return the order of the graph when requested by len(). + + @rtype: number + @return: Size of the graph. + """ + return len(self.node_neighbors) + + + def __iter__(self): + """ + Return a iterator passing through all nodes in the graph. + + @rtype: iterator + @return: Iterator passing through all nodes in the graph. + """ + for each in self.node_neighbors.iterkeys(): + yield each + + + def __getitem__(self, node): + """ + Return a iterator passing through all neighbors of the given node. + + @rtype: iterator + @return: Iterator passing through all neighbors of the given node. + """ + for each in self.node_neighbors[node]: + yield each + + + def read(self, string, fmt='xml'): + """ + Read a graph from a string. Nodes and edges specified in the input will be added to the + current graph. + + @type string: string + @param string: Input string specifying a graph. + + @type fmt: string + @param fmt: Input format. Possible formats are: + 1. 'xml' - XML (default) + """ + if (fmt == 'xml'): + readwrite.read_xml(self, string) + + + def write(self, fmt='xml'): + """ + Write the graph to a string. Depending of the output format, this string can be used by + read() to rebuild the graph. + + @type fmt: string + @param fmt: Output format. Possible formats are: + 1. 'xml' - XML (default) + 2. 'dot' - DOT Language (for GraphViz) + 3. 'dotwt' - DOT Language with weight information + + @rtype: string + @return: String specifying the graph. + """ + if (fmt == 'xml'): + return readwrite.write_xml(self) + elif (fmt == 'dot'): + return readwrite.write_dot_graph(self, False) + elif (fmt == 'dotwt'): + return readwrite.write_dot_graph(self, True) + + + def generate(self, num_nodes, num_edges, weight_range=(1, 1)): + """ + Add nodes and random edges to the graph. + + @type num_nodes: number + @param num_nodes: Number of nodes. + + @type num_edges: number + @param num_edges: Number of edges. + + @type weight_range: tuple + @param weight_range: tuple of two integers as lower and upper limits on randomly generated + weights (uniform distribution). + """ + generators.generate(self, num_nodes, num_edges, weight_range) + + + def nodes(self): + """ + Return node list. + + @rtype: list + @return: Node list. + """ + return self.node_neighbors.keys() + + + def neighbors(self, node): + """ + Return all nodes that are directly accessible from given node. + + @type node: node + @param node: Node identifier + + @rtype: list + @return: List of nodes directly accessible from given node. + """ + return self.node_neighbors[node] + + + def edges(self): + """ + Return all edges in the graph. + + @rtype: list + @return: List of all edges in the graph. + """ + return self.edge_properties.keys() + + + def has_node(self, node): + """ + Return whether the requested node exists. + + @type node: node + @param node: Node identifier + + @rtype: boolean + @return: Truth-value for node existence. + """ + return self.node_neighbors.has_key(node) + + + def add_node(self, node, attrs=[]): + """ + Add given node to the graph. + + @attention: While nodes can be of any type, it's strongly recommended to use only numbers + and single-line strings as node identifiers if you intend to use write(). + + @type node: node + @param node: Node identifier. + + @type attrs: list + @param attrs: List of node attributes specified as (attribute, value) tuples. + """ + if (not node in self.node_neighbors): + self.node_neighbors[node] = [] + self.node_attr[node] = attrs + + + def add_nodes(self, nodelist): + """ + Add given nodes to the graph. + + @attention: While nodes can be of any type, it's strongly recommended to use only numbers + and single-line strings as node identifiers if you intend to use write(). + + @type nodelist: list + @param nodelist: List of nodes to be added to the graph. + """ + for each in nodelist: + self.add_node(each) + + + def add_edge(self, u, v, wt=1, label='', attrs=[]): + """ + Add an edge (u,v) to the graph connecting nodes u and v. + + @type u: node + @param u: One node. + + @type v: node + @param v: Other node. + + @type wt: number + @param wt: Edge weight. + + @type label: string + @param label: Edge label. + + @type attrs: list + @param attrs: List of node attributes specified as (attribute, value) tuples. + """ + if (v not in self.node_neighbors[u] and u not in self.node_neighbors[v]): + self.node_neighbors[u].append(v) + self.node_neighbors[v].append(u) + self.edge_properties[(u, v)] = [label, wt] + self.edge_properties[(v, u)] = [label, wt] + self.edge_attr[(u, v)] = attrs + self.edge_attr[(v, u)] = attrs + + + def del_node(self, node): + """ + Remove a node from the graph. + + @type node: node + @param node: Node identifier. + """ + for each in list(self.neighbors(node)): + self.del_edge(each, node) + del(self.node_neighbors[node]) + del(self.node_attr[node]) + + + def del_edge(self, u, v): + """ + Remove an edge (u, v) from the graph. + + @type u: node + @param u: One node. + + @type v: node + @param v: Other node. + """ + self.node_neighbors[u].remove(v) + self.node_neighbors[v].remove(u) + del(self.edge_properties[(u,v)]) + del(self.edge_properties[(v,u)]) + del(self.edge_attr[(u,v)]) + del(self.edge_attr[(v,u)]) + + + def get_edge_weight(self, u, v): + """ + Get the weight of an edge. + + @type u: node + @param u: One node. + + @type v: node + @param v: Other node. + + @rtype: number + @return: Edge weight. + """ + return self.edge_properties[(u, v)][1] + + + def set_edge_weight(self, u, v, wt): + """ + Set the weight of an edge. + + @type u: node + @param u: One node. + + @type v: node + @param v: Other node. + + @type wt: number + @param wt: Edge weight. + """ + self.edge_properties[(u, v)][1] = wt + self.edge_properties[(v, u)][1] = wt + + + def get_edge_label(self, u, v): + """ + Get the label of an edge. + + @type u: node + @param u: One node. + + @type v: node + @param v: Other node. + + @rtype: string + @return: Edge label + """ + return self.edge_properties[(u, v)][0] + + + def set_edge_label(self, u, v, label): + """ + Set the label of an edge. + + @type u: node + @param u: One node. + + @type v: node + @param v: Other node. + + @type label: string + @param label: Edge label. + """ + self.edge_properties[(u, v)][0] = label + self.edge_properties[(v, u)][0] = label + + + def add_node_attribute(self, node, attr): + """ + Add attribute to the given node. + + @type node: node + @param node: Node identifier + + @type attr: tuple + @param attr: Node attribute specified as a tuple in the form (attribute, value). + """ + self.node_attr[node] = self.node_attr[node] + [attr] + + + def get_node_attributes(self, node): + """ + Return the attributes of the given node. + + @type node: node + @param node: Node identifier + + @rtype: list + @return: List of attributes specified tuples in the form (attribute, value). + """ + return self.node_attr[node] + + + def add_edge_attribute(self, u, v, attr): + """ + Add attribute to the given edge. + + @type u: node + @param u: One node. + + @type v: node + @param v: Other node. + + @type attr: tuple + @param attr: Node attribute specified as a tuple in the form (attribute, value). + """ + self.edge_attr[(u,v)] = self.edge_attr[(u,v)] + [attr] + self.edge_attr[(v,u)] = self.edge_attr[(v,u)] + [attr] + + + def get_edge_attributes(self, u, v): + """ + Return the attributes of the given edge. + + @type u: node + @param u: One node. + + @type v: node + @param v: Other node. + + @rtype: list + @return: List of attributes specified tuples in the form (attribute, value). + """ + return self.edge_attr[(u,v)] + + + def has_edge(self, u, v): + """ + Return whether an edge between nodes u and v exists. + + @type u: node + @param u: One node. + + @type v: node + @param v: Other node. + + @rtype: boolean + @return: Truth-value for edge existence. + """ + return self.edge_properties.has_key((u,v)) and self.edge_properties.has_key((v,u)) + + + def order(self, node): + """ + Return the order of the given node. + + @rtype: number + @return: Order of the given node. + """ + return len(self.neighbors(node)) + + + def complete(self): + """ + Make the graph a complete graph. + + @attention: This will modify the current graph. + """ + for each in self.nodes(): + for other in self.nodes(): + if (each != other): + self.add_edge(each, other) + + + def inverse(self): + """ + Return the inverse of the graph. + + @rtype: graph + @return: Complement graph for the graph. + """ + inv = graph() + inv.add_nodes(self.nodes()) + inv.complete() + for each in self.edges(): + if (inv.has_edge(each[0], each[1])): + inv.del_edge(each[0], each[1]) + return inv + + + def add_graph(self, graph): + """ + Add other graph to the graph. + + @attention: Attributes and labels are not preserved. + + @type graph: graph + @param graph: Graph + """ + self.add_nodes(graph.nodes()) + for each_node in graph.nodes(): + for each_edge in graph.neighbors(each_node): + self.add_edge(each_node, each_edge) + + + def add_spanning_tree(self, st): + """ + Add a spanning tree to the graph. + + @type st: dictionary + @param st: Spanning tree. + """ + self.add_nodes(st.keys()) + for each in st: + if (st[each] is not None): + self.add_edge(st[each], each) + + + def traversal(self, node, order='pre'): + """ + Graph traversal iterator. + + @type node: node + @param node: Node. + + @type order: string + @param order: traversal ordering. Possible values are: + 2. 'pre' - Preordering (default) + 1. 'post' - Postordering + + @rtype: iterator + @return: Traversal iterator. + """ + for each in traversal.traversal(self, node, order): + yield each + + + def depth_first_search(self, root=None): + """ + Depht-first search. + + @type root: node + @param root: Optional root node (will explore only root's connected component) + + @rtype: tuple + @return: tupple containing a dictionary and two lists: + 1. Generated spanning tree + 2. Graph's preordering + 3. Graph's postordering + """ + return searching.depth_first_search(self, root) + + + def breadth_first_search(self, root=None): + """ + Breadth-first search. + + @type root: node + @param root: Optional root node (will explore only root's connected component) + + @rtype: dictionary + @return: A tuple containing a dictionary and a list. + 1. Generated spanning tree + 2. Graph's level-based ordering + """ + return searching.breadth_first_search(self, root) + + + def accessibility(self): + """ + Accessibility matrix (transitive closure). + + @rtype: dictionary + @return: Accessibility information for each node. + """ + return accessibility.accessibility(self) + + + def connected_components(self): + """ + Connected components. + + @attention: Indentification of connected components is meaningful only for non-directed + graphs. + + @rtype: dictionary + @return: Pairing that associates each node to its connected component. + """ + return accessibility.connected_components(self) + + + def minimal_spanning_tree(self, root=None): + """ + Minimal spanning tree. + + @type root: node + @param root: Optional root node (will explore only root's connected component) + + @attention: Minimal spanning tree meaningful only for weighted graphs. + + @rtype: list + @return: Generated spanning tree. + """ + return minmax.minimal_spanning_tree(self, root) + + + def shortest_path(self, source): + """ + Return the shortest path distance between source node and all other nodes using Dijkstra's + algorithm. + + @attention: All weights must be nonnegative. + + @type source: node + @param source: Node from which to start the search. + + @rtype: tuple + @return: A tuple containing two dictionaries, each keyed by target nodes. + 1. Shortest path spanning tree + 2. Shortest distance from given source to each target node + Inaccessible target nodes do not appear in either dictionary. + """ + return minmax.shortest_path(self, source) + + + def cut_edges(self): + """ + Return the cut-edges of the given graph. + + @rtype: list + @return: List of cut-edges. + """ + return accessibility.cut_edges(self) + + + def cut_nodes(self): + """ + Return the cut-nodes of the given graph. + + @rtype: list + @return: List of cut-nodes. + """ + return accessibility.cut_nodes(self) + + +# Digraph class ------------------------------------------------------------------------------------ + +class digraph (object): + """ + Digraph class. + + Digraphs are built of nodes and directed edges. + + @sort: __init__, __getitem__, __iter__, __len__, __str__, add_edge, add_edge_attribute, + add_graph, add_node, add_node_attribute, add_nodes, add_spanning_tree, complete, degree, + del_edge, del_node, edges, get_edge_attributes, get_edge_label, get_edge_weight, + get_node_attributes, has_edge, has_node, incidents, inverse, neighbors, nodes, order, + set_edge_label, set_edge_weight, traversal, generate, read, write, accessibility, + breadth_first_search, cut_edges, cut_nodes, depth_first_search, minimal_spanning_tree, + mutual_accessibility, shortest_path, topological_sorting + """ + + + def __init__(self): + """ + Initialize a digraph. + """ + self.node_neighbors = {} # Pairing: Node -> Neighbors + self.edge_properties = {} # Pairing: Edge -> (Label, Weight) + self.node_incidence = {} # Pairing: Node -> Incident nodes + self.node_attr = {} # Pairing: Node -> Attributes + self.edge_attr = {} # Pairing: Edge -> Attributes + + + def __str__(self): + """ + Return a string representing the digraph when requested by str() (or print). + + @rtype: string + @return: String representing the graph. + """ + return "" + + + def __len__(self): + """ + Return the order of the digraph when requested by len(). + + @rtype: number + @return: Size of the graph. + """ + return len(self.node_neighbors) + + + def __iter__(self): + """ + Return a iterator passing through all nodes in the digraph. + + @rtype: iterator + @return: Iterator passing through all nodes in the digraph. + """ + for each in self.node_neighbors.iterkeys(): + yield each + + + def __getitem__(self, node): + """ + Return a iterator passing through all neighbors of the given node. + + @rtype: iterator + @return: Iterator passing through all neighbors of the given node. + """ + for each in self.node_neighbors[node]: + yield each + + + def read(self, string, fmt='xml'): + """ + Read a graph from a string. Nodes and edges specified in the input will be added to the + current graph. + + @type string: string + @param string: Input string specifying a graph. + + @type fmt: string + @param fmt: Input format. Possible formats are: + 1. 'xml' - XML (default) + """ + if (fmt == 'xml'): + readwrite.read_xml(self, string) + + + def write(self, fmt='xml'): + """ + Write the graph to a string. Depending of the output format, this string can be used by + read() to rebuild the graph. + + @type fmt: string + @param fmt: Output format. Possible formats are: + 1. 'xml' - XML (default) + 2. 'dot' - DOT Language (for GraphViz) + 3. 'dotwt' - DOT Language with weight information + + @rtype: string + @return: String specifying the graph. + """ + if (fmt == 'xml'): + return readwrite.write_xml(self) + elif (fmt == 'dot'): + return readwrite.write_dot_digraph(self, False) + elif (fmt == 'dotwt'): + return readwrite.write_dot_digraph(self, True) + + + def generate(self, num_nodes, num_edges, weight_range=(1, 1)): + """ + Add nodes and random edges to the graph. + + @type num_nodes: number + @param num_nodes: Number of nodes. + + @type num_edges: number + @param num_edges: Number of edges. + + @type weight_range: tuple + @param weight_range: tuple of two integers as lower and upper limits on randomly generated + weights (uniform distribution). + """ + generators.generate(self, num_nodes, num_edges, weight_range) + + + def nodes(self): + """ + Return node list. + + @rtype: list + @return: Node list. + """ + return self.node_neighbors.keys() + + + def neighbors(self, node): + """ + Return all nodes that are directly accessible from given node. + + @type node: node + @param node: Node identifier + + @rtype: list + @return: List of nodes directly accessible from given node. + """ + return self.node_neighbors[node] + + + def incidents(self, node): + """ + Return all nodes that are incident to the given node. + + @type node: node + @param node: Node identifier + + @rtype: list + @return: List of nodes directly accessible from given node. + """ + return self.node_incidence[node] + + + + def edges(self): + """ + Return all edges in the graph. + + @rtype: list + @return: List of all edges in the graph. + """ + return self.edge_properties.keys() + + + def has_node(self, node): + """ + Return whether the requested node exists. + + @type node: node + @param node: Node identifier + + @rtype: boolean + @return: Truth-value for node existence. + """ + return self.node_neighbors.has_key(node) + + + def add_node(self, node, attrs=[]): + """ + Add given node to the graph. + + @attention: While nodes can be of any type, it's strongly recommended to use only numbers + and single-line strings as node identifiers if you intend to use write(). + + @type node: node + @param node: Node identifier. + + @type attrs: list + @param attrs: List of node attributes specified as (attribute, value) tuples. + """ + if (node not in self.node_neighbors): + self.node_neighbors[node] = [] + self.node_incidence[node] = [] + self.node_attr[node] = attrs + + + def add_nodes(self, nodelist): + """ + Add given nodes to the graph. + + @attention: While nodes can be of any type, it's strongly recommended to use only numbers + and single-line strings as node identifiers if you intend to use write(). + + @type nodelist: list + @param nodelist: List of nodes to be added to the graph. + """ + for each in nodelist: + self.add_node(each) + + + def add_edge(self, u, v, wt=1, label='', attrs=[]): + """ + Add an directed edge (u,v) to the graph connecting nodes u to v. + + @type u: node + @param u: One node. + + @type v: node + @param v: Other node. + + @type wt: number + @param wt: Edge weight. + + @type label: string + @param label: Edge label. + + @type attrs: list + @param attrs: List of node attributes specified as (attribute, value) tuples. + """ + if (v not in self.node_neighbors[u]): + self.node_neighbors[u].append(v) + self.node_incidence[v].append(u) + self.edge_properties[(u, v)] = [label, wt] + self.edge_attr[(u, v)] = attrs + + + def del_node(self, node): + """ + Remove a node from the graph. + + @type node: node + @param node: Node identifier. + """ + for each in list(self.incidents(node)): + self.del_edge(each, node) + for each in list(self.neighbors(node)): + self.del_edge(node, each) + del(self.node_neighbors[node]) + del(self.node_incidence[node]) + del(self.node_attr[node]) + + + def del_edge(self, u, v): + """ + Remove an directed edge (u, v) from the graph. + + @type u: node + @param u: One node. + + @type v: node + @param v: Other node. + """ + self.node_neighbors[u].remove(v) + self.node_incidence[v].remove(u) + del(self.edge_properties[(u,v)]) + del(self.edge_attr[(u,v)]) + + + def get_edge_weight(self, u, v): + """ + Get the weight of an edge. + + @type u: node + @param u: One node. + + @type v: node + @param v: Other node. + + @rtype: number + @return: Edge weight. + """ + return self.edge_properties[(u, v)][1] + + + def set_edge_weight(self, u, v, wt): + """ + Set the weight of an edge. + + @type u: node + @param u: One node. + + @type v: node + @param v: Other node. + + @type wt: number + @param wt: Edge weight. + """ + self.edge_properties[(u, v)][1] = wt + + + def get_edge_label(self, u, v): + """ + Get the label of an edge. + + @type u: node + @param u: One node. + + @type v: node + @param v: Other node. + + @rtype: string + @return: Edge label + """ + return self.edge_properties[(u, v)][0] + + + def set_edge_label(self, u, v, label): + """ + Set the label of an edge. + + @type u: node + @param u: One node. + + @type v: node + @param v: Other node. + + @type label: string + @param label: Edge label. + """ + self.edge_properties[(u, v)][0] = label + + + def add_node_attribute(self, node, attr): + """ + Add attribute to the given node. + + @type node: node + @param node: Node identifier + + @type attr: tuple + @param attr: Node attribute specified as a tuple in the form (attribute, value). + """ + self.node_attr[node] = self.node_attr[node] + [attr] + + + def get_node_attributes(self, node): + """ + Return the attributes of the given node. + + @type node: node + @param node: Node identifier + + @rtype: list + @return: List of attributes specified tuples in the form (attribute, value). + """ + return self.node_attr[node] + + + def add_edge_attribute(self, u, v, attr): + """ + Add attribute to the given edge. + + @type u: node + @param u: One node. + + @type v: node + @param v: Other node. + + @type attr: tuple + @param attr: Node attribute specified as a tuple in the form (attribute, value). + """ + self.edge_attr[(u,v)] = self.edge_attr[(u,v)] + [attr] + + + def get_edge_attributes(self, u, v): + """ + Return the attributes of the given edge. + + @type u: node + @param u: One node. + + @type v: node + @param v: Other node. + + @rtype: list + @return: List of attributes specified tuples in the form (attribute, value). + """ + return self.edge_attr[(u,v)] + + + def has_edge(self, u, v): + """ + Return whether an edge between nodes u and v exists. + + @type u: node + @param u: One node. + + @type v: node + @param v: Other node. + + @rtype: boolean + @return: Truth-value for edge existence. + """ + return self.edge_properties.has_key((u,v)) + + + def order(self, node): + """ + Return the order of the given node. + + @rtype: number + @return: Order of the given node. + """ + return len(self.neighbors(node)) + + + def degree(self, node): + """ + Return the degree of the given node. + + @rtype: number + @return: Order of the given node. + """ + return len(self.node_incidence[node]) + + + def complete(self): + """ + Make the graph a complete graph. + + @attention: This will modify the current graph. + """ + for each in self.nodes(): + for other in self.nodes(): + if (each != other): + self.add_edge(each, other) + + + def inverse(self): + """ + Return the inverse of the graph. + + @rtype: graph + @return: Complement graph for the graph. + """ + inv = digraph() + inv.add_nodes(self.nodes()) + inv.complete() + for each in self.edges(): + inv.del_edge(each[0], each[1]) + return inv + + + def add_graph(self, graph): + """ + Add other graph to the graph. + + @attention: Attributes and labels are not preserved. + + @type graph: graph + @param graph: Graph + """ + self.add_nodes(graph.nodes()) + for each_node in graph.nodes(): + for each_edge in graph.neighbors(each_node): + self.add_edge(each_node, each_edge) + + + def add_spanning_tree(self, st): + """ + Add a spanning tree to the graph. + + @type st: dictionary + @param st: Spanning tree. + """ + self.add_nodes(st.keys()) + for each in st: + if (st[each] is not None): + self.add_edge(st[each], each) + + + def traversal(self, node, order='pre'): + """ + Graph traversal iterator. + + @type node: node + @param node: Node. + + @type order: string + @param order: traversal ordering. Possible values are: + 2. 'pre' - Preordering (default) + 1. 'post' - Postordering + + @rtype: iterator + @return: Traversal iterator. + """ + for each in traversal.traversal(self, node, order): + yield each + + + def depth_first_search(self, root=None): + """ + Depht-first search. + + @type root: node + @param root: Optional root node (will explore only root's connected component) + + @rtype: tuple + @return: tupple containing a dictionary and two lists: + 1. Generated spanning tree + 2. Graph's preordering + 3. Graph's postordering + """ + return searching.depth_first_search(self, root) + + + def accessibility(self): + """ + Accessibility matrix (transitive closure). + + @rtype: dictionary + @return: Accessibility information for each node. + """ + return accessibility.accessibility(self) + + + def breadth_first_search(self, root=None): + """ + Breadth-first search. + + @type root: node + @param root: Optional root node (will explore only root's connected component) + + @rtype: dictionary + @return: A tuple containing a dictionary and a list. + 1. Generated spanning tree + 2. Graph's level-based ordering + """ + return searching.breadth_first_search(self, root) + + + def mutual_accessibility(self): + """ + Mutual-accessibility matrix (strongly connected components). + + @rtype: list + @return: Mutual-accessibility information for each node. + """ + return accessibility.mutual_accessibility(self) + + + def topological_sorting(self): + """ + Topological sorting. + + @attention: Topological sorting is meaningful only for directed acyclic graphs. + + @rtype: list + @return: Topological sorting for the graph. + """ + return sorting.topological_sorting(self) + + + def minimal_spanning_tree(self, root=None): + """ + Minimal spanning tree. + + @type root: node + @param root: Optional root node (will explore only root's connected component) + + @attention: Minimal spanning tree meaningful only for weighted graphs. + + @rtype: list + @return: Generated spanning tree. + """ + return minmax.minimal_spanning_tree(self, root) + + + def shortest_path(self, source): + """ + Return the shortest path distance between source node and all other nodes using Dijkstra's + algorithm. + + @attention: All weights must be nonnegative. + + @type source: node + @param source: Node from which to start the search. + + @rtype: tuple + @return: A tuple containing two dictionaries, each keyed by target nodes. + 1. Shortest path spanning tree + 2. Shortest distance from given source to each target node + Inaccessible target nodes do not appear in either dictionary. + """ + return minmax.shortest_path(self, source) + + + def cut_edges(self): + """ + Return the cut-edges of the given graph. + + @rtype: list + @return: List of cut-edges. + """ + return accessibility.cut_edges(self) + + + def cut_nodes(self): + """ + Return the cut-nodes of the given graph. + + @rtype: list + @return: List of cut-nodes. + """ + return accessibility.cut_nodes(self) + + +# Hypergraph class --------------------------------------------------------------------------------- + +class hypergraph (object): + """ + Hypergraph class. + + Hypergraphs are a generalization of graphs where an edge (called hyperedge) can connect more + than two nodes. + + @sort: __init__, __len__, __str__, add_hyperedge, add_hyperedges, add_node, add_nodes, has_node, + hyperedges, link, links, nodes, unlink, read, write, accessibility, connected_components, + cut_hyperedges, cut_nodes + """ + + + def __init__(self): + """ + Initialize a hypergraph. + """ + self.node_links = {} # Pairing: Node -> Hyperedge + self.edge_links = {} # Pairing: Hyperedge -> Node + self.graph = graph() # Ordinary graph + + + def __str__(self): + """ + Return a string representing the hypergraph when requested by str() (or print). + + @rtype: string + @return: String representing the hypergraph. + """ + return "" + + + def __len__(self): + """ + Return the size of the hypergraph when requested by len(). + + @rtype: number + @return: Size of the hypergraph. + """ + return len(self.node_links) + + + def read(self, string, fmt='xml'): + """ + Read a hypergraph from a string. Nodes and hyperedges specified in the input will be added + to the current graph. + + @type string: string + @param string: Input string specifying a graph. + + @type fmt: string + @param fmt: Input format. Possible formats are: + 1. 'xml' - XML (default) + """ + if (fmt == 'xml'): + readwrite.read_xml_hypergraph(self, string) + + + def write(self, fmt='xml'): + """ + Write the hypergraph to a string. Depending of the output format, this string can be used by + read() to rebuild the graph. + + @type fmt: string + @param fmt: Output format. Possible formats are: + 1. 'xml' - XML (default) + 2. 'dot' - DOT Language (for GraphViz) + 3. 'dotclr' - DOT Language, coloured + + @rtype: string + @return: String specifying the graph. + """ + if (fmt == 'xml'): + return readwrite.write_xml_hypergraph(self) + elif (fmt == 'dot'): + return readwrite.write_dot_hypergraph(self) + elif (fmt == 'dotclr'): + return readwrite.write_dot_hypergraph(self, coloured=True) + + + def nodes(self): + """ + Return node list. + + @rtype: list + @return: Node list. + """ + return self.node_links.keys() + + + def hyperedges(self): + """ + Return hyperedge list. + + @rtype: list + @return: List of hyperedges linked to the given node. + """ + return self.edge_links.keys() + + + def links(self, obj): + """ + Return all objects linked to the given one. + + If given a node, linked hyperedges will be returned. If given a hyperedge, linked nodes will + be returned. + + @type obj: node or hyperedge + @param obj: Object identifier. + + @rtype: list + @return: List of objects linked to the given one. + """ + if (obj in self.node_links): + return self.node_links[obj] + else: + return self.edge_links[obj] + + + def has_node(self, node): + """ + Return whether the requested node exists. + + @type node: node + @param node: Node identifier + + @rtype: boolean + @return: Truth-value for node existence. + """ + return self.node_links.has_key(node) + + + def add_node(self, node): + """ + Add given node to the hypergraph. + + @attention: While nodes can be of any type, it's strongly recommended to use only numbers + and single-line strings as node identifiers if you intend to use write(). + + @type node: node + @param node: Node identifier. + """ + if (not node in self.node_links): + self.node_links[node] = [] + self.graph.add_node((node,'n')) + + + def add_nodes(self, nodelist): + """ + Add given nodes to the hypergraph. + + @attention: While nodes can be of any type, it's strongly recommended to use only numbers + and single-line strings as node identifiers if you intend to use write(). + + @type nodelist: list + @param nodelist: List of nodes to be added to the graph. + """ + for each in nodelist: + self.add_node(each) + + + def add_hyperedge(self, hyperedge): + """ + Add given hyperedge to the hypergraph. + + @attention: While hyperedge-nodes can be of any type, it's strongly recommended to use only + numbers and single-line strings as node identifiers if you intend to use write(). + + @type hyperedge: hyperedge + @param hyperedge: Hyperedge identifier. + """ + if (not hyperedge in self.edge_links): + self.edge_links[hyperedge] = [] + self.graph.add_node((hyperedge,'h')) + + + def add_hyperedges(self, edgelist): + """ + Add given hyperedges to the hypergraph. + + @attention: While hyperedge-nodes can be of any type, it's strongly recommended to use only + numbers and single-line strings as node identifiers if you intend to use write(). + + @type edgelist: list + @param edgelist: List of hyperedge-nodes to be added to the graph. + """ + for each in edgelist: + self.add_hyperedge(each) + + + def link(self, node, hyperedge): + """ + Link given node and hyperedge. + + @type node: node + @param node: Node. + + @type hyperedge: node + @param hyperedge: Hyperedge. + """ + if (hyperedge not in self.node_links[node]): + self.node_links[node].append(hyperedge) + self.edge_links[hyperedge].append(node) + self.graph.add_edge((node,'n'), (hyperedge,'h')) + + + def unlink(self, node, hyperedge): + """ + Unlink given node and hyperedge. + + @type node: node + @param node: Node. + + @type hyperedge: hyperedge + @param hyperedge: Hyperedge. + """ + self.node_links[node].remove(hyperedge) + self.edge_links[hyperedge].remove(node) + + + def accessibility(self): + """ + Accessibility matrix (transitive closure). + + @rtype: dictionary + @return: Accessibility information for each node. + """ + access_ = accessibility.accessibility(self.graph) + access = {} + + for each in access_.keys(): + if (each[1] == 'n'): + access[each[0]] = [] + for other in access_[each]: + if (other[1] == 'n'): + access[each[0]].append(other[0]) + + return access + + + def connected_components(self): + """ + Connected components. + + @rtype: dictionary + @return: Pairing that associates each node to its connected component. + """ + components_ = accessibility.connected_components(self.graph) + components = {} + + for each in components_.keys(): + if (each[1] == 'n'): + components[each[0]] = components_[each] + + return components + + + def cut_nodes(self): + """ + Return the cut-nodes of the given hypergraph. + + @rtype: list + @return: List of cut-nodes. + """ + cut_nodes_ = accessibility.cut_nodes(self.graph) + cut_nodes = [] + + for each in cut_nodes_: + if (each[1] == 'n'): + cut_nodes.append(each[0]) + + return cut_nodes + + + def cut_hyperedges(self): + """ + Return the cut-hyperedges of the given hypergraph. + + @rtype: list + @return: List of cut-nodes. + """ + cut_nodes_ = accessibility.cut_nodes(self.graph) + cut_nodes = [] + + for each in cut_nodes_: + if (each[1] == 'h'): + cut_nodes.append(each[0]) + + return cut_nodes + + def rank(self): + """ + Return the rank of the given hypergraph. + + @rtype: int + @return: Rank of graph. + """ + max_rank = 0 + + for each in hyperedges: + if len(each) > max_rank: + max_rank = len(each) + + return max_rank diff -r c1f9435bb645 -r 32a30f609530 scripts/graph/accessibility.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/scripts/graph/accessibility.py Thu Nov 27 23:41:08 2008 +0000 @@ -0,0 +1,228 @@ +# Copyright (c) 2007-2008 Pedro Matiello +# +# Permission is hereby granted, free of charge, to any person +# obtaining a copy of this software and associated documentation +# files (the "Software"), to deal in the Software without +# restriction, including without limitation the rights to use, +# copy, modify, merge, publish, distribute, sublicense, and/or sell +# copies of the Software, and to permit persons to whom the +# Software is furnished to do so, subject to the following +# conditions: + +# The above copyright notice and this permission notice shall be +# included in all copies or substantial portions of the Software. + +# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES +# OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND +# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT +# HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, +# WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR +# OTHER DEALINGS IN THE SOFTWARE. + + +""" +Accessibility algorithms for python-graph. + +@sort: accessibility, connected_components, cut_edges, cut_nodes, mutual_accessibility +""" + + +# Transitive-closure + +def accessibility(graph): + """ + Accessibility matrix (transitive closure). + + @type graph: graph + @param graph: Graph. + + @rtype: dictionary + @return: Accessibility information for each node. + """ + accessibility = {} # Accessibility matrix + + # For each node i, mark each node j if that exists a path from i to j. + for each in graph: + access = {} + # Perform DFS to explore all reachable nodes + _dfs(graph, access, 1, each) + accessibility[each] = access.keys() + return accessibility + + +# Strongly connected components + +def mutual_accessibility(graph): + """ + Mutual-accessibility matrix (strongly connected components). + + @type graph: graph + @param graph: Graph. + + @rtype: dictionary + @return: Mutual-accessibility information for each node. + """ + mutual_access = {} + access = graph.accessibility() + + for i in graph: + mutual_access[i] = [] + for j in graph: + if (i in access[j] and j in access[i]): + mutual_access[i].append(j) + + return mutual_access + + +# Connected components + +def connected_components(graph): + """ + Connected components. + + @attention: Indentification of connected components is meaningful only for non-directed graphs. + + @type graph: graph + @param graph: Graph. + + @rtype: dictionary + @return: Pairing that associates each node to its connected component. + """ + visited = {} + count = 1 + + # For 'each' node not found to belong to a connected component, find its connected component. + for each in graph: + if (each not in visited): + _dfs(graph, visited, count, each) + count = count + 1 + + return visited + + +# Limited DFS implementations used by algorithms here + +def _dfs(graph, visited, count, node): + """ + Depht-first search subfunction adapted for accessibility algorithms. + + @type graph: graph + @param graph: Graph. + + @type visited: dictionary + @param visited: List of nodes (visited nodes are marked non-zero). + + @type count: number + @param count: Counter of connected components. + + @type node: number + @param node: Node to be explored by DFS. + """ + visited[node] = count + # Explore recursively the connected component + for each in graph[node]: + if (each not in visited): + _dfs(graph, visited, count, each) + + +# Cut-Edge and Cut-Vertex identification + +def cut_edges(graph): + """ + Return the cut-edges of the given graph. + + @rtype: list + @return: List of cut-edges. + """ + pre = {} + low = {} + spanning_tree = {} + reply = [] + pre[None] = 0 + + for each in graph: + if (not pre.has_key(each)): + spanning_tree[each] = None + _cut_dfs(graph, spanning_tree, pre, low, reply, each) + return reply + + +def cut_nodes(graph): + """ + Return the cut-nodes of the given graph. + + @rtype: list + @return: List of cut-nodes. + """ + pre = {} # Pre-ordering + low = {} # Lowest pre[] reachable from this node going down the spanning tree + one backedge + reply = {} + spanning_tree = {} + pre[None] = 0 + + # Create spanning trees, calculate pre[], low[] + for each in graph: + if (not pre.has_key(each)): + spanning_tree[each] = None + _cut_dfs(graph, spanning_tree, pre, low, [], each) + + # Find cuts + for each in graph: + # If node is not a root + if (spanning_tree[each] is not None): + for other in graph[each]: + # If there is no back-edge from descendent to a ancestral of each + if (low[other] >= pre[each] and spanning_tree[other] == each): + reply[each] = 1 + # If node is a root + else: + children = 0 + for other in graph: + if (spanning_tree[other] == each): + children = children + 1 + # root is cut-vertex iff it has two or more children + if (children >= 2): + reply[each] = 1 + + return reply.keys() + + +def _cut_dfs(graph, spanning_tree, pre, low, reply, node): + """ + Depth first search adapted for identification of cut-edges and cut-nodes. + + @type graph: graph + @param graph: Graph + + @type spanning_tree: dictionary + @param spanning_tree: Spanning tree being built for the graph by DFS. + + @type pre: dictionary + @param pre: Graph's preordering. + + @type low: dictionary + @param low: Associates to each node, the preordering index of the node of lowest preordering + accessible from the given node. + + @type reply: list + @param reply: List of cut-edges. + + @type node: node + @param node: Node to be explored by DFS. + """ + pre[node] = pre[None] + low[node] = pre[None] + pre[None] = pre[None] + 1 + + for each in graph[node]: + if (not pre.has_key(each)): + spanning_tree[each] = node + _cut_dfs(graph, spanning_tree, pre, low, reply, each) + if (low[node] > low[each]): + low[node] = low[each] + if (low[each] == pre[each]): + reply.append((node, each)) + elif (low[node] > pre[each] and spanning_tree[node] != each): + low[node] = pre[each] diff -r c1f9435bb645 -r 32a30f609530 scripts/graph/generators.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/scripts/graph/generators.py Thu Nov 27 23:41:08 2008 +0000 @@ -0,0 +1,82 @@ +# Copyright (c) 2007-2008 Pedro Matiello +# Zsolt Haraszti +# +# Permission is hereby granted, free of charge, to any person +# obtaining a copy of this software and associated documentation +# files (the "Software"), to deal in the Software without +# restriction, including without limitation the rights to use, +# copy, modify, merge, publish, distribute, sublicense, and/or sell +# copies of the Software, and to permit persons to whom the +# Software is furnished to do so, subject to the following +# conditions: + +# The above copyright notice and this permission notice shall be +# included in all copies or substantial portions of the Software. + +# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES +# OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND +# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT +# HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, +# WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR +# OTHER DEALINGS IN THE SOFTWARE. + + +""" +Random graph generators for python-graph. + +@sort: generate +""" + + +# Imports +import graph as classes +from random import randint + + +# Generator + +def generate(graph, num_nodes, num_edges, weight_range=(1, 1)): + """ + Add nodes and random edges to the graph. + + @type graph: graph + @param graph: Graph. + + @type num_nodes: number + @param num_nodes: Number of nodes. + + @type num_edges: number + @param num_edges: Number of edges. + + @type weight_range: tuple + @param weight_range: tuple of two integers as lower and upper limits on randomly generated + weights (uniform distribution). + """ + # Discover if graph is directed or not + directed = (type(graph) == classes.digraph) + + # Nodes first + nodes = xrange(num_nodes) + graph.add_nodes(nodes) + + # Build a list of all possible edges + edges = [] + edges_append = edges.append + for x in nodes: + for y in nodes: + if ((directed and x != y) or (x > y)): + edges_append((x, y)) + + # Randomize the list + for i in xrange(len(edges)): + r = randint(0, len(edges)-1) + edges[i], edges[r] = edges[r], edges[i] + + # Add edges to the graph + min_wt = min(weight_range) + max_wt = max(weight_range) + for i in xrange(num_edges): + each = edges[i] + graph.add_edge(each[0], each[1], wt = randint(min_wt, max_wt)) diff -r c1f9435bb645 -r 32a30f609530 scripts/graph/minmax.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/scripts/graph/minmax.py Thu Nov 27 23:41:08 2008 +0000 @@ -0,0 +1,168 @@ +# Copyright (c) 2007-2008 Pedro Matiello +# Rhys Ulerich +# +# Permission is hereby granted, free of charge, to any person +# obtaining a copy of this software and associated documentation +# files (the "Software"), to deal in the Software without +# restriction, including without limitation the rights to use, +# copy, modify, merge, publish, distribute, sublicense, and/or sell +# copies of the Software, and to permit persons to whom the +# Software is furnished to do so, subject to the following +# conditions: + +# The above copyright notice and this permission notice shall be +# included in all copies or substantial portions of the Software. + +# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES +# OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND +# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT +# HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, +# WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR +# OTHER DEALINGS IN THE SOFTWARE. + + +""" +Minimization and maximization algorithms for python-graph. + +@sort: minimal_spanning_tree, shortest_path, _first_unvisited, _lightest_edge +""" + + +# Minimal spanning tree + +def minimal_spanning_tree(graph, root=None): + """ + Minimal spanning tree. + + @attention: Minimal spanning tree meaningful only for weighted graphs. + + @type graph: graph + @param graph: Graph. + + @type root: node + @param root: Optional root node (will explore only root's connected component) + + @rtype: dictionary + @return: Generated spanning tree. + """ + visited = [] # List for marking visited and non-visited nodes + spanning_tree = {} # MInimal Spanning tree + + # Initialization + if (root is not None): + visited.append(root) + nroot = root + spanning_tree[root] = None + else: + nroot = 1 + + # Algorithm loop + while (nroot is not None): + ledge = _lightest_edge(graph, visited) + if (ledge == (-1, -1)): + if (root is not None): + break + nroot = _first_unvisited(graph, visited) + if (nroot is not None): + spanning_tree[nroot] = None + visited.append(nroot) + else: + spanning_tree[ledge[1]] = ledge[0] + visited.append(ledge[1]) + + return spanning_tree + + +def _first_unvisited(graph, visited): + """ + Return first unvisited node. + + @type graph: graph + @param graph: Graph. + + @type visited: list + @param visited: List of nodes. + + @rtype: node + @return: First unvisited node. + """ + for each in graph: + if (each not in visited): + return each + return None + + +def _lightest_edge(graph, visited): + """ + Return the lightest edge in graph going from a visited node to an unvisited one. + + @type graph: graph + @param graph: Graph. + + @type visited: list + @param visited: List of nodes. + + @rtype: tuple + @return: Lightest edge in graph going from a visited node to an unvisited one. + """ + lightest_edge = (-1, -1) + weight = -1 + for each in visited: + for other in graph[each]: + if (other not in visited): + w = graph.get_edge_weight(each, other) + if (w < weight or weight < 0): + lightest_edge = (each, other) + weight = w + return lightest_edge + + +# Shortest Path +# Code donated by Rhys Ulerich + +def shortest_path(graph, source): + """ + Return the shortest path distance between source and all other nodes using Dijkstra's algorithm. + + @attention: All weights must be nonnegative. + + @type graph: graph + @param graph: Graph. + + @type source: node + @param source: Node from which to start the search. + + @rtype: tuple + @return: A tuple containing two dictionaries, each keyed by target nodes. + 1. Shortest path spanning tree + 2. Shortest distance from given source to each target node + Inaccessible target nodes do not appear in either dictionary. + """ + # Initialization + dist = { source: 0 } + previous = { source: None} + q = graph.nodes() + + # Algorithm loop + while q: + # examine_min process performed using O(nodes) pass here. + # May be improved using another examine_min data structure. + u = q[0] + for node in q[1:]: + if ((not dist.has_key(u)) + or (dist.has_key(node) and dist[node] < dist[u])): + u = node + q.remove(u) + + # Process reachable, remaining nodes from u + if (dist.has_key(u)): + for v in graph[u]: + if v in q: + alt = dist[u] + graph.get_edge_weight(u, v) + if (not dist.has_key(v)) or (alt < dist[v]): + dist[v] = alt + previous[v] = u + + return previous, dist diff -r c1f9435bb645 -r 32a30f609530 scripts/graph/readwrite.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/scripts/graph/readwrite.py Thu Nov 27 23:41:08 2008 +0000 @@ -0,0 +1,302 @@ +# Copyright (c) 2007-2008 Pedro Matiello +# +# Permission is hereby granted, free of charge, to any person +# obtaining a copy of this software and associated documentation +# files (the "Software"), to deal in the Software without +# restriction, including without limitation the rights to use, +# copy, modify, merge, publish, distribute, sublicense, and/or sell +# copies of the Software, and to permit persons to whom the +# Software is furnished to do so, subject to the following +# conditions: + +# The above copyright notice and this permission notice shall be +# included in all copies or substantial portions of the Software. + +# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES +# OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND +# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT +# HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, +# WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR +# OTHER DEALINGS IN THE SOFTWARE. + + +""" +Functions for reading and writing graphs. + +@sort: read_xml, write_xml, write_dot_graph, write_dot_digraph, write_dot_hypergraph +""" + + +# Imports +from xml.dom.minidom import Document, parseString + + +# Values +colors = ['aquamarine4', 'blue4', 'brown4', 'cornflowerblue', 'cyan4', + 'darkgreen', 'darkorange3', 'darkorchid4', 'darkseagreen4', 'darkslategray', + 'deeppink4', 'deepskyblue4', 'firebrick3', 'hotpink3', 'indianred3', + 'indigo', 'lightblue4', 'lightseagreen', 'lightskyblue4', 'magenta4', + 'maroon', 'palevioletred3', 'steelblue', 'violetred3'] + + +# XML + +def write_xml(graph): + """ + Return a string specifying the given graph as a XML document. + + @type graph: graph + @param graph: Graph. + + @rtype: string + @return: String specifying the graph as a XML document. + """ + + # Document root + grxml = Document() + grxmlr = grxml.createElement('graph') + grxml.appendChild(grxmlr) + + # Each node... + for each_node in graph.nodes(): + node = grxml.createElement('node') + node.setAttribute('id',str(each_node)) + grxmlr.appendChild(node) + for each_attr in graph.get_node_attributes(each_node): + attr = grxml.createElement('attribute') + attr.setAttribute('attr', each_attr[0]) + attr.setAttribute('value', each_attr[1]) + node.appendChild(attr) + + # Each edge... + for edge_from, edge_to in graph.edges(): + edge = grxml.createElement('edge') + edge.setAttribute('from',str(edge_from)) + edge.setAttribute('to',str(edge_to)) + edge.setAttribute('wt',str(graph.get_edge_weight(edge_from, edge_to))) + edge.setAttribute('label',str(graph.get_edge_label(edge_from, edge_to))) + grxmlr.appendChild(edge) + for attr_name, attr_value in graph.get_edge_attributes(edge_from, edge_to): + attr = grxml.createElement('attribute') + attr.setAttribute('attr', attr_name) + attr.setAttribute('value', attr_value) + edge.appendChild(attr) + + return grxml.toprettyxml() + + +def write_xml_hypergraph(hypergraph): + """ + Return a string specifying the given hypergraph as a XML document. + + @type hypergraph: hypergraph + @param hypergraph: Hypergraph. + + @rtype: string + @return: String specifying the graph as a XML document. + """ + + # Document root + grxml = Document() + grxmlr = grxml.createElement('hypergraph') + grxml.appendChild(grxmlr) + + # Each node... + nodes = hypergraph.nodes() + hyperedges = hypergraph.get_hyperedges() + for each_node in (nodes + hyperedges): + if (each_node in nodes): + node = grxml.createElement('node') + else: + node = grxml.createElement('hyperedge') + node.setAttribute('id',str(each_node)) + grxmlr.appendChild(node) + + # and its outgoing edge + for each_edge in hypergraph.get_links(each_node): + edge = grxml.createElement('link') + edge.setAttribute('to',str(each_edge)) + node.appendChild(edge) + + return grxml.toprettyxml() + + +def read_xml(graph, string): + """ + Read a graph from a XML document. Nodes and edges specified in the input will be added to the current graph. + + @type graph: graph + @param graph: Graph + + @type string: string + @param string: Input string in XML format specifying a graph. + """ + dom = parseString(string) + + # Read nodes... + for each_node in dom.getElementsByTagName("node"): + graph.add_node(each_node.getAttribute('id')) + for each_attr in each_node.getElementsByTagName("attribute"): + graph.add_node_attribute(each_node.getAttribute('id'), (each_attr.getAttribute('attr'), + each_attr.getAttribute('value'))) + + # Read edges... + for each_edge in dom.getElementsByTagName("edge"): + graph.add_edge(each_edge.getAttribute('from'), each_edge.getAttribute('to'), \ + wt=float(each_edge.getAttribute('wt')), label=each_edge.getAttribute('label')) + for each_attr in each_edge.getElementsByTagName("attribute"): + attr_tuple = (each_attr.getAttribute('attr'), each_attr.getAttribute('value')) + if (attr_tuple not in graph.get_edge_attributes(each_edge.getAttribute('from'), \ + each_edge.getAttribute('to'))): + graph.add_edge_attribute(each_edge.getAttribute('from'), \ + each_edge.getAttribute('to'), attr_tuple) + + +def read_xml_hypergraph(hypergraph, string): + """ + Read a graph from a XML document. Nodes and hyperedges specified in the input will be added to the current graph. + + @type hypergraph: hypergraph + @param hypergraph: Hypergraph + + @type string: string + @param string: Input string in XML format specifying a graph. + """ + dom = parseString(string) + for each_node in dom.getElementsByTagName("node"): + hypergraph.add_nodes(each_node.getAttribute('id')) + for each_node in dom.getElementsByTagName("hyperedge"): + hypergraph.add_hyperedges(each_node.getAttribute('id')) + dom = parseString(string) + for each_node in dom.getElementsByTagName("node"): + for each_edge in each_node.getElementsByTagName("link"): + hypergraph.link(each_node.getAttribute('id'), each_edge.getAttribute('to')) + + +# DOT Language + +def _dot_node_str(graph, node, wt): + line = '\t"%s" [ ' % str(node) + attrlist = graph.get_node_attributes(node) + for each in attrlist: + attr = '%s="%s" ' % (each[0], each[1]) + line = line + attr + line = line + ']\n' + return line + + +def _dot_edge_str(graph, u, v, wt): + line = '\t"%s" -- "%s" [ ' % (str(u), str(v)) + attrlist = graph.get_edge_attributes(u, v) + [('label',graph.get_edge_label(u, v))] + for each in attrlist: + attr = '%s="%s" ' % (each[0], each[1]) + line = line + attr + line = line + ']\n' + return line + + +def _dot_arrow_str(graph, u, v, wt): + line = '\t"%s" -> "%s" [ ' % (str(u), str(v)) + attrlist = graph.get_edge_attributes(u, v) + [('label',graph.get_edge_label(u, v))] + for each in attrlist: + attr = '%s="%s" ' % (each[0], each[1]) + line = line + attr + line = line + ']\n' + return line + + +def write_dot_graph(graph, wt): + """ + Return a string specifying the given graph in DOT Language. + + @type graph: graph + @param graph: Graph. + + @type wt: boolean + @param wt: Whether edges should be labelled with its weight. + + @rtype: string + @return: String specifying the graph in DOT Language. + """ + doc = 'graph graphname \n{\n' + for node in graph: + doc = doc + _dot_node_str(graph, node, wt) + for edge in graph[node]: + if (node >= edge): + doc = doc + _dot_edge_str(graph, node, edge, wt) + doc = doc + '}' + return doc + + +def write_dot_digraph(graph, wt): + """ + Return a string specifying the given digraph in DOT Language. + + @type graph: graph + @param graph: Graph. + + @type wt: boolean + @param wt: Whether arrows should be labelled with its weight. + + @rtype: string + @return: String specifying the graph in DOT Language. + """ + doc = 'digraph graphname \n{\n' + for node in graph: + doc = doc + _dot_node_str(graph, node, wt) + for edge in graph[node]: + doc = doc + _dot_arrow_str(graph, node, edge, wt) + doc = doc + '}' + return doc + + +def write_dot_hypergraph(hypergraph, coloured=False): + """ + Return a string specifying the given hypergraph in DOT Language. + + @type hypergraph: hypergraph + @param hypergraph: Hypergraph. + + @type coloured: boolean + @param coloured: Whether hyperedges should be coloured. + + @rtype: string + @return: String specifying the hypergraph in DOT Language. + """ + # Start document + doc = "" + doc = doc + "graph graphname" + "\n{\n" + colortable = {} + colorcount = 0 + + + # Add hyperedges + color = '' + for each_hyperedge in hypergraph.hyperedges(): + colortable[each_hyperedge] = colors[colorcount % len(colors)] + colorcount = colorcount + 1 + if (coloured): + color = " color=%s" % colortable[each_hyperedge] + vars = { + 'hyperedge' : str(each_hyperedge), + 'color' : color + } + doc = doc + '\t"%(hyperedge)s" [shape=point %(color)s]\n' % vars + + color = "\n" + # Add nodes and links + for each_node in hypergraph.nodes(): + doc = doc + "\t\"%s\"\n" % str(each_node) + for each_link in hypergraph.links(each_node): + if (coloured): + color = " [color=%s]\n" % colortable[each_link] + linkvars = { + 'node' : str(each_node), + 'hyperedge' : str(each_link) + } + doc = doc + '\t %(node)s -- %(hyperedge)s' % linkvars + color + + doc = doc + "}" + return doc diff -r c1f9435bb645 -r 32a30f609530 scripts/graph/searching.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/scripts/graph/searching.py Thu Nov 27 23:41:08 2008 +0000 @@ -0,0 +1,167 @@ +# Copyright (c) 2007-2008 Pedro Matiello +# +# Permission is hereby granted, free of charge, to any person +# obtaining a copy of this software and associated documentation +# files (the "Software"), to deal in the Software without +# restriction, including without limitation the rights to use, +# copy, modify, merge, publish, distribute, sublicense, and/or sell +# copies of the Software, and to permit persons to whom the +# Software is furnished to do so, subject to the following +# conditions: + +# The above copyright notice and this permission notice shall be +# included in all copies or substantial portions of the Software. + +# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES +# OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND +# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT +# HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, +# WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR +# OTHER DEALINGS IN THE SOFTWARE. + + +""" +Search algorithms for python-graph. + +@sort: breadth_first_search, depth_first_search, _bfs, _dfs +""" + + +# Depth-first search + +def depth_first_search(graph, root=None): + """ + Depth-first search. + + @type graph: graph + @param graph: Graph. + + @type root: node + @param root: Optional root node (will explore only root's connected component) + + @rtype: tuple + @return: A tupple containing a dictionary and two lists: + 1. Generated spanning tree + 2. Graph's preordering + 3. Graph's postordering + """ + visited = {} # List for marking visited and non-visited nodes + spanning_tree = {} # Spanning tree + pre = [] # Graph's preordering + post = [] # Graph's postordering + + # DFS from one node only + if (root is not None): + spanning_tree[root] = None + _dfs(graph, visited, spanning_tree, pre, post, root) + return spanning_tree, pre, post + + # Algorithm loop + for each in graph: + # Select a non-visited node + if (each not in visited): + spanning_tree[each] = None + # Explore node's connected component + _dfs(graph, visited, spanning_tree, pre, post, each) + + return spanning_tree, pre, post + + +def _dfs(graph, visited, spanning_tree, pre, post, node): + """ + Depht-first search subfunction. + + @type graph: graph + @param graph: Graph. + + @type visited: dictionary + @param visited: List of nodes (visited nodes are marked non-zero). + + @type spanning_tree: dictionary + @param spanning_tree: Spanning tree being built for the graph by DFS. + + @type pre: list + @param pre: Graph's preordering. + + @type post: list + @param post: Graph's postordering. + + @type node: node + @param node: Node to be explored by DFS. + """ + visited[node] = 1 + pre.append(node) + # Explore recursively the connected component + for each in graph[node]: + if (each not in visited): + spanning_tree[each] = node + _dfs(graph, visited, spanning_tree, pre, post, each) + post.append(node) + + +# Breadth-first search + +def breadth_first_search(graph, root=None): + """ + Breadth-first search. + + @type graph: graph + @param graph: Graph. + + @type root: node + @param root: Optional root node (will explore only root's connected component) + + @rtype: tuple + @return: A tuple containing a dictionary and a list. + 1. Generated spanning tree + 2. Graph's level-based ordering + """ + queue = [] # Visiting queue + spanning_tree = {} # Spanning tree + ordering = [] + + # BFS from one node only + if (root is not None): + queue.append(root) + ordering.append(root) + spanning_tree[root] = None + _bfs(graph, queue, spanning_tree, ordering) + return spanning_tree, ordering + + # Algorithm + for each in graph: + if (each not in spanning_tree): + queue.append(each) + ordering.append(root) + spanning_tree[each] = None + _bfs(graph, queue, spanning_tree, ordering) + + return spanning_tree, ordering[1:] + + +def _bfs(graph, queue, spanning_tree, ordering): + """ + Breadth-first search subfunction. + + @type graph: graph + @param graph: Graph. + + @type spanning_tree: dictionary + @param spanning_tree: Spanning tree being built for the graph by DFS. + + @type ordering: list + @param ordering: Graph's level-based ordering. + + @type queue: list + @param queue: Nodes to be visited (ordered). + """ + while (queue != []): + node = queue.pop(0) + + for other in graph[node]: + if (other not in spanning_tree): + queue.append(other) + ordering.append(other) + spanning_tree[other] = node diff -r c1f9435bb645 -r 32a30f609530 scripts/graph/sorting.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/scripts/graph/sorting.py Thu Nov 27 23:41:08 2008 +0000 @@ -0,0 +1,49 @@ +# Copyright (c) 2007-2008 Pedro Matiello +# +# Permission is hereby granted, free of charge, to any person +# obtaining a copy of this software and associated documentation +# files (the "Software"), to deal in the Software without +# restriction, including without limitation the rights to use, +# copy, modify, merge, publish, distribute, sublicense, and/or sell +# copies of the Software, and to permit persons to whom the +# Software is furnished to do so, subject to the following +# conditions: + +# The above copyright notice and this permission notice shall be +# included in all copies or substantial portions of the Software. + +# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES +# OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND +# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT +# HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, +# WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR +# OTHER DEALINGS IN THE SOFTWARE. + + +""" +Sorting algorithms for python-graph. + +@sort: topological_sorting +""" + + +# Topological sorting + +def topological_sorting(graph): + """ + Topological sorting. + + @attention: Topological sorting is meaningful only for directed acyclic graphs. + + @type graph: graph + @param graph: Graph. + + @rtype: list + @return: Topological sorting for the graph. + """ + # The topological sorting of a DAG is equivalent to its reverse postordering. + tmp, tmp, post = graph.depth_first_search() + post.reverse() + return post diff -r c1f9435bb645 -r 32a30f609530 scripts/graph/traversal.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/scripts/graph/traversal.py Thu Nov 27 23:41:08 2008 +0000 @@ -0,0 +1,81 @@ +# Copyright (c) 2007-2008 Pedro Matiello +# +# Permission is hereby granted, free of charge, to any person +# obtaining a copy of this software and associated documentation +# files (the "Software"), to deal in the Software without +# restriction, including without limitation the rights to use, +# copy, modify, merge, publish, distribute, sublicense, and/or sell +# copies of the Software, and to permit persons to whom the +# Software is furnished to do so, subject to the following +# conditions: + +# The above copyright notice and this permission notice shall be +# included in all copies or substantial portions of the Software. + +# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES +# OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND +# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT +# HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, +# WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR +# OTHER DEALINGS IN THE SOFTWARE. + + +""" +Traversal algorithms for python-graph. + +@sort: traversal +""" + + +# Minimal spanning tree + +def traversal(graph, node, order): + """ + Graph traversal iterator. + + @type node: node + @param node: Node. + + @type order: string + @param order: traversal ordering. Possible values are: + 2. 'pre' - Preordering (default) + 1. 'post' - Postordering + + @rtype: iterator + @return: Traversal iterator. + """ + visited = {} + if (order == 'pre'): + pre = 1 + post = 0 + elif (order == 'post'): + pre = 0 + post = 1 + + for each in _dfs(graph, visited, node, pre, post): + yield each + + +def _dfs(graph, visited, node, pre, post): + """ + Depht-first search subfunction for traversals. + + @type graph: graph + @param graph: Graph. + + @type visited: dictionary + @param visited: List of nodes (visited nodes are marked non-zero). + + @type node: node + @param node: Node to be explored by DFS. + """ + visited[node] = 1 + if (pre): yield node + # Explore recursively the connected component + for each in graph[node]: + if (each not in visited): + for other in _dfs(graph, visited, each, pre, post): + yield other + if (post): yield node