[Zope-CVS] CVS: Packages/pypes/pypes - graph.py:1.6
interfaces.py:1.5
Casey Duncan
casey at zope.com
Mon Aug 18 01:36:32 EDT 2003
Update of /cvs-repository/Packages/pypes/pypes
In directory cvs.zope.org:/tmp/cvs-serv707
Modified Files:
graph.py interfaces.py
Log Message:
Move shortestPath and allPaths methods from graph.edges to graph
Change interface to reflect that paths are lists of nodes, not edges
Implement graph.allPaths method and test
Add identity tests for DirectedIdGraph test suite
=== Packages/pypes/pypes/graph.py 1.5 => 1.6 ===
--- Packages/pypes/pypes/graph.py:1.5 Sun Aug 10 22:32:15 2003
+++ Packages/pypes/pypes/graph.py Mon Aug 18 00:35:57 2003
@@ -37,6 +37,15 @@
_nodesMapFactory = OOBTree
_nodeSetFactory = OOTreeSet
+
+class cycle(list):
+ """Traversal path of the graph that indicates a cycle. The last item
+ of the path is the element where the cycle occurred. It appears twice
+ in the path.
+ """
+ def __repr__(self):
+ return 'cycle(%s)' % repr(list(self))
+
class DirectedGraph(Persistent):
"""Directed graph for arbitrary object nodes. All nodes must be totally
@@ -49,11 +58,190 @@
def __init__(self):
self.edges = DirectedGraphEdges()
self.nodes = DirectedGraphNodes(self.edges)
+
+
+ def shortestPath(self, source, target, use_values=False):
+ if source not in self.nodes._nodes:
+ raise GraphLookupError, source
+ if target not in self.nodes._nodes:
+ 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
+ """
+ edgemap = self.edges._nodes
+ seen = {}
+ nodes = [source]
+ path = []
+ while nodes:
+ node = nodes.pop()
+ if seen.has_key(node):
+ continue
+ referers, targets = edgemap[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.nodes._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 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
+ """
+ edgemap = self.edges._nodes
+ nodes = PQueue()
+ nodes.insert(source, None)
+ pred = {}
+ while nodes:
+ n, nd = nodes.popMin()
+ referers, targets = edgemap[n]
+ if targets is not None:
+ if not isinstance(targets, self.nodes._nodeSetFactory):
+ targets = (targets,)
+ for t in targets:
+ td = self.edges._edge_values[n, t]
+ if nd is not None:
+ td += nd
+ if t in pred and td >= pred[t][1]:
+ continue
+ nodes.insert(t, td)
+ pred[t] = n, td
+ if target in pred:
+ path = []
+ while target is not source:
+ path.append(target)
+ target, nil = pred[target]
+ path.append(source)
+ path.reverse()
+ return path
+
+ def allPaths(self, source=None, target=None):
+ """Generates an iterator of paths between graph nodes. Paths are
+ either a list of nodes or a cycle object (a list derivative) that
+ signals a cyclic path.
+ """
+ edgemap = self.edges._nodes
+ if source is not None:
+ if source not in self.nodes._nodes:
+ raise GraphLookupError, source
+ start_node = source
+ end_node = target
+ start_nodes = (source,)
+ direction = 1
+ else:
+ start_node = target
+ end_node = source
+ if target is None:
+ direction = 1
+ start_nodes = edgemap.keys()
+ else:
+ direction = 0
+ start_nodes = (target,)
+ if target is not None:
+ if target not in edgemap:
+ raise GraphLookupError, target
+ if edgemap[target][0] is None:
+ # Optimization: target has no edges pointing to it
+ # ergo, there are no paths to the target
+ start_nodes = ()
+ nulliter = iter(())
+ pathtype = list
+ for n in start_nodes:
+ if n is end_node:
+ continue
+ targetiters = []
+ path = [n]
+ node = n
+ while node is not None:
+ targets = edgemap[node][direction]
+ if targets is not None:
+ if isinstance(targets, self.nodes._nodeSetFactory):
+ if targets:
+ ti = iter(targets)
+ targetiters.append(ti)
+ node = ti.next()
+ if node in path:
+ if pathtype is not cycle:
+ pathtype = cycle
+ else:
+ node = None # avoid double cycle
+ path.append(node)
+ else:
+ targets = None
+ else:
+ node = targets
+ targetiters.append(nulliter)
+ if node in path:
+ if pathtype is not cycle:
+ pathtype = cycle
+ else:
+ node = None # avoid double cycle
+ path.append(node)
+ while True:
+ if targets is None:
+ # leaf node or cycle
+ while targetiters:
+ try:
+ # try to get a sibling
+ node = targetiters[-1].next()
+ except StopIteration:
+ # no more siblings, go to the parent
+ targetiters.pop()
+ path.pop()
+ node = None
+ else:
+ if node in path:
+ if pathtype is not cycle:
+ pathtype = cycle
+ else:
+ node = None # avoid double cycle
+ path[-1] = node
+ break
+ else:
+ # path fully explored
+ node = None
+ break
+ # NOTE: identification of end_node is done by comparison
+ # the common case is integers here, so that's not an issue
+ # and an identity test will not work. since BTree key
+ # identity is also comparison based we should be safe
+ if node is not None and (end_node is None
+ or end_node == node):
+ p = pathtype(path)
+ if not direction:
+ p.reverse()
+ yield p
+ if pathtype is cycle:
+ # cycle detected, stop traversal here
+ targets = None
+ pathtype = list
+ else:
+ break
def transitiveClosure(self, with_values=False):
raise NotImplementedError
-
-
+
class DirectedGraphEdges(ObjectNodeStore, Persistent):
"""Directed graph edges accessor"""
@@ -216,80 +404,6 @@
def iterItems(self):
return iter(self._edge_values.items())
-
- 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 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
- """
- nodes = PQueue()
- nodes.insert(source, None)
- pred = {}
- while nodes:
- n, nd = nodes.popMin()
- referers, targets = self._nodes[n]
- if targets is not None:
- if not isinstance(targets, self._nodeSetFactory):
- targets = (targets,)
- for t in targets:
- td = self._edge_values[n, t]
- if nd is not None:
- td += nd
- if t in pred and td >= pred[t][1]:
- continue
- nodes.insert(t, td)
- pred[t] = n, td
- if target in pred:
- path = []
- while target is not source:
- path.append(target)
- target, nil = pred[target]
- path.append(source)
- path.reverse()
- return path
class DirectedGraphNodes(ObjectNodeStore, Persistent):
"""Directed graph nodes accessor"""
@@ -471,6 +585,36 @@
self.edges = DirectedIdGraphEdges(self)
self.nodes = DirectedIdGraphNodes(self)
+ def shortestPath(self, source, target, use_values=False):
+ source, target = pypesid(source), pypesid(target)
+ if source is None:
+ raise IdentityError, source
+ if target is None:
+ raise IdentityError, target
+ getObject = services.identity(self.edges).getObject
+ path = super(DirectedIdGraph, self).shortestPath(
+ source, target, use_values)
+ if path is not None:
+ return [getObject(ident) for ident in path]
+
+ def allPaths(self, source=None, target=None):
+ if source is not None:
+ source = pypesid(source)
+ if source is None:
+ raise IdentityError, source
+ if target is not None:
+ target = pypesid(target)
+ if target is None:
+ raise IdentityError, target
+ # XXX This should be lazified
+ getObject = services.identity(self.edges).getObject
+ for path in super(DirectedIdGraph, self).allPaths(source, target):
+ idpath = [getObject(ident) for ident in path]
+ if isinstance(path, cycle):
+ yield cycle(idpath)
+ else:
+ yield idpath
+
def transitiveClosure(self, with_values=False):
raise NotImplementedError
@@ -555,14 +699,6 @@
identity.getObject(tgt_ident)), value
except IdentityKeyError:
yield None, None, value
-
- def shortestPath(self, source, target, use_values=False):
- source, target = pypesid(source), pypesid(target)
- getObject = services.identity(self).getObject
- 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"""
=== Packages/pypes/pypes/interfaces.py 1.4 => 1.5 ===
--- Packages/pypes/pypes/interfaces.py:1.4 Mon Aug 11 22:35:05 2003
+++ Packages/pypes/pypes/interfaces.py Mon Aug 18 00:35:57 2003
@@ -360,23 +360,8 @@
def iterItems():
"""Return an iterator of ((source, target), value) pairs for each
edge with a value in the graph.
- """
-
- def shortestPath(source, target, use_values=False):
- """Return the sequence of node pairs which represent the edges of the
- shortest path between the nodes. For instance, If source and target are
- adjacent, return [(source, target)]; if they connect through a single
- intermediary return [(source, other), (other, target)], etc.
-
- If use_values is true, then the edge data is used to calculate the
- distance between nodes. This implies that all data objects in the graph
- can be added and compared to one another as distances. By default, the
- values are not used and the distance between adjacent nodes is assumed
- to be 1.
"""
-# def paths()
-
class IGraph(Interface):
"""Persistent graph of object nodes"""
@@ -390,4 +375,28 @@
"""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"""
+ edge values in the graph must be addable
+ """
+
+ def shortestPath(source, target, use_values=False):
+ """Return the sequence of node which is the shortest path from source
+ to target. For instance, If source and target are
+ adjacent, return [source, target]; if they connect through a single
+ intermediary return [source, intermediate, target], etc. If no
+ path connects source and target, return None.
+
+ If use_values is true, then the edge data is used to calculate the
+ distance between nodes. This implies that all data objects in the graph
+ can be added and compared to one another as distances. By default, the
+ values are not used and the distance between adjacent nodes is assumed
+ to be 1.
+ """
+
+ def allPaths(source=None, target=None):
+ """Return an iterator of sequences of nodes representing all possible
+ paths between nodes of the graph. If source and target are omitted,
+ all possible paths between all graph nodes are returned. If source
+ is specified, only paths starting from source are returned. If
+ target is specified, only paths to target are returned. If both are
+ specifed to compute all paths connecting source to target
+ """
\ No newline at end of file
More information about the Zope-CVS
mailing list