COIN-OR::LEMON - Graph Library

Changes between Initial Version and Version 1 of Ticket #377, comment 10


Ignore:
Timestamp:
04/02/17 16:27:08 (7 years ago)
Author:
Peter Kovacs
Comment:

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #377, comment 10

    initial v1  
    11I briefly checked the attached patch. Here are some comments.
    22
    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).
     3Handling 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.
    44
    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()`.
     5Anyway, 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).
    116
    127Apart from that, please use `LEMON_COMPACT_GRAPH_H` instead of `LEMON_FORWARD_GRAPH_H` in lines 19 and 20.