Modify

Opened 7 years ago

Closed 7 years ago

Last modified 7 years ago

#4737 closed Bugs (fixed)

Documentation for Prim MST concerning distance_map is wrong

Reported by: nicoe@… Owned by: asutton
Milestone: To Be Determined Component: graph
Version: Boost 1.44.0 Severity: Problem
Keywords: Cc:

Description

In the documentation for prim_minimum_spanning_tree, you can read at distance_map:

The shortest path weight from the source vertex s to each vertex in the graph g is recorded in this property map. The shortest path weight is the sum of the edge weights along the shortest path.

I would say this is wrong. I claim that the prim_minimum_spanning_tree stores original edgeweights in the distance map. Precisely, an entry i in the distance map corresponds to the edgeweight of the edge from vertex i to its predecessor in the MST.

Example: Given a undirected graph on the vertex set {0,1,2} with edges (0,1,2), (0,2,3), (1,2,4) (to be read as vertex, vertex, weight). The output of prim MST called with parameters root_vertex(1) concerning the distance map is (2,0,3). According to the documentation it schould be (2,0,5).

See attached example for details

Attachments (1)

Example.cpp (1.2 KB) - added by nicoe@… 7 years ago.

Download all attachments as: .zip

Change History (3)

Changed 7 years ago by nicoe@…

comment:1 Changed 7 years ago by jewillco

  • Resolution set to fixed
  • Status changed from new to closed

(In [65963]) Fixed documentation of distance map; fixes #4737

comment:2 Changed 7 years ago by jewillco

(In [66093]) Merged changes r65193, r65939, r65963, and r65964 from trunk; refs #4731, #4737

Add Comment

Modify Ticket

Change Properties
Set your email in Preferences
Action
as closed The owner will remain asutton.
The resolution will be deleted. Next status will be 'reopened'.
Author


E-mail address and user name can be saved in the Preferences.

 
Note: See TracTickets for help on using tickets.