[m-rev.] for review: make each SCC a set
jfischer at opturion.com
Mon Feb 20 10:11:08 AEDT 2017
On Fri, 17 Feb 2017, Zoltan Somogyi wrote:
> 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 can't think of anything catchier myself.
> Make each SCC in the dependency graph a set, not a list.
> This is to make the data type follow the inherent semantics of SCCs
> more closely, and enforce the invariant that a procedure can appear
> in the SCC only once.
> Also, rename the list of SCCs from "dependency_ordering", which does
> not give a clue about *which way* the SCCs are ordered, to "bottom_up_sccs",
> which does.
The diff looks fine.
More information about the reviews