Opened 9 years ago

Last modified 9 years ago

#9368 new Patches

Generalize edge weight types usable in prim_minimum_spanning_tree

Reported by: lgtorres42@… Owned by: Jeremiah Willcock
Milestone: To Be Determined Component: graph
Version: Boost Development Trunk Severity: Problem
Keywords: bgl, prim, weight Cc:

Description

The current implementation of prim_minimum_spanning_tree makes the following assumptions about edge weight types:

+ weights have the less-than (<) operator defined

+ weight identity value is 0

+ the maximum weight value is accessible by std::numeric_limits<W>::max()

I've attached a patch that removes these requirements of edge weights by allowing users to use the distance_compare, distance_zero, and distance_inf named parameters. These parameters are passed to the dijsktra_shortest_paths() call that underlies the prim_minimum_spanning_tree function.

Attachments (1)

prim-patch.patch (2.4 KB ) - added by lgtorres42@… 9 years ago.
general edge weight patch to BGL prim's minimum spanning tree

Download all attachments as: .zip

Change History (2)

by lgtorres42@…, 9 years ago

Attachment: prim-patch.patch added

general edge weight patch to BGL prim's minimum spanning tree

comment:1 by lgtorres42@…, 9 years ago

Note: adding this patch would require updating the Prim's documentation to reflect the new functionality.

Note: See TracTickets for help on using tickets.