[Zope-CVS] CVS: Packages/pypes/pypes - graph.py:1.3
interfaces.py:1.2
Casey Duncan
casey at zope.com
Fri Aug 8 01:58:26 EDT 2003
Update of /cvs-repository/Packages/pypes/pypes
In directory cvs.zope.org:/tmp/cvs-serv4948
Modified Files:
graph.py interfaces.py
Log Message:
Add shortestPath implementation without values
Begin roughing out implementation the uses values
=== Packages/pypes/pypes/graph.py 1.2 => 1.3 ===
--- Packages/pypes/pypes/graph.py:1.2 Tue Aug 5 23:30:49 2003
+++ Packages/pypes/pypes/graph.py Fri Aug 8 00:57:49 2003
@@ -49,7 +49,7 @@
self.edges = DirectedGraphEdges()
self.nodes = DirectedGraphNodes(self.edges)
- def transitiveClosure(self):
+ def transitiveClosure(self, with_values=False):
raise NotImplementedError
@@ -59,9 +59,9 @@
implements(IGraphEdges)
def __init__(self):
- # _nodes is a mapping of nodes => referers, neighbors
+ # _nodes is a mapping of nodes => referers, targets
# The values are a 2-tuple value where each item is one of:
- # None -- No referers/neighbors
+ # None -- No referers/targets
# Node -- Single referer/neighbor
# Set -- BTree set of multiple neighbor/referer nodes
# XXX We should consider storing values here as well using a btree...
@@ -75,7 +75,7 @@
assert source is not None, 'Edge source cannot be None'
assert target is not None, 'Edge target cannot be None'
try:
- referers, neighbors = self._nodes[source]
+ referers, targets = self._nodes[source]
except KeyError:
# source not in graph
added = True
@@ -93,36 +93,36 @@
referers.insert(target)
elif target is not referers:
referers = self._nodeSetFactory((referers, target))
- if neighbors is None:
+ if targets is None:
self._nodes[source] = referers, target
added = True
- elif isinstance(neighbors, self._nodeSetFactory):
- added = neighbors.insert(target)
+ elif isinstance(targets, self._nodeSetFactory):
+ added = targets.insert(target)
if source is target:
# referers may have changed above
- self._nodes[source] = referers, neighbors
- elif target is not neighbors:
+ self._nodes[source] = referers, targets
+ elif target is not targets:
self._nodes[source] = (
- referers, self._nodeSetFactory((neighbors, target)))
+ referers, self._nodeSetFactory((targets, target)))
added = True
else:
added = False
if target is not source:
# update target referers
try:
- referers, neighbors = self._nodes[target]
+ referers, targets = self._nodes[target]
except KeyError:
# target not in graph
self._node_count.change(1)
self._nodes[target] = source, None
else:
if referers is None:
- self._nodes[target] = source, neighbors
+ self._nodes[target] = source, targets
elif isinstance(referers, self._nodeSetFactory):
referers.insert(source)
elif source is not referers:
self._nodes[target] = (
- self._nodeSetFactory((referers, source)), neighbors)
+ self._nodeSetFactory((referers, source)), targets)
if value is not _marker:
self._edge_values[source, target] = value
if added:
@@ -131,20 +131,20 @@
def remove(self, source, target):
try:
- src_referers, src_neighbors = self._nodes[source]
- tgt_referers, tgt_neighbors = self._nodes[target]
+ src_referers, src_targets = self._nodes[source]
+ tgt_referers, tgt_targets = self._nodes[target]
except KeyError:
raise GraphLookupError, (source, target)
else:
- if isinstance(src_neighbors, self._nodeSetFactory):
- if target in src_neighbors:
- src_neighbors.remove(target)
- if not src_neighbors:
+ if isinstance(src_targets, self._nodeSetFactory):
+ if target in src_targets:
+ src_targets.remove(target)
+ if not src_targets:
# replace the empty set with a None for efficiency
self._nodes[source] = src_referers, None
else:
raise GraphLookupError, (source, target)
- elif src_neighbors is target:
+ elif src_targets is target:
self._nodes[source] = src_referers, None
else:
raise GraphLookupError, (source, target)
@@ -152,9 +152,9 @@
tgt_referers.remove(source)
if not tgt_referers:
# replace the empty set with a None for efficiency
- self._nodes[target] = None, tgt_neighbors
+ self._nodes[target] = None, tgt_targets
elif tgt_referers is source:
- self._nodes[target] = None, tgt_neighbors
+ self._nodes[target] = None, tgt_targets
try:
del self._edge_values[source, target]
except KeyError:
@@ -182,13 +182,13 @@
assert source is not None, 'Edge source cannot be None'
assert target is not None, 'Edge target cannot be None'
try:
- referers, neighbors = self._nodes[source]
+ referers, targets = self._nodes[source]
except KeyError:
return False
else:
- return target is neighbors or (
- isinstance(neighbors, self._nodeSetFactory)
- and target in neighbors)
+ return target is targets or (
+ isinstance(targets, self._nodeSetFactory)
+ and target in targets)
def __contains__(self, pair):
return self._has_edge(*pair)
@@ -199,16 +199,16 @@
def __iter__(self):
for source in self._nodes.keys():
try:
- referers, neighbors = self._nodes[source]
+ referers, targets = self._nodes[source]
except KeyError:
# Handle mutation during iteration
continue
else:
- if isinstance(neighbors, self._nodeSetFactory):
- for target in neighbors:
+ if isinstance(targets, self._nodeSetFactory):
+ for target in targets:
yield source, target
- elif neighbors is not None:
- yield source, neighbors
+ elif targets is not None:
+ yield source, targets
def iterValues(self):
return iter(self._edge_values.values())
@@ -216,9 +216,56 @@
def iterItems(self):
return iter(self._edge_values.items())
- def shortestPath(self, source, target, use_values=False):
- raise NotImplementedError
+ def shortestPath(self, source, target, use_values=False):
+ if not self._nodes.has_key(source):
+ raise GraphLookupError, source
+ if not self._nodes.has_key(target):
+ raise GraphLookupError, target
+ if not use_values:
+ return self._breadthSearch(source, target)
+ else:
+ return self._dijkstraSearch(source, target)
+ def _breadthSearch(self, source, target):
+ """Returns the shortest list of nodes connecting source to target
+ without regard to edge values using a breadth-first search. Returns
+ None if no path exists between source and target
+ """
+ seen = {}
+ nodes = [source]
+ path = []
+ while nodes:
+ node = nodes.pop()
+ if seen.has_key(node):
+ continue
+ referers, targets = self._nodes[node]
+ seen[node] = 1
+ if targets is None:
+ continue
+ else:
+ path.append(node)
+ if targets is target:
+ path.append(targets)
+ break
+ if not isinstance(targets, self._nodeSetFactory):
+ if not seen.has_key(targets):
+ nodes.append(targets)
+ elif target in targets:
+ path.append(target)
+ break
+ else:
+ nodes.extend(targets)
+ if path[-1] is target:
+ return path
+
+ def _dijkstraSearch(self, source, target):
+ """Return the shortest list of nodes connecting source to target
+ with the smallest cumulative distance derived from the edge values
+ using Dijkstra's algorithm. Note, this does not work correctly if
+ edges have negative values
+ """
+ raise NotImplementedError
+
class DirectedGraphNodes(ObjectNodeStore, Persistent):
"""Directed graph nodes accessor"""
@@ -241,7 +288,7 @@
def remove(self, obj):
try:
- referers, neighbors = self._nodes[obj]
+ referers, targets = self._nodes[obj]
except KeyError:
raise GraphLookupError, obj
else:
@@ -263,10 +310,10 @@
except KeyError:
pass
self._edge_count.change(-len(referers))
- if neighbors is not None:
- if not isinstance(neighbors, self._nodeSetFactory):
- neighbors = (neighbors,)
- for node in neighbors:
+ if targets is not None:
+ if not isinstance(targets, self._nodeSetFactory):
+ targets = (targets,)
+ for node in targets:
r, n = self._nodes[node]
if isinstance(r, self._nodeSetFactory):
r.remove(obj)
@@ -279,7 +326,7 @@
del self._edge_values[obj, node]
except KeyError:
pass
- self._edge_count.change(-len(neighbors))
+ self._edge_count.change(-len(targets))
except KeyError:
# Graph not consistent
raise PypesError, 'Graph inconsistency error'
@@ -300,14 +347,14 @@
def degree(self, node):
try:
- referers, neighbors = self._nodes[node]
+ referers, targets = self._nodes[node]
except KeyError:
raise GraphLookupError, node
else:
- if neighbors is None:
+ if targets is None:
return 0
- elif isinstance(neighbors, self._nodeSetFactory):
- return len(neighbors)
+ elif isinstance(targets, self._nodeSetFactory):
+ return len(targets)
else:
return 1
@@ -365,7 +412,7 @@
self.edges = DirectedIdGraphEdges(self)
self.nodes = DirectedIdGraphNodes(self)
- def transitiveClosure(self):
+ def transitiveClosure(self, with_values=False):
raise NotImplementedError
class DirectedIdGraphEdges(IdNodeStore, DirectedGraphEdges):
@@ -451,10 +498,12 @@
yield None, None, value
def shortestPath(self, source, target, use_values=False):
+ source, target = pypesid(source), pypesid(target)
getObject = services.identity(self).getObject
- return [(getObject(src), getObject(tgt)) for src, tgt in
- super(DirectedIdGraphEdges, self).shortestPath(
- source, target, use_values)]
+ path = super(DirectedIdGraphEdges, self).shortestPath(
+ source, target, use_values)
+ if path is not None:
+ return [getObject(ident) for ident in path]
class DirectedIdGraphNodes(IdNodeStore, DirectedGraphNodes):
"""Directed id graph nodes accessor"""
@@ -534,3 +583,41 @@
raise IdentityError, node
id_set = super(DirectedIdGraphNodes, self).targets(ident, transitive)
return IdentitySet.fromIdSet(id_set, not transitive, self._p_jar)
+
+class PQueue:
+ """Simple priority queue using BTrees"""
+
+ def __init__(self):
+ self._keys = OOBTree()
+
+ def insert(self, key, value):
+ """Insert the key and value. All values in the queue must be
+ comparable. Note that inserting a key multiple times has
+ undefined results"""
+ k = self._keys.get(value)
+ if k is None:
+ self._keys[value] = [key]
+ else:
+ k.append(key)
+
+ def popMin(self):
+ """Return the key with the minimum value and remove it from the queue"""
+ minval = self._keys.minKey()
+ keys = self._keys[minval]
+ r = keys.pop()
+ if not keys:
+ del self._keys[minval]
+ return r
+
+ def popMax(self):
+ """Return the key with the maximum value and remove it from the queue"""
+ maxval = self._keys.maxKey()
+ keys = self._keys[maxval]
+ r = keys.pop()
+ if not keys:
+ del self._keys[maxval]
+ return r
+
+ def __nonzero__(self):
+ return bool(self._keys)
+
=== Packages/pypes/pypes/interfaces.py 1.1.1.1 => 1.2 ===
--- Packages/pypes/pypes/interfaces.py:1.1.1.1 Mon Aug 4 00:46:03 2003
+++ Packages/pypes/pypes/interfaces.py Fri Aug 8 00:57:49 2003
@@ -374,5 +374,8 @@
edges = Attribute('edges',
"""IGraphEdges object for manipulating the edges of the graph""")
- def transitiveClosure():
- """Return the transitive closure graph for the current graph."""
+ def transitiveClosure(with_values=False):
+ """Return the transitive closure graph for the current graph. If
+ with_values is true, then the values for each edge in the resulting
+ graph are computed from the exisiting values. This means that all
+ edge values in the graph must be addable"""
More information about the Zope-CVS
mailing list