| 3 | | Handling of the `last` field of `Arc` still seems to be problematic. According to the usage of its value (lines 87, 110, 114), `e.last` should always be equal to `node_first_out[e.source+1]`, unless `e.id==-1`. However, some assignments do not correspond to this invariant. The change in iteration order of `OutArcIt` seems to be inconsistently updated (see lines 89, 98, 138, 216). |
| | 3 | Handling of the `last` field of `Arc` still seems to be problematic. According to the usage of its value (lines 87, 110, 114), `e.last` should always be equal to `node_first_out[e.source+1]`, unless `e.id==-1`. However, some assignments do not correspond to this invariant. The change in iteration order of `OutArcIt` seems to be inconsistently updated, see lines 89, 98, 138, 216). Please review these parts of the code. |
| 5 | | Anyway, this field is not necessary at all, recalculating its value would always be feasible. |
| 6 | | |
| 7 | | My suggestion is: |
| 8 | | 1. Entirely remove this field from `Arc` and calculate its value in `firstOut()` and `nextOut()`. |
| 9 | | 2. Compare the performance of this implementation and the previous one for various graphs (small/large, sparse/dense). `OutArcIt` might become slower, but `ArcIt` should be faster, because assignments of `last` and additional if statements would be saved there. |
| 10 | | 3. If `OutArcIt` becomes significantly slower, then we can re-introduce the `last` field, even as an optional field (or "cache") which is used only in `firstOut()` and `nextOut()`. |
| | 5 | Anyway, this field is not necessary, recalculating its value would always be feasible. However, it would make out arc iteration slower. It would be interesting to compare the performance of an alternative implementation that does not store this field (on various graphs: small/large, sprase/dense). |
