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

Zoltan Somogyi zoltan.somogyi at runbox.com
Mon Feb 20 16:10:11 AEDT 2017



On Mon, 20 Feb 2017 16:03:59 +1100, Paul Bone <paul at bone.id.au> wrote:
> > 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,

Which "these" are you referring to? The top_down/bottom_up pair,
or the from_to_order/to_from_order pair?

> 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. 

Edges in digraphs can be used to represent many relationships other than
parent/child relationships, and those relationships don't necessarily have
anything to do with up vs down, which is why I don't see the top_down/bottom_up
names as being a good choice.

> 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).

Thanks.

> I suggest a little reminder in a comment on the declrations for these
> functions/predicates.

This diff already added some.

Zoltan.




More information about the reviews mailing list