id	summary	reporter	owner	description	type	status	milestone	component	version	severity	resolution	keywords	cc
76	invalid result for File Dependency Examp	nobody	jsiek	"{{{
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)

}}}"	Bugs	closed		graph	None		Fixed