search

joedski / dag-progress

Calculate user progress for each vertex in an acyclic digraph
1 stars 0 forks source link

Graphs ending with several progress:false vertices which form a merging structure return incorrect progress results #2

Closed joedski closed 8 years ago

joedski commented 8 years ago

A simple demonstrative case, as drawn up in Mermaid:

graph TD;
PreStart --> Start
Start --> Branch
Branch --> A
Branch --> B
A --> AtoEnd
AtoEnd --> End
B --> End

With these vertex options:

'Branch': { progress: false }
'A': { progress: false }
'B': { progress: false }
'AtoEnd': { progress: false }
'End': { progress: false }

Expected Result

PreStart will have a value of 0.5 and Start will have a value of 1, as will the rest of the vertices after Start.

Actual Result

Start has a value less than 1, as does A.

joedski commented 8 years ago

The fix for this required rewriting pathLengths to work with the reversed adjacency list, kind of like how the number-of-paths algorithm works. Kind of. Also started from 0 so that I don't have to fiddle around with subtracting the vertex's own progress.