Re: [Monotone-devel] pretty pretty pictures (for some value of pretty)

[Nathaniel Smith]

On Wed, Sep 13, 2006 at 08:23:02PM -0700, Nathaniel Smith wrote:
> An interesting problem is how to reduce the revision graph when that's
> needed.  Restricted log, for instance, would have some trouble
> showing a graph.  Same for --no-merges, and even forward log (because
> the graph drawer currently assumes that every node has at most 2
> successors; though I have some idea how to fix that).  It would also
> be very useful to have some sort of "stay on branch" mode, that elided
> or compressed any revisions that are off the branch.  (In particular,
> this would help a lot with some of the really wide bits in that graph
> of nvm.)  monotone-viz actually has logic to do this sort of graph
> reduction; we should look at that.

Oh, duh -- of course I know how to reduce the graph sensibly, it's
unique-*-merge :-).

Start from the set of nodes you want to include, e.g., the set of
nodes in a branch.  We want to reduce the graph so it includes these
nodes, but we want leave in strategic merge nodes that show different
chunks of graph came together and lead into each other.

Treat the starting set like they're marks.  At each merge node, find
the nearest included ancestor on each side -- if they're different,
include the merge node too (i.e., mark it).

This can be done in a single forward pass over the graph.

Can something analogous be done iteratively backwards, for normal log?
Perhaps simply reverse the graph, and say "if any incoming edges
disagree on the mark, then mark this node"?  (The difference between
a forward and backward graph is that in a forward graph, the highest
in-degree is 2, while in a backwards graph it can be arbitrarily
large -- because a rev can have at most 2 parents, but arbitrarily
many children.)  I wonder how the final sets generated by a forward
pass would differ from the ones generated by a backwards pass...

-- Nathaniel

-- 
"But in Middle-earth, the distinct accusative case disappeared from
the speech of the Noldor (such things happen when you are busy
fighting Orcs, Balrogs, and Dragons)."