--- 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)
--- 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 <pmatiello@gmail.com>
-# Christian Muise <christian.muise@gmail.com>
-# Nathan Davis <davisn90210@gmail.com>
-# Zsolt Haraszti <zsolt@drawwell.net>
-#
-# Permission is hereby granted, free of charge, to any person
-# obtaining a copy of this software and associated documentation
-# files (the "Software"), to deal in the Software without
-# restriction, including without limitation the rights to use,
-# copy, modify, merge, publish, distribute, sublicense, and/or sell
-# copies of the Software, and to permit persons to whom the
-# Software is furnished to do so, subject to the following
-# conditions:
-
-# The above copyright notice and this permission notice shall be
-# included in all copies or substantial portions of the Software.
-
-# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
-# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
-# OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
-# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
-# HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
-# WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
-# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
-# OTHER DEALINGS IN THE SOFTWARE.
-
-
-"""
-python-graph
-
-A library for working with graphs in Python.
-
-@version: 1.3.1
-"""
-
-
-# Imports
-import accessibility
-import generators
-import minmax
-import searching
-import sorting
-import readwrite
-import traversal
-
-
-# Graph class --------------------------------------------------------------------------------------
-
-class graph (object):
- """
- Graph class.
-
- Graphs are built of nodes and edges.
-
- @sort: __init__, __getitem__, __iter__, __len__, __str__, add_edge, add_edge_attribute,
- add_graph, add_node, add_node_attribute, add_nodes, add_spanning_tree, complete, del_edge,
- del_node, edges, get_edge_attributes, get_edge_label, get_edge_weight, get_node_attributes,
- has_edge, has_node, inverse, neighbors, nodes, order, set_edge_label, set_edge_weight,
- traversal, generate, read, write, accessibility, breadth_first_search, connected_components,
- cut_edges, cut_nodes, depth_first_search, minimal_spanning_tree, shortest_path
- """
-
-
- def __init__(self):
- """
- Initialize a graph.
- """
- self.node_neighbors = {} # Pairing: Node -> Neighbors
- self.edge_properties = {} # Pairing: Edge -> (Label, Weight)
- self.node_attr = {} # Pairing: Node -> Attributes
- self.edge_attr = {} # Pairing: Edge -> Attributes
-
-
- def __str__(self):
- """
- Return a string representing the graph when requested by str() (or print).
-
- @rtype: string
- @return: String representing the graph.
- """
- return "<graph object " + str(self.nodes()) + " " + str(self.edges()) + ">"
-
-
- def __len__(self):
- """
- Return the order of the graph when requested by len().
-
- @rtype: number
- @return: Size of the graph.
- """
- return len(self.node_neighbors)
-
-
- def __iter__(self):
- """
- Return a iterator passing through all nodes in the graph.
-
- @rtype: iterator
- @return: Iterator passing through all nodes in the graph.
- """
- for each in self.node_neighbors.iterkeys():
- yield each
-
-
- def __getitem__(self, node):
- """
- Return a iterator passing through all neighbors of the given node.
-
- @rtype: iterator
- @return: Iterator passing through all neighbors of the given node.
- """
- for each in self.node_neighbors[node]:
- yield each
-
-
- def read(self, string, fmt='xml'):
- """
- Read a graph from a string. Nodes and edges specified in the input will be added to the
- current graph.
-
- @type string: string
- @param string: Input string specifying a graph.
-
- @type fmt: string
- @param fmt: Input format. Possible formats are:
- 1. 'xml' - XML (default)
- """
- if (fmt == 'xml'):
- readwrite.read_xml(self, string)
-
-
- def write(self, fmt='xml'):
- """
- Write the graph to a string. Depending of the output format, this string can be used by
- read() to rebuild the graph.
-
- @type fmt: string
- @param fmt: Output format. Possible formats are:
- 1. 'xml' - XML (default)
- 2. 'dot' - DOT Language (for GraphViz)
- 3. 'dotwt' - DOT Language with weight information
-
- @rtype: string
- @return: String specifying the graph.
- """
- if (fmt == 'xml'):
- return readwrite.write_xml(self)
- elif (fmt == 'dot'):
- return readwrite.write_dot_graph(self, False)
- elif (fmt == 'dotwt'):
- return readwrite.write_dot_graph(self, True)
-
-
- def generate(self, num_nodes, num_edges, weight_range=(1, 1)):
- """
- Add nodes and random edges to the graph.
-
- @type num_nodes: number
- @param num_nodes: Number of nodes.
-
- @type num_edges: number
- @param num_edges: Number of edges.
-
- @type weight_range: tuple
- @param weight_range: tuple of two integers as lower and upper limits on randomly generated
- weights (uniform distribution).
- """
- generators.generate(self, num_nodes, num_edges, weight_range)
-
-
- def nodes(self):
- """
- Return node list.
-
- @rtype: list
- @return: Node list.
- """
- return self.node_neighbors.keys()
-
-
- def neighbors(self, node):
- """
- Return all nodes that are directly accessible from given node.
-
- @type node: node
- @param node: Node identifier
-
- @rtype: list
- @return: List of nodes directly accessible from given node.
- """
- return self.node_neighbors[node]
-
-
- def edges(self):
- """
- Return all edges in the graph.
-
- @rtype: list
- @return: List of all edges in the graph.
- """
- return self.edge_properties.keys()
-
-
- def has_node(self, node):
- """
- Return whether the requested node exists.
-
- @type node: node
- @param node: Node identifier
-
- @rtype: boolean
- @return: Truth-value for node existence.
- """
- return self.node_neighbors.has_key(node)
-
-
- def add_node(self, node, attrs=[]):
- """
- Add given node to the graph.
-
- @attention: While nodes can be of any type, it's strongly recommended to use only numbers
- and single-line strings as node identifiers if you intend to use write().
-
- @type node: node
- @param node: Node identifier.
-
- @type attrs: list
- @param attrs: List of node attributes specified as (attribute, value) tuples.
- """
- if (not node in self.node_neighbors):
- self.node_neighbors[node] = []
- self.node_attr[node] = attrs
-
-
- def add_nodes(self, nodelist):
- """
- Add given nodes to the graph.
-
- @attention: While nodes can be of any type, it's strongly recommended to use only numbers
- and single-line strings as node identifiers if you intend to use write().
-
- @type nodelist: list
- @param nodelist: List of nodes to be added to the graph.
- """
- for each in nodelist:
- self.add_node(each)
-
-
- def add_edge(self, u, v, wt=1, label='', attrs=[]):
- """
- Add an edge (u,v) to the graph connecting nodes u and v.
-
- @type u: node
- @param u: One node.
-
- @type v: node
- @param v: Other node.
-
- @type wt: number
- @param wt: Edge weight.
-
- @type label: string
- @param label: Edge label.
-
- @type attrs: list
- @param attrs: List of node attributes specified as (attribute, value) tuples.
- """
- if (v not in self.node_neighbors[u] and u not in self.node_neighbors[v]):
- self.node_neighbors[u].append(v)
- self.node_neighbors[v].append(u)
- self.edge_properties[(u, v)] = [label, wt]
- self.edge_properties[(v, u)] = [label, wt]
- self.edge_attr[(u, v)] = attrs
- self.edge_attr[(v, u)] = attrs
-
-
- def del_node(self, node):
- """
- Remove a node from the graph.
-
- @type node: node
- @param node: Node identifier.
- """
- for each in list(self.neighbors(node)):
- self.del_edge(each, node)
- del(self.node_neighbors[node])
- del(self.node_attr[node])
-
-
- def del_edge(self, u, v):
- """
- Remove an edge (u, v) from the graph.
-
- @type u: node
- @param u: One node.
-
- @type v: node
- @param v: Other node.
- """
- self.node_neighbors[u].remove(v)
- self.node_neighbors[v].remove(u)
- del(self.edge_properties[(u,v)])
- del(self.edge_properties[(v,u)])
- del(self.edge_attr[(u,v)])
- del(self.edge_attr[(v,u)])
-
-
- def get_edge_weight(self, u, v):
- """
- Get the weight of an edge.
-
- @type u: node
- @param u: One node.
-
- @type v: node
- @param v: Other node.
-
- @rtype: number
- @return: Edge weight.
- """
- return self.edge_properties[(u, v)][1]
-
-
- def set_edge_weight(self, u, v, wt):
- """
- Set the weight of an edge.
-
- @type u: node
- @param u: One node.
-
- @type v: node
- @param v: Other node.
-
- @type wt: number
- @param wt: Edge weight.
- """
- self.edge_properties[(u, v)][1] = wt
- self.edge_properties[(v, u)][1] = wt
-
-
- def get_edge_label(self, u, v):
- """
- Get the label of an edge.
-
- @type u: node
- @param u: One node.
-
- @type v: node
- @param v: Other node.
-
- @rtype: string
- @return: Edge label
- """
- return self.edge_properties[(u, v)][0]
-
-
- def set_edge_label(self, u, v, label):
- """
- Set the label of an edge.
-
- @type u: node
- @param u: One node.
-
- @type v: node
- @param v: Other node.
-
- @type label: string
- @param label: Edge label.
- """
- self.edge_properties[(u, v)][0] = label
- self.edge_properties[(v, u)][0] = label
-
-
- def add_node_attribute(self, node, attr):
- """
- Add attribute to the given node.
-
- @type node: node
- @param node: Node identifier
-
- @type attr: tuple
- @param attr: Node attribute specified as a tuple in the form (attribute, value).
- """
- self.node_attr[node] = self.node_attr[node] + [attr]
-
-
- def get_node_attributes(self, node):
- """
- Return the attributes of the given node.
-
- @type node: node
- @param node: Node identifier
-
- @rtype: list
- @return: List of attributes specified tuples in the form (attribute, value).
- """
- return self.node_attr[node]
-
-
- def add_edge_attribute(self, u, v, attr):
- """
- Add attribute to the given edge.
-
- @type u: node
- @param u: One node.
-
- @type v: node
- @param v: Other node.
-
- @type attr: tuple
- @param attr: Node attribute specified as a tuple in the form (attribute, value).
- """
- self.edge_attr[(u,v)] = self.edge_attr[(u,v)] + [attr]
- self.edge_attr[(v,u)] = self.edge_attr[(v,u)] + [attr]
-
-
- def get_edge_attributes(self, u, v):
- """
- Return the attributes of the given edge.
-
- @type u: node
- @param u: One node.
-
- @type v: node
- @param v: Other node.
-
- @rtype: list
- @return: List of attributes specified tuples in the form (attribute, value).
- """
- return self.edge_attr[(u,v)]
-
-
- def has_edge(self, u, v):
- """
- Return whether an edge between nodes u and v exists.
-
- @type u: node
- @param u: One node.
-
- @type v: node
- @param v: Other node.
-
- @rtype: boolean
- @return: Truth-value for edge existence.
- """
- return self.edge_properties.has_key((u,v)) and self.edge_properties.has_key((v,u))
-
-
- def order(self, node):
- """
- Return the order of the given node.
-
- @rtype: number
- @return: Order of the given node.
- """
- return len(self.neighbors(node))
-
-
- def complete(self):
- """
- Make the graph a complete graph.
-
- @attention: This will modify the current graph.
- """
- for each in self.nodes():
- for other in self.nodes():
- if (each != other):
- self.add_edge(each, other)
-
-
- def inverse(self):
- """
- Return the inverse of the graph.
-
- @rtype: graph
- @return: Complement graph for the graph.
- """
- inv = graph()
- inv.add_nodes(self.nodes())
- inv.complete()
- for each in self.edges():
- if (inv.has_edge(each[0], each[1])):
- inv.del_edge(each[0], each[1])
- return inv
-
-
- def add_graph(self, graph):
- """
- Add other graph to the graph.
-
- @attention: Attributes and labels are not preserved.
-
- @type graph: graph
- @param graph: Graph
- """
- self.add_nodes(graph.nodes())
- for each_node in graph.nodes():
- for each_edge in graph.neighbors(each_node):
- self.add_edge(each_node, each_edge)
-
-
- def add_spanning_tree(self, st):
- """
- Add a spanning tree to the graph.
-
- @type st: dictionary
- @param st: Spanning tree.
- """
- self.add_nodes(st.keys())
- for each in st:
- if (st[each] is not None):
- self.add_edge(st[each], each)
-
-
- def traversal(self, node, order='pre'):
- """
- Graph traversal iterator.
-
- @type node: node
- @param node: Node.
-
- @type order: string
- @param order: traversal ordering. Possible values are:
- 2. 'pre' - Preordering (default)
- 1. 'post' - Postordering
-
- @rtype: iterator
- @return: Traversal iterator.
- """
- for each in traversal.traversal(self, node, order):
- yield each
-
-
- def depth_first_search(self, root=None):
- """
- Depht-first search.
-
- @type root: node
- @param root: Optional root node (will explore only root's connected component)
-
- @rtype: tuple
- @return: tupple containing a dictionary and two lists:
- 1. Generated spanning tree
- 2. Graph's preordering
- 3. Graph's postordering
- """
- return searching.depth_first_search(self, root)
-
-
- def breadth_first_search(self, root=None):
- """
- Breadth-first search.
-
- @type root: node
- @param root: Optional root node (will explore only root's connected component)
-
- @rtype: dictionary
- @return: A tuple containing a dictionary and a list.
- 1. Generated spanning tree
- 2. Graph's level-based ordering
- """
- return searching.breadth_first_search(self, root)
-
-
- def accessibility(self):
- """
- Accessibility matrix (transitive closure).
-
- @rtype: dictionary
- @return: Accessibility information for each node.
- """
- return accessibility.accessibility(self)
-
-
- def connected_components(self):
- """
- Connected components.
-
- @attention: Indentification of connected components is meaningful only for non-directed
- graphs.
-
- @rtype: dictionary
- @return: Pairing that associates each node to its connected component.
- """
- return accessibility.connected_components(self)
-
-
- def minimal_spanning_tree(self, root=None):
- """
- Minimal spanning tree.
-
- @type root: node
- @param root: Optional root node (will explore only root's connected component)
-
- @attention: Minimal spanning tree meaningful only for weighted graphs.
-
- @rtype: list
- @return: Generated spanning tree.
- """
- return minmax.minimal_spanning_tree(self, root)
-
-
- def shortest_path(self, source):
- """
- Return the shortest path distance between source node and all other nodes using Dijkstra's
- algorithm.
-
- @attention: All weights must be nonnegative.
-
- @type source: node
- @param source: Node from which to start the search.
-
- @rtype: tuple
- @return: A tuple containing two dictionaries, each keyed by target nodes.
- 1. Shortest path spanning tree
- 2. Shortest distance from given source to each target node
- Inaccessible target nodes do not appear in either dictionary.
- """
- return minmax.shortest_path(self, source)
-
-
- def cut_edges(self):
- """
- Return the cut-edges of the given graph.
-
- @rtype: list
- @return: List of cut-edges.
- """
- return accessibility.cut_edges(self)
-
-
- def cut_nodes(self):
- """
- Return the cut-nodes of the given graph.
-
- @rtype: list
- @return: List of cut-nodes.
- """
- return accessibility.cut_nodes(self)
-
-
-# Digraph class ------------------------------------------------------------------------------------
-
-class digraph (object):
- """
- Digraph class.
-
- Digraphs are built of nodes and directed edges.
-
- @sort: __init__, __getitem__, __iter__, __len__, __str__, add_edge, add_edge_attribute,
- add_graph, add_node, add_node_attribute, add_nodes, add_spanning_tree, complete, degree,
- del_edge, del_node, edges, get_edge_attributes, get_edge_label, get_edge_weight,
- get_node_attributes, has_edge, has_node, incidents, inverse, neighbors, nodes, order,
- set_edge_label, set_edge_weight, traversal, generate, read, write, accessibility,
- breadth_first_search, cut_edges, cut_nodes, depth_first_search, minimal_spanning_tree,
- mutual_accessibility, shortest_path, topological_sorting
- """
-
-
- def __init__(self):
- """
- Initialize a digraph.
- """
- self.node_neighbors = {} # Pairing: Node -> Neighbors
- self.edge_properties = {} # Pairing: Edge -> (Label, Weight)
- self.node_incidence = {} # Pairing: Node -> Incident nodes
- self.node_attr = {} # Pairing: Node -> Attributes
- self.edge_attr = {} # Pairing: Edge -> Attributes
-
-
- def __str__(self):
- """
- Return a string representing the digraph when requested by str() (or print).
-
- @rtype: string
- @return: String representing the graph.
- """
- return "<graph object " + str(self.nodes()) + " " + str(self.edges()) + ">"
-
-
- def __len__(self):
- """
- Return the order of the digraph when requested by len().
-
- @rtype: number
- @return: Size of the graph.
- """
- return len(self.node_neighbors)
-
-
- def __iter__(self):
- """
- Return a iterator passing through all nodes in the digraph.
-
- @rtype: iterator
- @return: Iterator passing through all nodes in the digraph.
- """
- for each in self.node_neighbors.iterkeys():
- yield each
-
-
- def __getitem__(self, node):
- """
- Return a iterator passing through all neighbors of the given node.
-
- @rtype: iterator
- @return: Iterator passing through all neighbors of the given node.
- """
- for each in self.node_neighbors[node]:
- yield each
-
-
- def read(self, string, fmt='xml'):
- """
- Read a graph from a string. Nodes and edges specified in the input will be added to the
- current graph.
-
- @type string: string
- @param string: Input string specifying a graph.
-
- @type fmt: string
- @param fmt: Input format. Possible formats are:
- 1. 'xml' - XML (default)
- """
- if (fmt == 'xml'):
- readwrite.read_xml(self, string)
-
-
- def write(self, fmt='xml'):
- """
- Write the graph to a string. Depending of the output format, this string can be used by
- read() to rebuild the graph.
-
- @type fmt: string
- @param fmt: Output format. Possible formats are:
- 1. 'xml' - XML (default)
- 2. 'dot' - DOT Language (for GraphViz)
- 3. 'dotwt' - DOT Language with weight information
-
- @rtype: string
- @return: String specifying the graph.
- """
- if (fmt == 'xml'):
- return readwrite.write_xml(self)
- elif (fmt == 'dot'):
- return readwrite.write_dot_digraph(self, False)
- elif (fmt == 'dotwt'):
- return readwrite.write_dot_digraph(self, True)
-
-
- def generate(self, num_nodes, num_edges, weight_range=(1, 1)):
- """
- Add nodes and random edges to the graph.
-
- @type num_nodes: number
- @param num_nodes: Number of nodes.
-
- @type num_edges: number
- @param num_edges: Number of edges.
-
- @type weight_range: tuple
- @param weight_range: tuple of two integers as lower and upper limits on randomly generated
- weights (uniform distribution).
- """
- generators.generate(self, num_nodes, num_edges, weight_range)
-
-
- def nodes(self):
- """
- Return node list.
-
- @rtype: list
- @return: Node list.
- """
- return self.node_neighbors.keys()
-
-
- def neighbors(self, node):
- """
- Return all nodes that are directly accessible from given node.
-
- @type node: node
- @param node: Node identifier
-
- @rtype: list
- @return: List of nodes directly accessible from given node.
- """
- return self.node_neighbors[node]
-
-
- def incidents(self, node):
- """
- Return all nodes that are incident to the given node.
-
- @type node: node
- @param node: Node identifier
-
- @rtype: list
- @return: List of nodes directly accessible from given node.
- """
- return self.node_incidence[node]
-
-
-
- def edges(self):
- """
- Return all edges in the graph.
-
- @rtype: list
- @return: List of all edges in the graph.
- """
- return self.edge_properties.keys()
-
-
- def has_node(self, node):
- """
- Return whether the requested node exists.
-
- @type node: node
- @param node: Node identifier
-
- @rtype: boolean
- @return: Truth-value for node existence.
- """
- return self.node_neighbors.has_key(node)
-
-
- def add_node(self, node, attrs=[]):
- """
- Add given node to the graph.
-
- @attention: While nodes can be of any type, it's strongly recommended to use only numbers
- and single-line strings as node identifiers if you intend to use write().
-
- @type node: node
- @param node: Node identifier.
-
- @type attrs: list
- @param attrs: List of node attributes specified as (attribute, value) tuples.
- """
- if (node not in self.node_neighbors):
- self.node_neighbors[node] = []
- self.node_incidence[node] = []
- self.node_attr[node] = attrs
-
-
- def add_nodes(self, nodelist):
- """
- Add given nodes to the graph.
-
- @attention: While nodes can be of any type, it's strongly recommended to use only numbers
- and single-line strings as node identifiers if you intend to use write().
-
- @type nodelist: list
- @param nodelist: List of nodes to be added to the graph.
- """
- for each in nodelist:
- self.add_node(each)
-
-
- def add_edge(self, u, v, wt=1, label='', attrs=[]):
- """
- Add an directed edge (u,v) to the graph connecting nodes u to v.
-
- @type u: node
- @param u: One node.
-
- @type v: node
- @param v: Other node.
-
- @type wt: number
- @param wt: Edge weight.
-
- @type label: string
- @param label: Edge label.
-
- @type attrs: list
- @param attrs: List of node attributes specified as (attribute, value) tuples.
- """
- if (v not in self.node_neighbors[u]):
- self.node_neighbors[u].append(v)
- self.node_incidence[v].append(u)
- self.edge_properties[(u, v)] = [label, wt]
- self.edge_attr[(u, v)] = attrs
-
-
- def del_node(self, node):
- """
- Remove a node from the graph.
-
- @type node: node
- @param node: Node identifier.
- """
- for each in list(self.incidents(node)):
- self.del_edge(each, node)
- for each in list(self.neighbors(node)):
- self.del_edge(node, each)
- del(self.node_neighbors[node])
- del(self.node_incidence[node])
- del(self.node_attr[node])
-
-
- def del_edge(self, u, v):
- """
- Remove an directed edge (u, v) from the graph.
-
- @type u: node
- @param u: One node.
-
- @type v: node
- @param v: Other node.
- """
- self.node_neighbors[u].remove(v)
- self.node_incidence[v].remove(u)
- del(self.edge_properties[(u,v)])
- del(self.edge_attr[(u,v)])
-
-
- def get_edge_weight(self, u, v):
- """
- Get the weight of an edge.
-
- @type u: node
- @param u: One node.
-
- @type v: node
- @param v: Other node.
-
- @rtype: number
- @return: Edge weight.
- """
- return self.edge_properties[(u, v)][1]
-
-
- def set_edge_weight(self, u, v, wt):
- """
- Set the weight of an edge.
-
- @type u: node
- @param u: One node.
-
- @type v: node
- @param v: Other node.
-
- @type wt: number
- @param wt: Edge weight.
- """
- self.edge_properties[(u, v)][1] = wt
-
-
- def get_edge_label(self, u, v):
- """
- Get the label of an edge.
-
- @type u: node
- @param u: One node.
-
- @type v: node
- @param v: Other node.
-
- @rtype: string
- @return: Edge label
- """
- return self.edge_properties[(u, v)][0]
-
-
- def set_edge_label(self, u, v, label):
- """
- Set the label of an edge.
-
- @type u: node
- @param u: One node.
-
- @type v: node
- @param v: Other node.
-
- @type label: string
- @param label: Edge label.
- """
- self.edge_properties[(u, v)][0] = label
-
-
- def add_node_attribute(self, node, attr):
- """
- Add attribute to the given node.
-
- @type node: node
- @param node: Node identifier
-
- @type attr: tuple
- @param attr: Node attribute specified as a tuple in the form (attribute, value).
- """
- self.node_attr[node] = self.node_attr[node] + [attr]
-
-
- def get_node_attributes(self, node):
- """
- Return the attributes of the given node.
-
- @type node: node
- @param node: Node identifier
-
- @rtype: list
- @return: List of attributes specified tuples in the form (attribute, value).
- """
- return self.node_attr[node]
-
-
- def add_edge_attribute(self, u, v, attr):
- """
- Add attribute to the given edge.
-
- @type u: node
- @param u: One node.
-
- @type v: node
- @param v: Other node.
-
- @type attr: tuple
- @param attr: Node attribute specified as a tuple in the form (attribute, value).
- """
- self.edge_attr[(u,v)] = self.edge_attr[(u,v)] + [attr]
-
-
- def get_edge_attributes(self, u, v):
- """
- Return the attributes of the given edge.
-
- @type u: node
- @param u: One node.
-
- @type v: node
- @param v: Other node.
-
- @rtype: list
- @return: List of attributes specified tuples in the form (attribute, value).
- """
- return self.edge_attr[(u,v)]
-
-
- def has_edge(self, u, v):
- """
- Return whether an edge between nodes u and v exists.
-
- @type u: node
- @param u: One node.
-
- @type v: node
- @param v: Other node.
-
- @rtype: boolean
- @return: Truth-value for edge existence.
- """
- return self.edge_properties.has_key((u,v))
-
-
- def order(self, node):
- """
- Return the order of the given node.
-
- @rtype: number
- @return: Order of the given node.
- """
- return len(self.neighbors(node))
-
-
- def degree(self, node):
- """
- Return the degree of the given node.
-
- @rtype: number
- @return: Order of the given node.
- """
- return len(self.node_incidence[node])
-
-
- def complete(self):
- """
- Make the graph a complete graph.
-
- @attention: This will modify the current graph.
- """
- for each in self.nodes():
- for other in self.nodes():
- if (each != other):
- self.add_edge(each, other)
-
-
- def inverse(self):
- """
- Return the inverse of the graph.
-
- @rtype: graph
- @return: Complement graph for the graph.
- """
- inv = digraph()
- inv.add_nodes(self.nodes())
- inv.complete()
- for each in self.edges():
- inv.del_edge(each[0], each[1])
- return inv
-
-
- def add_graph(self, graph):
- """
- Add other graph to the graph.
-
- @attention: Attributes and labels are not preserved.
-
- @type graph: graph
- @param graph: Graph
- """
- self.add_nodes(graph.nodes())
- for each_node in graph.nodes():
- for each_edge in graph.neighbors(each_node):
- self.add_edge(each_node, each_edge)
-
-
- def add_spanning_tree(self, st):
- """
- Add a spanning tree to the graph.
-
- @type st: dictionary
- @param st: Spanning tree.
- """
- self.add_nodes(st.keys())
- for each in st:
- if (st[each] is not None):
- self.add_edge(st[each], each)
-
-
- def traversal(self, node, order='pre'):
- """
- Graph traversal iterator.
-
- @type node: node
- @param node: Node.
-
- @type order: string
- @param order: traversal ordering. Possible values are:
- 2. 'pre' - Preordering (default)
- 1. 'post' - Postordering
-
- @rtype: iterator
- @return: Traversal iterator.
- """
- for each in traversal.traversal(self, node, order):
- yield each
-
-
- def depth_first_search(self, root=None):
- """
- Depht-first search.
-
- @type root: node
- @param root: Optional root node (will explore only root's connected component)
-
- @rtype: tuple
- @return: tupple containing a dictionary and two lists:
- 1. Generated spanning tree
- 2. Graph's preordering
- 3. Graph's postordering
- """
- return searching.depth_first_search(self, root)
-
-
- def accessibility(self):
- """
- Accessibility matrix (transitive closure).
-
- @rtype: dictionary
- @return: Accessibility information for each node.
- """
- return accessibility.accessibility(self)
-
-
- def breadth_first_search(self, root=None):
- """
- Breadth-first search.
-
- @type root: node
- @param root: Optional root node (will explore only root's connected component)
-
- @rtype: dictionary
- @return: A tuple containing a dictionary and a list.
- 1. Generated spanning tree
- 2. Graph's level-based ordering
- """
- return searching.breadth_first_search(self, root)
-
-
- def mutual_accessibility(self):
- """
- Mutual-accessibility matrix (strongly connected components).
-
- @rtype: list
- @return: Mutual-accessibility information for each node.
- """
- return accessibility.mutual_accessibility(self)
-
-
- def topological_sorting(self):
- """
- Topological sorting.
-
- @attention: Topological sorting is meaningful only for directed acyclic graphs.
-
- @rtype: list
- @return: Topological sorting for the graph.
- """
- return sorting.topological_sorting(self)
-
-
- def minimal_spanning_tree(self, root=None):
- """
- Minimal spanning tree.
-
- @type root: node
- @param root: Optional root node (will explore only root's connected component)
-
- @attention: Minimal spanning tree meaningful only for weighted graphs.
-
- @rtype: list
- @return: Generated spanning tree.
- """
- return minmax.minimal_spanning_tree(self, root)
-
-
- def shortest_path(self, source):
- """
- Return the shortest path distance between source node and all other nodes using Dijkstra's
- algorithm.
-
- @attention: All weights must be nonnegative.
-
- @type source: node
- @param source: Node from which to start the search.
-
- @rtype: tuple
- @return: A tuple containing two dictionaries, each keyed by target nodes.
- 1. Shortest path spanning tree
- 2. Shortest distance from given source to each target node
- Inaccessible target nodes do not appear in either dictionary.
- """
- return minmax.shortest_path(self, source)
-
-
- def cut_edges(self):
- """
- Return the cut-edges of the given graph.
-
- @rtype: list
- @return: List of cut-edges.
- """
- return accessibility.cut_edges(self)
-
-
- def cut_nodes(self):
- """
- Return the cut-nodes of the given graph.
-
- @rtype: list
- @return: List of cut-nodes.
- """
- return accessibility.cut_nodes(self)
-
-
-# Hypergraph class ---------------------------------------------------------------------------------
-
-class hypergraph (object):
- """
- Hypergraph class.
-
- Hypergraphs are a generalization of graphs where an edge (called hyperedge) can connect more
- than two nodes.
-
- @sort: __init__, __len__, __str__, add_hyperedge, add_hyperedges, add_node, add_nodes, has_node,
- hyperedges, link, links, nodes, unlink, read, write, accessibility, connected_components,
- cut_hyperedges, cut_nodes
- """
-
-
- def __init__(self):
- """
- Initialize a hypergraph.
- """
- self.node_links = {} # Pairing: Node -> Hyperedge
- self.edge_links = {} # Pairing: Hyperedge -> Node
- self.graph = graph() # Ordinary graph
-
-
- def __str__(self):
- """
- Return a string representing the hypergraph when requested by str() (or print).
-
- @rtype: string
- @return: String representing the hypergraph.
- """
- return "<hypergraph object " + str(self.nodes()) + " " + str(self.edge_links) + ">"
-
-
- def __len__(self):
- """
- Return the size of the hypergraph when requested by len().
-
- @rtype: number
- @return: Size of the hypergraph.
- """
- return len(self.node_links)
-
-
- def read(self, string, fmt='xml'):
- """
- Read a hypergraph from a string. Nodes and hyperedges specified in the input will be added
- to the current graph.
-
- @type string: string
- @param string: Input string specifying a graph.
-
- @type fmt: string
- @param fmt: Input format. Possible formats are:
- 1. 'xml' - XML (default)
- """
- if (fmt == 'xml'):
- readwrite.read_xml_hypergraph(self, string)
-
-
- def write(self, fmt='xml'):
- """
- Write the hypergraph to a string. Depending of the output format, this string can be used by
- read() to rebuild the graph.
-
- @type fmt: string
- @param fmt: Output format. Possible formats are:
- 1. 'xml' - XML (default)
- 2. 'dot' - DOT Language (for GraphViz)
- 3. 'dotclr' - DOT Language, coloured
-
- @rtype: string
- @return: String specifying the graph.
- """
- if (fmt == 'xml'):
- return readwrite.write_xml_hypergraph(self)
- elif (fmt == 'dot'):
- return readwrite.write_dot_hypergraph(self)
- elif (fmt == 'dotclr'):
- return readwrite.write_dot_hypergraph(self, coloured=True)
-
-
- def nodes(self):
- """
- Return node list.
-
- @rtype: list
- @return: Node list.
- """
- return self.node_links.keys()
-
-
- def hyperedges(self):
- """
- Return hyperedge list.
-
- @rtype: list
- @return: List of hyperedges linked to the given node.
- """
- return self.edge_links.keys()
-
-
- def links(self, obj):
- """
- Return all objects linked to the given one.
-
- If given a node, linked hyperedges will be returned. If given a hyperedge, linked nodes will
- be returned.
-
- @type obj: node or hyperedge
- @param obj: Object identifier.
-
- @rtype: list
- @return: List of objects linked to the given one.
- """
- if (obj in self.node_links):
- return self.node_links[obj]
- else:
- return self.edge_links[obj]
-
-
- def has_node(self, node):
- """
- Return whether the requested node exists.
-
- @type node: node
- @param node: Node identifier
-
- @rtype: boolean
- @return: Truth-value for node existence.
- """
- return self.node_links.has_key(node)
-
-
- def add_node(self, node):
- """
- Add given node to the hypergraph.
-
- @attention: While nodes can be of any type, it's strongly recommended to use only numbers
- and single-line strings as node identifiers if you intend to use write().
-
- @type node: node
- @param node: Node identifier.
- """
- if (not node in self.node_links):
- self.node_links[node] = []
- self.graph.add_node((node,'n'))
-
-
- def add_nodes(self, nodelist):
- """
- Add given nodes to the hypergraph.
-
- @attention: While nodes can be of any type, it's strongly recommended to use only numbers
- and single-line strings as node identifiers if you intend to use write().
-
- @type nodelist: list
- @param nodelist: List of nodes to be added to the graph.
- """
- for each in nodelist:
- self.add_node(each)
-
-
- def add_hyperedge(self, hyperedge):
- """
- Add given hyperedge to the hypergraph.
-
- @attention: While hyperedge-nodes can be of any type, it's strongly recommended to use only
- numbers and single-line strings as node identifiers if you intend to use write().
-
- @type hyperedge: hyperedge
- @param hyperedge: Hyperedge identifier.
- """
- if (not hyperedge in self.edge_links):
- self.edge_links[hyperedge] = []
- self.graph.add_node((hyperedge,'h'))
-
-
- def add_hyperedges(self, edgelist):
- """
- Add given hyperedges to the hypergraph.
-
- @attention: While hyperedge-nodes can be of any type, it's strongly recommended to use only
- numbers and single-line strings as node identifiers if you intend to use write().
-
- @type edgelist: list
- @param edgelist: List of hyperedge-nodes to be added to the graph.
- """
- for each in edgelist:
- self.add_hyperedge(each)
-
-
- def link(self, node, hyperedge):
- """
- Link given node and hyperedge.
-
- @type node: node
- @param node: Node.
-
- @type hyperedge: node
- @param hyperedge: Hyperedge.
- """
- if (hyperedge not in self.node_links[node]):
- self.node_links[node].append(hyperedge)
- self.edge_links[hyperedge].append(node)
- self.graph.add_edge((node,'n'), (hyperedge,'h'))
-
-
- def unlink(self, node, hyperedge):
- """
- Unlink given node and hyperedge.
-
- @type node: node
- @param node: Node.
-
- @type hyperedge: hyperedge
- @param hyperedge: Hyperedge.
- """
- self.node_links[node].remove(hyperedge)
- self.edge_links[hyperedge].remove(node)
-
-
- def accessibility(self):
- """
- Accessibility matrix (transitive closure).
-
- @rtype: dictionary
- @return: Accessibility information for each node.
- """
- access_ = accessibility.accessibility(self.graph)
- access = {}
-
- for each in access_.keys():
- if (each[1] == 'n'):
- access[each[0]] = []
- for other in access_[each]:
- if (other[1] == 'n'):
- access[each[0]].append(other[0])
-
- return access
-
-
- def connected_components(self):
- """
- Connected components.
-
- @rtype: dictionary
- @return: Pairing that associates each node to its connected component.
- """
- components_ = accessibility.connected_components(self.graph)
- components = {}
-
- for each in components_.keys():
- if (each[1] == 'n'):
- components[each[0]] = components_[each]
-
- return components
-
-
- def cut_nodes(self):
- """
- Return the cut-nodes of the given hypergraph.
-
- @rtype: list
- @return: List of cut-nodes.
- """
- cut_nodes_ = accessibility.cut_nodes(self.graph)
- cut_nodes = []
-
- for each in cut_nodes_:
- if (each[1] == 'n'):
- cut_nodes.append(each[0])
-
- return cut_nodes
-
-
- def cut_hyperedges(self):
- """
- Return the cut-hyperedges of the given hypergraph.
-
- @rtype: list
- @return: List of cut-nodes.
- """
- cut_nodes_ = accessibility.cut_nodes(self.graph)
- cut_nodes = []
-
- for each in cut_nodes_:
- if (each[1] == 'h'):
- cut_nodes.append(each[0])
-
- return cut_nodes
-
- def rank(self):
- """
- Return the rank of the given hypergraph.
-
- @rtype: int
- @return: Rank of graph.
- """
- max_rank = 0
-
- for each in hyperedges:
- if len(each) > max_rank:
- max_rank = len(each)
-
- return max_rank
--- 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 <pmatiello@gmail.com>
-#
-# 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]
--- 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 <pmatiello@gmail.com>
-# Zsolt Haraszti <zsolt@drawwell.net>
-#
-# Permission is hereby granted, free of charge, to any person
-# obtaining a copy of this software and associated documentation
-# files (the "Software"), to deal in the Software without
-# restriction, including without limitation the rights to use,
-# copy, modify, merge, publish, distribute, sublicense, and/or sell
-# copies of the Software, and to permit persons to whom the
-# Software is furnished to do so, subject to the following
-# conditions:
-
-# The above copyright notice and this permission notice shall be
-# included in all copies or substantial portions of the Software.
-
-# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
-# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
-# OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
-# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
-# HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
-# WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
-# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
-# OTHER DEALINGS IN THE SOFTWARE.
-
-
-"""
-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))
--- 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 <pmatiello@gmail.com>
-# Rhys Ulerich <rhys.ulerich@gmail.com>
-#
-# 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
--- 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 <pmatiello@gmail.com>
-#
-# 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
--- 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 <pmatiello@gmail.com>
-#
-# 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
--- 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 <pmatiello@gmail.com>
-#
-# 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
--- 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 <pmatiello@gmail.com>
-#
-# 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
--- /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)
--- /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 <pmatiello@gmail.com>
+# Christian Muise <christian.muise@gmail.com>
+# Nathan Davis <davisn90210@gmail.com>
+# Zsolt Haraszti <zsolt@drawwell.net>
+#
+# Permission is hereby granted, free of charge, to any person
+# obtaining a copy of this software and associated documentation
+# files (the "Software"), to deal in the Software without
+# restriction, including without limitation the rights to use,
+# copy, modify, merge, publish, distribute, sublicense, and/or sell
+# copies of the Software, and to permit persons to whom the
+# Software is furnished to do so, subject to the following
+# conditions:
+
+# The above copyright notice and this permission notice shall be
+# included in all copies or substantial portions of the Software.
+
+# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+# OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
+# HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+# WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+# OTHER DEALINGS IN THE SOFTWARE.
+
+
+"""
+python-graph
+
+A library for working with graphs in Python.
+
+@version: 1.3.1
+"""
+
+
+# Imports
+import accessibility
+import generators
+import minmax
+import searching
+import sorting
+import readwrite
+import traversal
+
+
+# Graph class --------------------------------------------------------------------------------------
+
+class graph (object):
+ """
+ Graph class.
+
+ Graphs are built of nodes and edges.
+
+ @sort: __init__, __getitem__, __iter__, __len__, __str__, add_edge, add_edge_attribute,
+ add_graph, add_node, add_node_attribute, add_nodes, add_spanning_tree, complete, del_edge,
+ del_node, edges, get_edge_attributes, get_edge_label, get_edge_weight, get_node_attributes,
+ has_edge, has_node, inverse, neighbors, nodes, order, set_edge_label, set_edge_weight,
+ traversal, generate, read, write, accessibility, breadth_first_search, connected_components,
+ cut_edges, cut_nodes, depth_first_search, minimal_spanning_tree, shortest_path
+ """
+
+
+ def __init__(self):
+ """
+ Initialize a graph.
+ """
+ self.node_neighbors = {} # Pairing: Node -> Neighbors
+ self.edge_properties = {} # Pairing: Edge -> (Label, Weight)
+ self.node_attr = {} # Pairing: Node -> Attributes
+ self.edge_attr = {} # Pairing: Edge -> Attributes
+
+
+ def __str__(self):
+ """
+ Return a string representing the graph when requested by str() (or print).
+
+ @rtype: string
+ @return: String representing the graph.
+ """
+ return "<graph object " + str(self.nodes()) + " " + str(self.edges()) + ">"
+
+
+ def __len__(self):
+ """
+ Return the order of the graph when requested by len().
+
+ @rtype: number
+ @return: Size of the graph.
+ """
+ return len(self.node_neighbors)
+
+
+ def __iter__(self):
+ """
+ Return a iterator passing through all nodes in the graph.
+
+ @rtype: iterator
+ @return: Iterator passing through all nodes in the graph.
+ """
+ for each in self.node_neighbors.iterkeys():
+ yield each
+
+
+ def __getitem__(self, node):
+ """
+ Return a iterator passing through all neighbors of the given node.
+
+ @rtype: iterator
+ @return: Iterator passing through all neighbors of the given node.
+ """
+ for each in self.node_neighbors[node]:
+ yield each
+
+
+ def read(self, string, fmt='xml'):
+ """
+ Read a graph from a string. Nodes and edges specified in the input will be added to the
+ current graph.
+
+ @type string: string
+ @param string: Input string specifying a graph.
+
+ @type fmt: string
+ @param fmt: Input format. Possible formats are:
+ 1. 'xml' - XML (default)
+ """
+ if (fmt == 'xml'):
+ readwrite.read_xml(self, string)
+
+
+ def write(self, fmt='xml'):
+ """
+ Write the graph to a string. Depending of the output format, this string can be used by
+ read() to rebuild the graph.
+
+ @type fmt: string
+ @param fmt: Output format. Possible formats are:
+ 1. 'xml' - XML (default)
+ 2. 'dot' - DOT Language (for GraphViz)
+ 3. 'dotwt' - DOT Language with weight information
+
+ @rtype: string
+ @return: String specifying the graph.
+ """
+ if (fmt == 'xml'):
+ return readwrite.write_xml(self)
+ elif (fmt == 'dot'):
+ return readwrite.write_dot_graph(self, False)
+ elif (fmt == 'dotwt'):
+ return readwrite.write_dot_graph(self, True)
+
+
+ def generate(self, num_nodes, num_edges, weight_range=(1, 1)):
+ """
+ Add nodes and random edges to the graph.
+
+ @type num_nodes: number
+ @param num_nodes: Number of nodes.
+
+ @type num_edges: number
+ @param num_edges: Number of edges.
+
+ @type weight_range: tuple
+ @param weight_range: tuple of two integers as lower and upper limits on randomly generated
+ weights (uniform distribution).
+ """
+ generators.generate(self, num_nodes, num_edges, weight_range)
+
+
+ def nodes(self):
+ """
+ Return node list.
+
+ @rtype: list
+ @return: Node list.
+ """
+ return self.node_neighbors.keys()
+
+
+ def neighbors(self, node):
+ """
+ Return all nodes that are directly accessible from given node.
+
+ @type node: node
+ @param node: Node identifier
+
+ @rtype: list
+ @return: List of nodes directly accessible from given node.
+ """
+ return self.node_neighbors[node]
+
+
+ def edges(self):
+ """
+ Return all edges in the graph.
+
+ @rtype: list
+ @return: List of all edges in the graph.
+ """
+ return self.edge_properties.keys()
+
+
+ def has_node(self, node):
+ """
+ Return whether the requested node exists.
+
+ @type node: node
+ @param node: Node identifier
+
+ @rtype: boolean
+ @return: Truth-value for node existence.
+ """
+ return self.node_neighbors.has_key(node)
+
+
+ def add_node(self, node, attrs=[]):
+ """
+ Add given node to the graph.
+
+ @attention: While nodes can be of any type, it's strongly recommended to use only numbers
+ and single-line strings as node identifiers if you intend to use write().
+
+ @type node: node
+ @param node: Node identifier.
+
+ @type attrs: list
+ @param attrs: List of node attributes specified as (attribute, value) tuples.
+ """
+ if (not node in self.node_neighbors):
+ self.node_neighbors[node] = []
+ self.node_attr[node] = attrs
+
+
+ def add_nodes(self, nodelist):
+ """
+ Add given nodes to the graph.
+
+ @attention: While nodes can be of any type, it's strongly recommended to use only numbers
+ and single-line strings as node identifiers if you intend to use write().
+
+ @type nodelist: list
+ @param nodelist: List of nodes to be added to the graph.
+ """
+ for each in nodelist:
+ self.add_node(each)
+
+
+ def add_edge(self, u, v, wt=1, label='', attrs=[]):
+ """
+ Add an edge (u,v) to the graph connecting nodes u and v.
+
+ @type u: node
+ @param u: One node.
+
+ @type v: node
+ @param v: Other node.
+
+ @type wt: number
+ @param wt: Edge weight.
+
+ @type label: string
+ @param label: Edge label.
+
+ @type attrs: list
+ @param attrs: List of node attributes specified as (attribute, value) tuples.
+ """
+ if (v not in self.node_neighbors[u] and u not in self.node_neighbors[v]):
+ self.node_neighbors[u].append(v)
+ self.node_neighbors[v].append(u)
+ self.edge_properties[(u, v)] = [label, wt]
+ self.edge_properties[(v, u)] = [label, wt]
+ self.edge_attr[(u, v)] = attrs
+ self.edge_attr[(v, u)] = attrs
+
+
+ def del_node(self, node):
+ """
+ Remove a node from the graph.
+
+ @type node: node
+ @param node: Node identifier.
+ """
+ for each in list(self.neighbors(node)):
+ self.del_edge(each, node)
+ del(self.node_neighbors[node])
+ del(self.node_attr[node])
+
+
+ def del_edge(self, u, v):
+ """
+ Remove an edge (u, v) from the graph.
+
+ @type u: node
+ @param u: One node.
+
+ @type v: node
+ @param v: Other node.
+ """
+ self.node_neighbors[u].remove(v)
+ self.node_neighbors[v].remove(u)
+ del(self.edge_properties[(u,v)])
+ del(self.edge_properties[(v,u)])
+ del(self.edge_attr[(u,v)])
+ del(self.edge_attr[(v,u)])
+
+
+ def get_edge_weight(self, u, v):
+ """
+ Get the weight of an edge.
+
+ @type u: node
+ @param u: One node.
+
+ @type v: node
+ @param v: Other node.
+
+ @rtype: number
+ @return: Edge weight.
+ """
+ return self.edge_properties[(u, v)][1]
+
+
+ def set_edge_weight(self, u, v, wt):
+ """
+ Set the weight of an edge.
+
+ @type u: node
+ @param u: One node.
+
+ @type v: node
+ @param v: Other node.
+
+ @type wt: number
+ @param wt: Edge weight.
+ """
+ self.edge_properties[(u, v)][1] = wt
+ self.edge_properties[(v, u)][1] = wt
+
+
+ def get_edge_label(self, u, v):
+ """
+ Get the label of an edge.
+
+ @type u: node
+ @param u: One node.
+
+ @type v: node
+ @param v: Other node.
+
+ @rtype: string
+ @return: Edge label
+ """
+ return self.edge_properties[(u, v)][0]
+
+
+ def set_edge_label(self, u, v, label):
+ """
+ Set the label of an edge.
+
+ @type u: node
+ @param u: One node.
+
+ @type v: node
+ @param v: Other node.
+
+ @type label: string
+ @param label: Edge label.
+ """
+ self.edge_properties[(u, v)][0] = label
+ self.edge_properties[(v, u)][0] = label
+
+
+ def add_node_attribute(self, node, attr):
+ """
+ Add attribute to the given node.
+
+ @type node: node
+ @param node: Node identifier
+
+ @type attr: tuple
+ @param attr: Node attribute specified as a tuple in the form (attribute, value).
+ """
+ self.node_attr[node] = self.node_attr[node] + [attr]
+
+
+ def get_node_attributes(self, node):
+ """
+ Return the attributes of the given node.
+
+ @type node: node
+ @param node: Node identifier
+
+ @rtype: list
+ @return: List of attributes specified tuples in the form (attribute, value).
+ """
+ return self.node_attr[node]
+
+
+ def add_edge_attribute(self, u, v, attr):
+ """
+ Add attribute to the given edge.
+
+ @type u: node
+ @param u: One node.
+
+ @type v: node
+ @param v: Other node.
+
+ @type attr: tuple
+ @param attr: Node attribute specified as a tuple in the form (attribute, value).
+ """
+ self.edge_attr[(u,v)] = self.edge_attr[(u,v)] + [attr]
+ self.edge_attr[(v,u)] = self.edge_attr[(v,u)] + [attr]
+
+
+ def get_edge_attributes(self, u, v):
+ """
+ Return the attributes of the given edge.
+
+ @type u: node
+ @param u: One node.
+
+ @type v: node
+ @param v: Other node.
+
+ @rtype: list
+ @return: List of attributes specified tuples in the form (attribute, value).
+ """
+ return self.edge_attr[(u,v)]
+
+
+ def has_edge(self, u, v):
+ """
+ Return whether an edge between nodes u and v exists.
+
+ @type u: node
+ @param u: One node.
+
+ @type v: node
+ @param v: Other node.
+
+ @rtype: boolean
+ @return: Truth-value for edge existence.
+ """
+ return self.edge_properties.has_key((u,v)) and self.edge_properties.has_key((v,u))
+
+
+ def order(self, node):
+ """
+ Return the order of the given node.
+
+ @rtype: number
+ @return: Order of the given node.
+ """
+ return len(self.neighbors(node))
+
+
+ def complete(self):
+ """
+ Make the graph a complete graph.
+
+ @attention: This will modify the current graph.
+ """
+ for each in self.nodes():
+ for other in self.nodes():
+ if (each != other):
+ self.add_edge(each, other)
+
+
+ def inverse(self):
+ """
+ Return the inverse of the graph.
+
+ @rtype: graph
+ @return: Complement graph for the graph.
+ """
+ inv = graph()
+ inv.add_nodes(self.nodes())
+ inv.complete()
+ for each in self.edges():
+ if (inv.has_edge(each[0], each[1])):
+ inv.del_edge(each[0], each[1])
+ return inv
+
+
+ def add_graph(self, graph):
+ """
+ Add other graph to the graph.
+
+ @attention: Attributes and labels are not preserved.
+
+ @type graph: graph
+ @param graph: Graph
+ """
+ self.add_nodes(graph.nodes())
+ for each_node in graph.nodes():
+ for each_edge in graph.neighbors(each_node):
+ self.add_edge(each_node, each_edge)
+
+
+ def add_spanning_tree(self, st):
+ """
+ Add a spanning tree to the graph.
+
+ @type st: dictionary
+ @param st: Spanning tree.
+ """
+ self.add_nodes(st.keys())
+ for each in st:
+ if (st[each] is not None):
+ self.add_edge(st[each], each)
+
+
+ def traversal(self, node, order='pre'):
+ """
+ Graph traversal iterator.
+
+ @type node: node
+ @param node: Node.
+
+ @type order: string
+ @param order: traversal ordering. Possible values are:
+ 2. 'pre' - Preordering (default)
+ 1. 'post' - Postordering
+
+ @rtype: iterator
+ @return: Traversal iterator.
+ """
+ for each in traversal.traversal(self, node, order):
+ yield each
+
+
+ def depth_first_search(self, root=None):
+ """
+ Depht-first search.
+
+ @type root: node
+ @param root: Optional root node (will explore only root's connected component)
+
+ @rtype: tuple
+ @return: tupple containing a dictionary and two lists:
+ 1. Generated spanning tree
+ 2. Graph's preordering
+ 3. Graph's postordering
+ """
+ return searching.depth_first_search(self, root)
+
+
+ def breadth_first_search(self, root=None):
+ """
+ Breadth-first search.
+
+ @type root: node
+ @param root: Optional root node (will explore only root's connected component)
+
+ @rtype: dictionary
+ @return: A tuple containing a dictionary and a list.
+ 1. Generated spanning tree
+ 2. Graph's level-based ordering
+ """
+ return searching.breadth_first_search(self, root)
+
+
+ def accessibility(self):
+ """
+ Accessibility matrix (transitive closure).
+
+ @rtype: dictionary
+ @return: Accessibility information for each node.
+ """
+ return accessibility.accessibility(self)
+
+
+ def connected_components(self):
+ """
+ Connected components.
+
+ @attention: Indentification of connected components is meaningful only for non-directed
+ graphs.
+
+ @rtype: dictionary
+ @return: Pairing that associates each node to its connected component.
+ """
+ return accessibility.connected_components(self)
+
+
+ def minimal_spanning_tree(self, root=None):
+ """
+ Minimal spanning tree.
+
+ @type root: node
+ @param root: Optional root node (will explore only root's connected component)
+
+ @attention: Minimal spanning tree meaningful only for weighted graphs.
+
+ @rtype: list
+ @return: Generated spanning tree.
+ """
+ return minmax.minimal_spanning_tree(self, root)
+
+
+ def shortest_path(self, source):
+ """
+ Return the shortest path distance between source node and all other nodes using Dijkstra's
+ algorithm.
+
+ @attention: All weights must be nonnegative.
+
+ @type source: node
+ @param source: Node from which to start the search.
+
+ @rtype: tuple
+ @return: A tuple containing two dictionaries, each keyed by target nodes.
+ 1. Shortest path spanning tree
+ 2. Shortest distance from given source to each target node
+ Inaccessible target nodes do not appear in either dictionary.
+ """
+ return minmax.shortest_path(self, source)
+
+
+ def cut_edges(self):
+ """
+ Return the cut-edges of the given graph.
+
+ @rtype: list
+ @return: List of cut-edges.
+ """
+ return accessibility.cut_edges(self)
+
+
+ def cut_nodes(self):
+ """
+ Return the cut-nodes of the given graph.
+
+ @rtype: list
+ @return: List of cut-nodes.
+ """
+ return accessibility.cut_nodes(self)
+
+
+# Digraph class ------------------------------------------------------------------------------------
+
+class digraph (object):
+ """
+ Digraph class.
+
+ Digraphs are built of nodes and directed edges.
+
+ @sort: __init__, __getitem__, __iter__, __len__, __str__, add_edge, add_edge_attribute,
+ add_graph, add_node, add_node_attribute, add_nodes, add_spanning_tree, complete, degree,
+ del_edge, del_node, edges, get_edge_attributes, get_edge_label, get_edge_weight,
+ get_node_attributes, has_edge, has_node, incidents, inverse, neighbors, nodes, order,
+ set_edge_label, set_edge_weight, traversal, generate, read, write, accessibility,
+ breadth_first_search, cut_edges, cut_nodes, depth_first_search, minimal_spanning_tree,
+ mutual_accessibility, shortest_path, topological_sorting
+ """
+
+
+ def __init__(self):
+ """
+ Initialize a digraph.
+ """
+ self.node_neighbors = {} # Pairing: Node -> Neighbors
+ self.edge_properties = {} # Pairing: Edge -> (Label, Weight)
+ self.node_incidence = {} # Pairing: Node -> Incident nodes
+ self.node_attr = {} # Pairing: Node -> Attributes
+ self.edge_attr = {} # Pairing: Edge -> Attributes
+
+
+ def __str__(self):
+ """
+ Return a string representing the digraph when requested by str() (or print).
+
+ @rtype: string
+ @return: String representing the graph.
+ """
+ return "<graph object " + str(self.nodes()) + " " + str(self.edges()) + ">"
+
+
+ def __len__(self):
+ """
+ Return the order of the digraph when requested by len().
+
+ @rtype: number
+ @return: Size of the graph.
+ """
+ return len(self.node_neighbors)
+
+
+ def __iter__(self):
+ """
+ Return a iterator passing through all nodes in the digraph.
+
+ @rtype: iterator
+ @return: Iterator passing through all nodes in the digraph.
+ """
+ for each in self.node_neighbors.iterkeys():
+ yield each
+
+
+ def __getitem__(self, node):
+ """
+ Return a iterator passing through all neighbors of the given node.
+
+ @rtype: iterator
+ @return: Iterator passing through all neighbors of the given node.
+ """
+ for each in self.node_neighbors[node]:
+ yield each
+
+
+ def read(self, string, fmt='xml'):
+ """
+ Read a graph from a string. Nodes and edges specified in the input will be added to the
+ current graph.
+
+ @type string: string
+ @param string: Input string specifying a graph.
+
+ @type fmt: string
+ @param fmt: Input format. Possible formats are:
+ 1. 'xml' - XML (default)
+ """
+ if (fmt == 'xml'):
+ readwrite.read_xml(self, string)
+
+
+ def write(self, fmt='xml'):
+ """
+ Write the graph to a string. Depending of the output format, this string can be used by
+ read() to rebuild the graph.
+
+ @type fmt: string
+ @param fmt: Output format. Possible formats are:
+ 1. 'xml' - XML (default)
+ 2. 'dot' - DOT Language (for GraphViz)
+ 3. 'dotwt' - DOT Language with weight information
+
+ @rtype: string
+ @return: String specifying the graph.
+ """
+ if (fmt == 'xml'):
+ return readwrite.write_xml(self)
+ elif (fmt == 'dot'):
+ return readwrite.write_dot_digraph(self, False)
+ elif (fmt == 'dotwt'):
+ return readwrite.write_dot_digraph(self, True)
+
+
+ def generate(self, num_nodes, num_edges, weight_range=(1, 1)):
+ """
+ Add nodes and random edges to the graph.
+
+ @type num_nodes: number
+ @param num_nodes: Number of nodes.
+
+ @type num_edges: number
+ @param num_edges: Number of edges.
+
+ @type weight_range: tuple
+ @param weight_range: tuple of two integers as lower and upper limits on randomly generated
+ weights (uniform distribution).
+ """
+ generators.generate(self, num_nodes, num_edges, weight_range)
+
+
+ def nodes(self):
+ """
+ Return node list.
+
+ @rtype: list
+ @return: Node list.
+ """
+ return self.node_neighbors.keys()
+
+
+ def neighbors(self, node):
+ """
+ Return all nodes that are directly accessible from given node.
+
+ @type node: node
+ @param node: Node identifier
+
+ @rtype: list
+ @return: List of nodes directly accessible from given node.
+ """
+ return self.node_neighbors[node]
+
+
+ def incidents(self, node):
+ """
+ Return all nodes that are incident to the given node.
+
+ @type node: node
+ @param node: Node identifier
+
+ @rtype: list
+ @return: List of nodes directly accessible from given node.
+ """
+ return self.node_incidence[node]
+
+
+
+ def edges(self):
+ """
+ Return all edges in the graph.
+
+ @rtype: list
+ @return: List of all edges in the graph.
+ """
+ return self.edge_properties.keys()
+
+
+ def has_node(self, node):
+ """
+ Return whether the requested node exists.
+
+ @type node: node
+ @param node: Node identifier
+
+ @rtype: boolean
+ @return: Truth-value for node existence.
+ """
+ return self.node_neighbors.has_key(node)
+
+
+ def add_node(self, node, attrs=[]):
+ """
+ Add given node to the graph.
+
+ @attention: While nodes can be of any type, it's strongly recommended to use only numbers
+ and single-line strings as node identifiers if you intend to use write().
+
+ @type node: node
+ @param node: Node identifier.
+
+ @type attrs: list
+ @param attrs: List of node attributes specified as (attribute, value) tuples.
+ """
+ if (node not in self.node_neighbors):
+ self.node_neighbors[node] = []
+ self.node_incidence[node] = []
+ self.node_attr[node] = attrs
+
+
+ def add_nodes(self, nodelist):
+ """
+ Add given nodes to the graph.
+
+ @attention: While nodes can be of any type, it's strongly recommended to use only numbers
+ and single-line strings as node identifiers if you intend to use write().
+
+ @type nodelist: list
+ @param nodelist: List of nodes to be added to the graph.
+ """
+ for each in nodelist:
+ self.add_node(each)
+
+
+ def add_edge(self, u, v, wt=1, label='', attrs=[]):
+ """
+ Add an directed edge (u,v) to the graph connecting nodes u to v.
+
+ @type u: node
+ @param u: One node.
+
+ @type v: node
+ @param v: Other node.
+
+ @type wt: number
+ @param wt: Edge weight.
+
+ @type label: string
+ @param label: Edge label.
+
+ @type attrs: list
+ @param attrs: List of node attributes specified as (attribute, value) tuples.
+ """
+ if (v not in self.node_neighbors[u]):
+ self.node_neighbors[u].append(v)
+ self.node_incidence[v].append(u)
+ self.edge_properties[(u, v)] = [label, wt]
+ self.edge_attr[(u, v)] = attrs
+
+
+ def del_node(self, node):
+ """
+ Remove a node from the graph.
+
+ @type node: node
+ @param node: Node identifier.
+ """
+ for each in list(self.incidents(node)):
+ self.del_edge(each, node)
+ for each in list(self.neighbors(node)):
+ self.del_edge(node, each)
+ del(self.node_neighbors[node])
+ del(self.node_incidence[node])
+ del(self.node_attr[node])
+
+
+ def del_edge(self, u, v):
+ """
+ Remove an directed edge (u, v) from the graph.
+
+ @type u: node
+ @param u: One node.
+
+ @type v: node
+ @param v: Other node.
+ """
+ self.node_neighbors[u].remove(v)
+ self.node_incidence[v].remove(u)
+ del(self.edge_properties[(u,v)])
+ del(self.edge_attr[(u,v)])
+
+
+ def get_edge_weight(self, u, v):
+ """
+ Get the weight of an edge.
+
+ @type u: node
+ @param u: One node.
+
+ @type v: node
+ @param v: Other node.
+
+ @rtype: number
+ @return: Edge weight.
+ """
+ return self.edge_properties[(u, v)][1]
+
+
+ def set_edge_weight(self, u, v, wt):
+ """
+ Set the weight of an edge.
+
+ @type u: node
+ @param u: One node.
+
+ @type v: node
+ @param v: Other node.
+
+ @type wt: number
+ @param wt: Edge weight.
+ """
+ self.edge_properties[(u, v)][1] = wt
+
+
+ def get_edge_label(self, u, v):
+ """
+ Get the label of an edge.
+
+ @type u: node
+ @param u: One node.
+
+ @type v: node
+ @param v: Other node.
+
+ @rtype: string
+ @return: Edge label
+ """
+ return self.edge_properties[(u, v)][0]
+
+
+ def set_edge_label(self, u, v, label):
+ """
+ Set the label of an edge.
+
+ @type u: node
+ @param u: One node.
+
+ @type v: node
+ @param v: Other node.
+
+ @type label: string
+ @param label: Edge label.
+ """
+ self.edge_properties[(u, v)][0] = label
+
+
+ def add_node_attribute(self, node, attr):
+ """
+ Add attribute to the given node.
+
+ @type node: node
+ @param node: Node identifier
+
+ @type attr: tuple
+ @param attr: Node attribute specified as a tuple in the form (attribute, value).
+ """
+ self.node_attr[node] = self.node_attr[node] + [attr]
+
+
+ def get_node_attributes(self, node):
+ """
+ Return the attributes of the given node.
+
+ @type node: node
+ @param node: Node identifier
+
+ @rtype: list
+ @return: List of attributes specified tuples in the form (attribute, value).
+ """
+ return self.node_attr[node]
+
+
+ def add_edge_attribute(self, u, v, attr):
+ """
+ Add attribute to the given edge.
+
+ @type u: node
+ @param u: One node.
+
+ @type v: node
+ @param v: Other node.
+
+ @type attr: tuple
+ @param attr: Node attribute specified as a tuple in the form (attribute, value).
+ """
+ self.edge_attr[(u,v)] = self.edge_attr[(u,v)] + [attr]
+
+
+ def get_edge_attributes(self, u, v):
+ """
+ Return the attributes of the given edge.
+
+ @type u: node
+ @param u: One node.
+
+ @type v: node
+ @param v: Other node.
+
+ @rtype: list
+ @return: List of attributes specified tuples in the form (attribute, value).
+ """
+ return self.edge_attr[(u,v)]
+
+
+ def has_edge(self, u, v):
+ """
+ Return whether an edge between nodes u and v exists.
+
+ @type u: node
+ @param u: One node.
+
+ @type v: node
+ @param v: Other node.
+
+ @rtype: boolean
+ @return: Truth-value for edge existence.
+ """
+ return self.edge_properties.has_key((u,v))
+
+
+ def order(self, node):
+ """
+ Return the order of the given node.
+
+ @rtype: number
+ @return: Order of the given node.
+ """
+ return len(self.neighbors(node))
+
+
+ def degree(self, node):
+ """
+ Return the degree of the given node.
+
+ @rtype: number
+ @return: Order of the given node.
+ """
+ return len(self.node_incidence[node])
+
+
+ def complete(self):
+ """
+ Make the graph a complete graph.
+
+ @attention: This will modify the current graph.
+ """
+ for each in self.nodes():
+ for other in self.nodes():
+ if (each != other):
+ self.add_edge(each, other)
+
+
+ def inverse(self):
+ """
+ Return the inverse of the graph.
+
+ @rtype: graph
+ @return: Complement graph for the graph.
+ """
+ inv = digraph()
+ inv.add_nodes(self.nodes())
+ inv.complete()
+ for each in self.edges():
+ inv.del_edge(each[0], each[1])
+ return inv
+
+
+ def add_graph(self, graph):
+ """
+ Add other graph to the graph.
+
+ @attention: Attributes and labels are not preserved.
+
+ @type graph: graph
+ @param graph: Graph
+ """
+ self.add_nodes(graph.nodes())
+ for each_node in graph.nodes():
+ for each_edge in graph.neighbors(each_node):
+ self.add_edge(each_node, each_edge)
+
+
+ def add_spanning_tree(self, st):
+ """
+ Add a spanning tree to the graph.
+
+ @type st: dictionary
+ @param st: Spanning tree.
+ """
+ self.add_nodes(st.keys())
+ for each in st:
+ if (st[each] is not None):
+ self.add_edge(st[each], each)
+
+
+ def traversal(self, node, order='pre'):
+ """
+ Graph traversal iterator.
+
+ @type node: node
+ @param node: Node.
+
+ @type order: string
+ @param order: traversal ordering. Possible values are:
+ 2. 'pre' - Preordering (default)
+ 1. 'post' - Postordering
+
+ @rtype: iterator
+ @return: Traversal iterator.
+ """
+ for each in traversal.traversal(self, node, order):
+ yield each
+
+
+ def depth_first_search(self, root=None):
+ """
+ Depht-first search.
+
+ @type root: node
+ @param root: Optional root node (will explore only root's connected component)
+
+ @rtype: tuple
+ @return: tupple containing a dictionary and two lists:
+ 1. Generated spanning tree
+ 2. Graph's preordering
+ 3. Graph's postordering
+ """
+ return searching.depth_first_search(self, root)
+
+
+ def accessibility(self):
+ """
+ Accessibility matrix (transitive closure).
+
+ @rtype: dictionary
+ @return: Accessibility information for each node.
+ """
+ return accessibility.accessibility(self)
+
+
+ def breadth_first_search(self, root=None):
+ """
+ Breadth-first search.
+
+ @type root: node
+ @param root: Optional root node (will explore only root's connected component)
+
+ @rtype: dictionary
+ @return: A tuple containing a dictionary and a list.
+ 1. Generated spanning tree
+ 2. Graph's level-based ordering
+ """
+ return searching.breadth_first_search(self, root)
+
+
+ def mutual_accessibility(self):
+ """
+ Mutual-accessibility matrix (strongly connected components).
+
+ @rtype: list
+ @return: Mutual-accessibility information for each node.
+ """
+ return accessibility.mutual_accessibility(self)
+
+
+ def topological_sorting(self):
+ """
+ Topological sorting.
+
+ @attention: Topological sorting is meaningful only for directed acyclic graphs.
+
+ @rtype: list
+ @return: Topological sorting for the graph.
+ """
+ return sorting.topological_sorting(self)
+
+
+ def minimal_spanning_tree(self, root=None):
+ """
+ Minimal spanning tree.
+
+ @type root: node
+ @param root: Optional root node (will explore only root's connected component)
+
+ @attention: Minimal spanning tree meaningful only for weighted graphs.
+
+ @rtype: list
+ @return: Generated spanning tree.
+ """
+ return minmax.minimal_spanning_tree(self, root)
+
+
+ def shortest_path(self, source):
+ """
+ Return the shortest path distance between source node and all other nodes using Dijkstra's
+ algorithm.
+
+ @attention: All weights must be nonnegative.
+
+ @type source: node
+ @param source: Node from which to start the search.
+
+ @rtype: tuple
+ @return: A tuple containing two dictionaries, each keyed by target nodes.
+ 1. Shortest path spanning tree
+ 2. Shortest distance from given source to each target node
+ Inaccessible target nodes do not appear in either dictionary.
+ """
+ return minmax.shortest_path(self, source)
+
+
+ def cut_edges(self):
+ """
+ Return the cut-edges of the given graph.
+
+ @rtype: list
+ @return: List of cut-edges.
+ """
+ return accessibility.cut_edges(self)
+
+
+ def cut_nodes(self):
+ """
+ Return the cut-nodes of the given graph.
+
+ @rtype: list
+ @return: List of cut-nodes.
+ """
+ return accessibility.cut_nodes(self)
+
+
+# Hypergraph class ---------------------------------------------------------------------------------
+
+class hypergraph (object):
+ """
+ Hypergraph class.
+
+ Hypergraphs are a generalization of graphs where an edge (called hyperedge) can connect more
+ than two nodes.
+
+ @sort: __init__, __len__, __str__, add_hyperedge, add_hyperedges, add_node, add_nodes, has_node,
+ hyperedges, link, links, nodes, unlink, read, write, accessibility, connected_components,
+ cut_hyperedges, cut_nodes
+ """
+
+
+ def __init__(self):
+ """
+ Initialize a hypergraph.
+ """
+ self.node_links = {} # Pairing: Node -> Hyperedge
+ self.edge_links = {} # Pairing: Hyperedge -> Node
+ self.graph = graph() # Ordinary graph
+
+
+ def __str__(self):
+ """
+ Return a string representing the hypergraph when requested by str() (or print).
+
+ @rtype: string
+ @return: String representing the hypergraph.
+ """
+ return "<hypergraph object " + str(self.nodes()) + " " + str(self.edge_links) + ">"
+
+
+ def __len__(self):
+ """
+ Return the size of the hypergraph when requested by len().
+
+ @rtype: number
+ @return: Size of the hypergraph.
+ """
+ return len(self.node_links)
+
+
+ def read(self, string, fmt='xml'):
+ """
+ Read a hypergraph from a string. Nodes and hyperedges specified in the input will be added
+ to the current graph.
+
+ @type string: string
+ @param string: Input string specifying a graph.
+
+ @type fmt: string
+ @param fmt: Input format. Possible formats are:
+ 1. 'xml' - XML (default)
+ """
+ if (fmt == 'xml'):
+ readwrite.read_xml_hypergraph(self, string)
+
+
+ def write(self, fmt='xml'):
+ """
+ Write the hypergraph to a string. Depending of the output format, this string can be used by
+ read() to rebuild the graph.
+
+ @type fmt: string
+ @param fmt: Output format. Possible formats are:
+ 1. 'xml' - XML (default)
+ 2. 'dot' - DOT Language (for GraphViz)
+ 3. 'dotclr' - DOT Language, coloured
+
+ @rtype: string
+ @return: String specifying the graph.
+ """
+ if (fmt == 'xml'):
+ return readwrite.write_xml_hypergraph(self)
+ elif (fmt == 'dot'):
+ return readwrite.write_dot_hypergraph(self)
+ elif (fmt == 'dotclr'):
+ return readwrite.write_dot_hypergraph(self, coloured=True)
+
+
+ def nodes(self):
+ """
+ Return node list.
+
+ @rtype: list
+ @return: Node list.
+ """
+ return self.node_links.keys()
+
+
+ def hyperedges(self):
+ """
+ Return hyperedge list.
+
+ @rtype: list
+ @return: List of hyperedges linked to the given node.
+ """
+ return self.edge_links.keys()
+
+
+ def links(self, obj):
+ """
+ Return all objects linked to the given one.
+
+ If given a node, linked hyperedges will be returned. If given a hyperedge, linked nodes will
+ be returned.
+
+ @type obj: node or hyperedge
+ @param obj: Object identifier.
+
+ @rtype: list
+ @return: List of objects linked to the given one.
+ """
+ if (obj in self.node_links):
+ return self.node_links[obj]
+ else:
+ return self.edge_links[obj]
+
+
+ def has_node(self, node):
+ """
+ Return whether the requested node exists.
+
+ @type node: node
+ @param node: Node identifier
+
+ @rtype: boolean
+ @return: Truth-value for node existence.
+ """
+ return self.node_links.has_key(node)
+
+
+ def add_node(self, node):
+ """
+ Add given node to the hypergraph.
+
+ @attention: While nodes can be of any type, it's strongly recommended to use only numbers
+ and single-line strings as node identifiers if you intend to use write().
+
+ @type node: node
+ @param node: Node identifier.
+ """
+ if (not node in self.node_links):
+ self.node_links[node] = []
+ self.graph.add_node((node,'n'))
+
+
+ def add_nodes(self, nodelist):
+ """
+ Add given nodes to the hypergraph.
+
+ @attention: While nodes can be of any type, it's strongly recommended to use only numbers
+ and single-line strings as node identifiers if you intend to use write().
+
+ @type nodelist: list
+ @param nodelist: List of nodes to be added to the graph.
+ """
+ for each in nodelist:
+ self.add_node(each)
+
+
+ def add_hyperedge(self, hyperedge):
+ """
+ Add given hyperedge to the hypergraph.
+
+ @attention: While hyperedge-nodes can be of any type, it's strongly recommended to use only
+ numbers and single-line strings as node identifiers if you intend to use write().
+
+ @type hyperedge: hyperedge
+ @param hyperedge: Hyperedge identifier.
+ """
+ if (not hyperedge in self.edge_links):
+ self.edge_links[hyperedge] = []
+ self.graph.add_node((hyperedge,'h'))
+
+
+ def add_hyperedges(self, edgelist):
+ """
+ Add given hyperedges to the hypergraph.
+
+ @attention: While hyperedge-nodes can be of any type, it's strongly recommended to use only
+ numbers and single-line strings as node identifiers if you intend to use write().
+
+ @type edgelist: list
+ @param edgelist: List of hyperedge-nodes to be added to the graph.
+ """
+ for each in edgelist:
+ self.add_hyperedge(each)
+
+
+ def link(self, node, hyperedge):
+ """
+ Link given node and hyperedge.
+
+ @type node: node
+ @param node: Node.
+
+ @type hyperedge: node
+ @param hyperedge: Hyperedge.
+ """
+ if (hyperedge not in self.node_links[node]):
+ self.node_links[node].append(hyperedge)
+ self.edge_links[hyperedge].append(node)
+ self.graph.add_edge((node,'n'), (hyperedge,'h'))
+
+
+ def unlink(self, node, hyperedge):
+ """
+ Unlink given node and hyperedge.
+
+ @type node: node
+ @param node: Node.
+
+ @type hyperedge: hyperedge
+ @param hyperedge: Hyperedge.
+ """
+ self.node_links[node].remove(hyperedge)
+ self.edge_links[hyperedge].remove(node)
+
+
+ def accessibility(self):
+ """
+ Accessibility matrix (transitive closure).
+
+ @rtype: dictionary
+ @return: Accessibility information for each node.
+ """
+ access_ = accessibility.accessibility(self.graph)
+ access = {}
+
+ for each in access_.keys():
+ if (each[1] == 'n'):
+ access[each[0]] = []
+ for other in access_[each]:
+ if (other[1] == 'n'):
+ access[each[0]].append(other[0])
+
+ return access
+
+
+ def connected_components(self):
+ """
+ Connected components.
+
+ @rtype: dictionary
+ @return: Pairing that associates each node to its connected component.
+ """
+ components_ = accessibility.connected_components(self.graph)
+ components = {}
+
+ for each in components_.keys():
+ if (each[1] == 'n'):
+ components[each[0]] = components_[each]
+
+ return components
+
+
+ def cut_nodes(self):
+ """
+ Return the cut-nodes of the given hypergraph.
+
+ @rtype: list
+ @return: List of cut-nodes.
+ """
+ cut_nodes_ = accessibility.cut_nodes(self.graph)
+ cut_nodes = []
+
+ for each in cut_nodes_:
+ if (each[1] == 'n'):
+ cut_nodes.append(each[0])
+
+ return cut_nodes
+
+
+ def cut_hyperedges(self):
+ """
+ Return the cut-hyperedges of the given hypergraph.
+
+ @rtype: list
+ @return: List of cut-nodes.
+ """
+ cut_nodes_ = accessibility.cut_nodes(self.graph)
+ cut_nodes = []
+
+ for each in cut_nodes_:
+ if (each[1] == 'h'):
+ cut_nodes.append(each[0])
+
+ return cut_nodes
+
+ def rank(self):
+ """
+ Return the rank of the given hypergraph.
+
+ @rtype: int
+ @return: Rank of graph.
+ """
+ max_rank = 0
+
+ for each in hyperedges:
+ if len(each) > max_rank:
+ max_rank = len(each)
+
+ return max_rank
--- /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 <pmatiello@gmail.com>
+#
+# 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]
--- /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 <pmatiello@gmail.com>
+# Zsolt Haraszti <zsolt@drawwell.net>
+#
+# Permission is hereby granted, free of charge, to any person
+# obtaining a copy of this software and associated documentation
+# files (the "Software"), to deal in the Software without
+# restriction, including without limitation the rights to use,
+# copy, modify, merge, publish, distribute, sublicense, and/or sell
+# copies of the Software, and to permit persons to whom the
+# Software is furnished to do so, subject to the following
+# conditions:
+
+# The above copyright notice and this permission notice shall be
+# included in all copies or substantial portions of the Software.
+
+# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+# OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
+# HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+# WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+# OTHER DEALINGS IN THE SOFTWARE.
+
+
+"""
+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))
--- /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 <pmatiello@gmail.com>
+# Rhys Ulerich <rhys.ulerich@gmail.com>
+#
+# 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
--- /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 <pmatiello@gmail.com>
+#
+# 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
--- /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 <pmatiello@gmail.com>
+#
+# 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
--- /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 <pmatiello@gmail.com>
+#
+# 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
--- /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 <pmatiello@gmail.com>
+#
+# 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