Page MenuHomePhabricator

[ADT] Update RPOT to work with specializations of different types.
ClosedPublic

Authored by fhahn on Apr 9 2021, 3:08 AM.

Details

Summary

At the moment, ReversePostOrderTraversal performs a post-order walk on
the entry node of the passed in graph, rather than the graph type
itself.

If GT::NodeRef is the same as GraphT, everything works as expected and
this is the case for the current uses in-tree. But it does not work as
expected if GraphT != GT::NodeRef. In that case, we either fail to build
(if there is no GraphTrait specialization for GT:NodeRef) or we pick the
GraphTrait specialization for GT::NodeRef, instead of the specialization
of GraphT.

Both the depth-first and post-order iterators pick the expected
specalization and this patch updates ReversePostOrderTraversal to
delegate to po_begin & po_end to pick the right specialization, rather
than forcing using GraphTraits<GT::NodeRef>, by first getting the entry
node.

This makes ReversePostOrderTraversal<Graph<6>> RPOT(G); build and
work as expected in the test.

The patch also updates a couple of functions that unnecessarily took the
input graph by value, when it was not needed. They can take the graph by
const-reference instead, which does not require GraphT to provide a copy
constructor. This technically is a separate change, but is required to
be able to use Graph<> from TestGraph in the test, because it does not
provide a copy constructor. If desired, I can split this out as a
separate change.

Diff Detail

Event Timeline

fhahn requested review of this revision.Apr 9 2021, 3:08 AM
fhahn created this revision.
Herald added a project: Restricted Project. · View Herald TranscriptApr 9 2021, 3:08 AM
dexonsmith accepted this revision.Apr 16 2021, 12:18 PM

Looks like a nice clean up; LGTM.

The patch also updates a couple of functions that unnecessarily took the
input graph by value, when it was not needed. They can take the graph by
const-reference instead, which does not require GraphT to provide a copy
constructor. This technically is a separate change, but is required to
be able to use Graph<> from TestGraph in the test, because it does not
provide a copy constructor. If desired, I can split this out as a
separate change.

My tendency would usually be an NFC prep commit as you suggest, but at the same time it's nice to land a coincident, motivating use case (which would be the Graph test). Either way seems fine.

This revision is now accepted and ready to land.Apr 16 2021, 12:18 PM
fhahn updated this revision to Diff 338306.Apr 17 2021, 7:22 AM

Thanks Duncan! I'll commit the changes const & changes to the post-order iterators separately.

fhahn updated this revision to Diff 338322.Apr 17 2021, 10:04 AM

Rebased after landing the post-order iterator fixes in bbf01f96b5ccc1dcb4d1d47cb55292c27c698dbb.

This revision was landed with ongoing or failed builds.Apr 17 2021, 12:49 PM
This revision was automatically updated to reflect the committed changes.