Ticket #3992 (closed enhancement: fixed)

Opened 7 years ago

Last modified 3 years ago

property_maps, references, and copy construction

Reported by: jberry Owned by: gemacke
Priority: normal Milestone: 1.2
Version: 1.0 Severity: normal
Keywords: property_maps copy construction Cc:

Description (last modified by gemacke) (diff)

We need to be able to pass property_maps (e.g. edge_property_map<graph,T>) to algorithms. We also don't want to pass these by value because of the O(V+E) copying time. Plus, the current default implementations of vertex and edge property maps don't have copy constructors and hence fail in unfriendly ways when they are mistakenly passed by value (I've added a private copy constructor in my sandbox to give me a compiler error instead). However, it is currently not possible to pass a property map by reference to (for example) the shiloach_vishkin() algorithm, which optionally takes an edge filter (most conveniently - a property map). The default argument if the user doesn't pass a filter is a temporary object, which can't be used to initialize a reference. This example might not be completely compelling since we're going to change filtering strategy, but this general situation does seem like a problem. One solution might be to reference count the embedded data structure (array_property_map or map_property_map), but then the user would have to do this when making custom property maps for new graph structures. Another solution could be partial specialization of the algorithm class, but this doesn't seem very nice either. I don't know the "right" thing to do.

Change History

comment:1 Changed 7 years ago by gemacke

  • component Eldorado deleted

comment:2 Changed 7 years ago by gemacke

  • Owner changed from eldorado-graph@… to gemacke
  • Status changed from new to accepted

comment:3 Changed 7 years ago by gemacke

  • Type changed from defect to enhancement

comment:4 Changed 7 years ago by gemacke

This might be partially addressed because you can now use the noalias pragma on references. This allows you to pass a property map and noalias it to get basically the same performance as an array.

comment:5 Changed 6 years ago by gemacke

  • Version set to 1.1
  • Milestone set to 1.0

comment:6 Changed 6 years ago by gemacke

  • Version changed from 1.1 to 1.0
  • Milestone changed from 1.0 to 1.1

comment:7 Changed 6 years ago by gemacke

  • Milestone changed from 1.1 to 1.2

comment:8 Changed 3 years ago by gemacke

  • Status changed from accepted to closed
  • Resolution set to fixed
  • Description modified (diff)

This was addressed for shiloach_vishkin() in r3492. There are two different functions: one that takes a property map and one that doesn't. Both of them do initialization stuff and then call a separate function that actually performs the Shiloach Vishkin algorithm. The function that doesn't take a property map declares an object that defaults to using all the edges. The shiloach_vishkin() code serves as an example for how to do this for other algorithms.

Note: See TracTickets for help on using tickets.