[m-rev.] for review: make each SCC a set

Paul Bone paul at bone.id.au
Mon Feb 20 16:03:59 AEDT 2017

On Fri, Feb 17, 2017 at 01:22:02PM +1100, Zoltan Somogyi wrote:
> For review by anyone.
> I think digraph.m should have predicates that returns the list of SCCs
> in the graph in BOTH orders, not just one, and I think that the names
> of those predicates should say what the order they return is. The current
> atsort predicate can be a synonym for one of these.
> Names like return_bottom_up_sccs and return_top_down_sccs would work
> only if for each edge x->y, it were obvious which of x and y is higher.
> For our use case, this is clear, but for other use cases, it could be clear
> the other way around. Any ideas for better names? All I came up with
> are return_sccs_in_from_to_order and return_sccs_in_to_from_order,
> relying on the fact that it is pretty clear that x is "from" and y is "to",
> but those names are not exactly catchy.

I think these are the best names we can find, but I still have to remind
myself what they mean.  In other words I have to remind myself that parents
are drawn above children and/or that callers are parents, and callees are
children.  I think this is something I confuse myself about sometimes but
maybe others do as well.

But comments like this help:

    make_dependency_info(Graph) = dependency_info(Graph, BottomUpOrdering) :-
        % digraph.atsort puts the cliques of parents before the cliques
        % of their children. This is a top down order.
        digraph.atsort(Graph, TopDownOrdering),
        list.reverse(TopDownOrdering, BottomUpOrdering).

I suggest a little reminder in a comment on the declrations for these

Paul Bone

More information about the reviews mailing list