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)
Note:
See TracTickets
for help on using tickets.