pseudoPython

Duncan Smith buzzard at urubu.freeserve.co.uk
Thu Mar 27 04:01:17 CET 2003


"Gareth McCaughan" <Gareth.McCaughan at pobox.com> wrote in message
news:slrnb84j5d.1efb.Gareth.McCaughan at g.local...
> Duncan Smith wrote:
>
> >                          I seem to have forgotten to post my last
function.
> > Just wondering whether a non-Pythonista would be able to follow this as
> > 'tis, or whether I should be popping and pushing the cliques (pointers
to
> > cliques) to a stack, or something.
> ..
> > graphThin(DJT):
> >
> > cliques = a list of cliques in elimination order
> >
> > while cliques:
> >     nextClique = cliques[-1]
> >     cliques = clique[:-1]
> >     cliques = cliques + cliqueThin(nextClique)
> >
> >
> > or maybe,
> >
> >
> > graphThin(DJT):
> >
> > cliques = a list of cliques in elimination order
> >
> > while cliques:
> >     nextClique = cliques.pop()
> >     for newClique in cliqueThin(nextClique):
> >         cliques.append(newClique)
>
> graphThin(DJT):
>
>     cliques = a list of cliques in elimination order
>
>     while cliques is not empty:
>         nextClique = last element of cliques
>         delete last element of cliques
>         for newClique in cliqueThin(nextClique):
>             append newClique to cliques
>
> is surely clearer. Instead of "while cliques is not
> empty", you could use a phrasing you used before:
> "while there are cliques". I don't like it much,
> though :-).
>

Yes, 'is not empty' is better.

> I think it's worth indenting the body of each function
> as well as the structures within the functions, as I've
> done here.
>

Yes, I'll see what I can do with that.  I'm limited to 3.25 inch columns.
But I can reduce the indent.

> Returning briefly to the original pseudocode, I think
> it's a mistake to use "\" to denote both set-theoretic
> difference and line continuation. I suggest "..." for
> the "continued on next line" meaning.

Good point.

And you probably
> want to replace "cliques.append(Cv)" with "append Cv to
> cliques", not that it matters much. I'm also puzzled
> by the inner loop in cliqueThin, which goes like this:
>
>     for each edge in thinnableEdges:
>         if edge is incident to v:
>             remove edge \
>             from thinnableEdges
>         elif edge is in Cv:
>             remove edge \
>             from thinnableEdges
>
> Why not
>
>     for each edge in thinnableEdges:
>         if edge is incident to v, or in Cv:
>             remove edge from thinnableEdges
>
> instead?

Yes, I'm still thinking about that.  It's that the "if" removes an edge from
a graph and the "elif" makes it non-removable (at least from the current
clique).  In any case, I need to add a couple of comments.

Er, and is mutating thinnableEdges meant
> to have a lasting effect? I mean, does "remove edge
> from thinnableEdges" actually alter the structure
> of the graph? If not, then this whole loop could
> be deleted :-).

Its actually 'permCluster(clique)' that removes edges from the graph
(indirectly, by locally changing a cluster tree).  Iterating over
thinnableEdges is just to remove those that have been removed from the
graph, and those that are no longer removable (because of the new structure
of the cluster tree).

If it does, then it might be worth
> flagging the fact more explicitly when you say
> "thinnableEdges = thinEdges(clique)". Anyway, I'm
> now quibbling about style, which is pretty stupid
> since I haven't read the accompanying text that may
> make sense of everything that's puzzling me :-),
> so I'll stop.
>

Not in its present state :-).  But by the third draft it might be easier to
follow.  I haven't even thought about the complexity analysis yet.  Cheers.

Duncan







More information about the Python-list mailing list