"Florian G. Pflug" <[EMAIL PROTECTED]> writes: > Christopher Browne wrote: >> Christopher Browne wrote >> >>>I whiteboarded a couple of attempts at algorithms for this, this >>>afternoon. It needs a bit more thought, I think, to come up with >>>something final... > >> Here's what I have at this point... >> The notion that seems to make sense, here, is to construct all of the >> possible maximum-length paths from each origin. Note that this is a >> loose mix of C-like and pl/pgsql-like code; I'm not yet expecting it to >> be exactly right... > <snipped algorithm> > >> That gives us a list of all the longest possible traversals. > Hm.. I don't really understand that algorithm (But, then, maybe > if've just been up for too long now.. ;-) ). Where is that > quantity-value coming from, and what does it do?
The quantity is counting whether, for a given traversal, we have found: 0 extensions to it (e.g. - we're at the end of the road) 1 extension to it (e.g. - lengthen it by one) more than one extension to it (which means we have found a fork in the road). > In the meantime I've coded up something myself. My first attempt was > to generate all traversals (not just the ones with maximum length), > and store them in a table (I used an array-valued field instead of a > second table vpath, but thats just a detail). This seems to work, > basically, but performance was horrible (For a fully-meshed graph > with 10 nodes, it would need to generate 10! (10 faktorial = > 10*9*...*1) entries... :-( I try to extend them as much as possible, so that means you need rather fewer of them. > Therefore, I came up with another idea. Here it is, in pseudocode. > foreach node as x > foreach possible provider of x as y > Temporarily remove x from the graph > zs <- All nodes that are somehow connected to y, via one or more nodes > foreach node in zs as z > If x subscribes a set from z with provider != z > do nothing > else > Add (receiver=x, provider=y, origin=z) to sl_listen. > > The idea is that, if I want to figure out if a node x can use > a neighbour y as a provider for events from some node z, I have > to check if y can receive events from z assuming the node x doesn't even > exists. If it can, than y is used as a provider, otherwise it is not. > > Attachted is a sql-script that creates a few tables, creates two functions > that implement this algorithm in plpgsql. Below the functions there a few > testcases. It uses it's own tables, with different names than slony for now, > because this made the development and testing easier. > > create_listen contains the 3 nested for-loops, while the set-valued function > reachable_from(starting_node, nodes_to_ignore) check with nodes are reachable > from the starting_node when the nodes in nodes_to_ignore are, well, ignored > ;-) > > I used the columns src, dst and via instead of origin, receiver and provider ( > Or src and dst instead of server and client in the case if sl_path). > > Does anyone see a case where this would fail? If not, I'll try to > fit this into slony, and see if it workes for my case. I'll have to think about that tomorrow. -- let name="cbbrowne" and tld="ca.afilias.info" in String.concat "@" [name;tld];; <http://dba2.int.libertyrms.com/> Christopher Browne (416) 673-4124 (land) _______________________________________________ Slony1-general mailing list [email protected] http://gborg.postgresql.org/mailman/listinfo/slony1-general
