"""Some graph-theoretic stuff. See also graphviz (http://www.graphviz.org/ and man pages for: twopi, dotty, lefty, acyclic, lneato, nop, tred, gc, sccmap, unflatten, gvgpr, dot, neato, ccomps and gvcolorize) for visualisation of graphs. Things to play at: * .h file inclusion hierarchy; CPP sensitive ? * C function call hierarchy $Id: graph.py,v 1.4 2002/10/08 22:06:15 eddy Exp $ """ class Partition: """Base-class for partitions. Home for docs. A partition, P, of a set, S, is a set of disjoint sub-sets of S for which S is the union of all P's members. I'll refer to the members of P as `parts'; each part is a sub-set of S, each member of S is a member of exactly one part. I'll describe members of S as nodes; and the members of the part containing a given node as peers of that node. The present implementation works with S as range(n) for some integer n; the nodes are integers 0 to n-1. Where doc-strings in sub-classes of Partition describe a parameter as a node, an IndexError will be raised if its value is not in range(n). Internal datastructures use the node as an index into appropriate arrays of length n. Partitions support len(); a new node may be added by calling append(len()). It is presumed that the caller had some prior knowledge of len()'s value; the argument to append() is asserted to be len() when __debug__ is true. Each new node will be in a new part when created: thus initialisation of the nodes creates a `discrete' partition in which each node is a part and each part has only one node in it. [The presence of the empty set as one of the parts is formally allowed but invariably a nuisance: it is more practical to exclude empty.] A partition is modified by uniting two of its parts: this is expressed as joining two nodes, one from each part. A partition can be thought of as answering two primitive questions, * are these two nodes in the same part as one another ? * which nodes are peers of this one ? along with the inevitable `give a complete description of yourself'. The implementations of Find and Unite, below, answer the primitive questions and suffice, together, to provide a complete description. Each is optimised to answer one question and avoids answering the other: each presumes that the other will be consulted for the information it lacks. Thus Unite presumes that you won't ask it to join two nodes unless you know they are in different parts: it thereby saves itself the expensive (for it) job of checking this. """ def peers(self, node): """Returns a list of the nodes in the same connected component as the given node. """ raise NotImplementedError def join(self, node, vertex): """Joins the connected components of the given nodes. """ raise NotImplementedError def joined(self, node, *nodes): """Returns true iff all the given nodes are in one connected component. """ raise NotImplementedError class Unite (Partition): """Keeps track of the parts of a partition. Methods: peers(node) -- returns a list of peers of the given node. join(this, that) -- combines two *disjoint* parts. """ def __init__(self, size=0): """Initialise internal datastructures.""" self.__forward = range(size) self.__backward = range(size) # Chasing i->forward[i] leads round a loop; # likewise backward, traversing the same loop in reverse. # Each such loop is a connected component of self. # assert i == backward[forward[i]] for each 0 < i < len(self) def __len__(self): return len(self.__forward) # assert: equal to len(self.__backward) def peers(self, node): """Returns the component containing a given node. Result is a list of nodes in the given node's component. If it ever involves duplicates, something's gone wrong. Probably so wrong you won't see the answer ... """ # This should be implemented to yield an iterator ... f, n, row = self.__forward, node, [] while 1: row.append(n) n = f[n] assert self.__backward[n] == row[-1] if n is node: return row def append(self, ind): assert len(self.__forward) == ind == len(self.__backward), \ "Unite's append requires the right value" # new loop with one member: backward[i] == i == forward[i] self.__forward.append(ind) self.__backward.append(ind) def join(self, nod, ver): """Joins two *disjoint* components. Arguments are nodes, one from each component. The nodes must not be peers: this is *not* checked. They will be peers after join is called. """ f, b = self.__forward, self.__backward pod, wer = f[nod], f[ver] assert b[pod] is nod and b[wer] is ver # Do the swaps: b[pod], b[wer] = ver, nod f[nod], f[ver] = wer, pod class Find (Partition): """Keeps track of `in same part' truths for a partition. Handles predicates relating to a partition; also keeps track of the collection of parts, expressed as one member of each part. Methods: joined(node, ...) -- true if all given nodes are in one part join(this, that) -- ensures two nodes are joined disjoint() -- returns a list of nodes, one from each part peercount(node) -- size of given node's connected component """ def __init__(self, size=0): self.__up = range(size) self.__count = [ 1 ] * size # self.__up[i] is a member of the same connected component as i; i is # the representative member of the component iff i is self.__up[i], in # which case self.__count[i] is the size of the connected component. def __len__(self): return len(self.__up) # assert: always equal to len(self.__count) def __chase(self, node): """Returns the representative member of node's connected component. Single argument is a node (index): returns the node reached from this by chasing i->self.__up[i] to a fixed point. Side-effect: changes the __up[] of all nodes it visits on the way to point at the answer returned, so as to speed this chase next time around. """ trail = [] while 1: n = self.__up[node] if n is node: break trail.append(node) node = n # self.__up[node] is node, as is self.__up[trail[-1]] if len(trail) > 0. # All but the last item in trail need to point __up at node: for n in trail[:-1]: self.__up[n] = node return node def peercount(self, node): return self.__count[self.__chase(node)] def joined(self, node, *nodes): """Do the edges seen thus far connect (all) the given nodes ? Arguments are node indices; at least one must be given. Result is true precisely if all nodes are in the same connected component of the graph of edges thus far passed to self.join(). """ nod = self.__chase(node) for vertex in nodes: if self.__chase(vertex) != nod: return None # i.e. No. return 1>0 # i.e. Yes def append(self, ind): assert len(self.__count) == ind == len(self.__up), \ "Find's append requires the right value" # Lazily grow the lists: node is initially alone. self.__up.append(ind) # so self.__up[ind] is ind. # New node's sub-tree contains only one node: itself. self.__count.append(1) # and self.__count[ind] is 1. def join(self, node, vertex): """Joins two nodes. Returns None if nodes were already joined: else, a true value. Consequently its return is what `not self.joined()' would have yielded previously. """ nod, ver = self.__chase(node), self.__chase(vertex) if nod is ver: return # nothing to do # Who has the bigger sub-tree ? count = self.__count n, v = count[nod], count[ver] if n < v: nod, ver = ver, nod # swap # Hang smaller tree below bigger: self.__up[ver], count[nod] = nod, n + v return 1>0 # did something def disjoint(self): """Returns a list containing one sample member from each connected component. """ # the sample members being the fixed-points of __up return filter(lambda x, _u=self.__up: x is _u[x], range(len(self.__up))) class FindUnite (Find, Unite): """An implementation of the find-unite algorithm. Provides for arbitrary graph-partitioning, provided the nodes of the graph are labelled with an initial sub-sequence of the natural numbers, i.e. 0, 1, ..., n for some natural n, with no omissions. Graph, below, provides such a packaging for a graph with arbitrary python objects as nodes. Create an instance of FindUnite(); for each edge in a graph, identify the two ends and invoke the instance's .join(thisend, thatend). At any stage, invoke .peers(node) to get a list of all nodes in the given one's connected component. """ def __init__(self, size=0): """Initialises an empty FindUnite.""" Find.__init__(self, size) Unite.__init__(self, size) def append(self, ind): Find.append(self, ind) Unite.append(self, ind) def join(self, node, vertex): """Joins a given pair of nodes. Takes two arguments: the end-nodes of an edge in your graph. Joins their connected components, if disjoint, together. Nodes not previously known to self are added, initially connected to nothing; they are then joined as for familiar nodes. """ # Unite doesn't want to join things if they're already joined. # Find knows whether they're already joined: if Find.join(self, node, vertex): # Find did something: get Unite in on the act. Unite.join(self, node, vertex) def partition(self): """Returns a list of disjoint lists describing the partition. Each entry in the list returned is a list of nodes representing a connected component of the graph described by the FindUnite object. """ return map(self.peers, self.disjoint()) class Graph: """Represents a network of nodes joined by edges. Creation: Graph([node, ...]) -- creates a new graph with, optionally, the given objects as (initially) unconnected nodes. Command: join(this, that) -- adds an edge from this to that, optionally adding each as a node in the process. None of the following modifies the graph: whereas join() will add any unfamiliar arguments as nodes of the graph, the queries (below) will interprete any unrecognised node as being outside the graph and connected to nothing but itself - but will promptly forget they ever heard of the given node. Attributes: nodes -- a tuple containing all known nodes. edges -- a tuple containing all known edges, each of which is represented by a 2-tuple of nodes. partition -- a list of connected components of self. Each connected component is represented as a list (whose order is arbitrary) of nodes; each such list is equal, subject to shuffling order, to the .peers(n) of each node, n, in the list. Each node of the graph appears in exactly one of the connected components. Queries: peers(node) -- returns a list of all nodes in the same connected component as the given node (order is arbitrary). peercount(node) -- returns the value len(peers(node)) would produce: the number of nodes in the connected component in which the given node appears. joined(node, ...) -- tests whether given nodes are all in one connected component. span(node, ...) -- returns a Graph consisting of all nodes and arcs in the same connected component as at least one of the given nodes. chop(node, ...) -- returns a Graph consisting of the given nodes and any edges directly connecting these nodes. Note that .span() provides a sub-graph `grown outwards from' its given nodes, while .chop() provides a sub-graph `stripped down to only' the given nodes. """ # Creation: def __init__(self, *nodes): self.__edges, self.__nodes, self.__connect = [], list(nodes), FindUnite(len(nodes)) # Attributes: def __getattr__(self, key): # Read-only copies: if key == 'nodes': return tuple(self.__nodes) if key == 'edges': return tuple(self.__edges) if key == 'partition': return map(self.__peers, self.__connect.disjoint()) raise AttributeError, key # Command: .join() with support from .__node() def __node(self, node): """Returns internal index of node, adding node to graph if needed. If node has been met before, an index has been recorded for it: this is returned. Otherwise, the node is added to internal datastructures with a previously-unused index, which is returned. For internal use only. """ # Could be more efficient using an inverse-lookup here. try: return self.__nodes.index(node) except ValueError: pass ind = len(self.__nodes) self.__nodes.append(node) self.__connect.append(ind) return ind def join(self, start, stop): """Connects two nodes in the present graph, adding the nodes if necessary. """ self.__edges.append((start, stop)) self.__connect.join(self.__node(start), self.__node(stop)) # Queries: joined(), peers() and sub-Graph()s. def joined(self, *nodes): # requires at least one node, in fact if len(nodes) < 1: raise ValueError('no nodes provided: how can I check whether they are joined ?') if len(nodes) < 2: return 1 # every node is implicitly connected to itself try: indices = map(self.__nodes.index, nodes) except ValueError: return None return apply(self.__connect.joined, indices) def peercount(self, node): try: nod = self.__nodes.index(node) except ValueError: return 1 return self.__connect.peercount(nod) def __peers(self, nod): return map(lambda i, _r=self.__nodes: _r[i], self.__connect.peers(nod)) def peers(self, node): try: nod = self.__nodes.index(node) except ValueError: return [ node ] return self.__peers(nod) # sub-Graph()s: span(), chop() def span(self, *nodes): """Returns a full sub-graph containing the given nodes. """ # collect the union of the connected components of the given nodes: all = [] for node in nodes: if node not in all: all = all + self.peers(node) # build a graph out of them: ans = apply(Graph, tuple(all)) for a, b in self.__edges: assert (a in all) == (b in all), 'I thought we had a partition here !' if a in all: ans.join(a, b) # return that graph: return ans def chop(self, *nodes): """Returns a restriction sub-graph containing only the given nodes. Includes each edge of self whose ends are both in the restriction. In particular, doesn't include linkage via nodes omitted (see .span() for that). """ # build a graph using only the given nodes: ans = apply(Graph, nodes) for a, b in self.__edges: if a in nodes and b in nodes: ans.join(a, b) # return that graph: return ans """ $Log: graph.py,v $ Revision 1.4 2002/10/08 22:06:15 eddy Major over-haul, largely for docs. Added ADT baseclass Partition. Made initialisers take an initial size. New peercount(node) method. Changed Graph more drastically; nodes, edges and partition are now attributes, not methods; renamed sub -> span, added peercount, chop. Revision 1.3 2000/02/19 15:37:11 eddy Carved everything up better. Revision 1.2 2000/02/19 13:37:30 eddy Moved all node/index translations to Graph so FindUnite's node values are all indices into lists. Now to carve up FindUnite. Initial Revision 1.1 2000/02/19 12:18:45 eddy """