Opened 20 years ago

Closed 16 years ago

#76 closed Bugs (Fixed)

invalid result for File Dependency Examp

Reported by: nobody Owned by: jsiek
Milestone: Component: graph
Version: None Severity:
Keywords: Cc:

Description

Using shortest paths algorithm with greater_than 
comparison instead of less_than will not compute the 
expected result (for parallel compilation earliest 
time)

Example:
Vertex1: A
Vertex2: B
Vertex3: C
Vertex4: D
Vertex5: E

Edge1: Vertex1 -> Vertex2
Edge2: Vertex2 -> Vertex3
Edge3: Vertex3 -> Vertex4
Edge4: Vertex1 -> Vertex4
Edge5: Vertex4 -> Vertex5

Weight[ Edge1 ] = 1
Weight[ Edge2 ] = 2
Weight[ Edge3 ] = 2
Weight[ Edge4 ] = 2
Weight[ Edge5 ] = 1

We start with Vertex1. Because Weight[ Edge4 ] is 
greater than Weight[ Edge1 ], Vertex4 will be visited 
next, then Vertex5, Vertex2, and finally Vertex3.

The times computed are:
Time[ Vertex1 ] = 0
Time[ Vertex2 ] = 1
Time[ Vertex3 ] = 3
Time[ Vertex4 ] = 5
Time[ Vertex5 ] = 3  <----

Vertex5 has the wrong time (should have been 6)!. It 
kept the time of the first traversal path which was [ 
Vertex1, Vertex4, Vertex5 ]. The second path [ 
Vertex1, Vertex2, Vertex3, Vertex4, Vertex5 ] never 
got a chance to update Vertex5's time (stopped at 
Vertex4 since it was already black)

Change History (1)

comment:1 by Douglas Gregor, 16 years ago

Status: assignedclosed
Logged In: YES 
user_id=249098
Originator: NO

I've fixed the example for Boost 1.34.0.
Note: See TracTickets for help on using tickets.