|
@@ -184,25 +184,25 @@ public:
|
|
|
*/
|
|
|
NodeID Next()
|
|
|
{
|
|
|
if (this->it == this->end) return INVALID_NODE;
|
|
|
return this->station_to_node[(this->it++)->second];
|
|
|
}
|
|
|
};
|
|
|
|
|
|
/**
|
|
|
* Determines if an extension to the given Path with the given parameters is
|
|
|
* better than this path.
|
|
|
* @param base Other path.
|
|
|
* @param cap Capacity of the new edge to be added to base.
|
|
|
* @param free_cap Capacity of the new edge to be added to base.
|
|
|
* @param dist Distance of the new edge.
|
|
|
* @return True if base + the new edge would be better than the path associated
|
|
|
* with this annotation.
|
|
|
*/
|
|
|
bool DistanceAnnotation::IsBetter(const DistanceAnnotation *base, uint cap,
|
|
|
int free_cap, uint dist) const
|
|
|
{
|
|
|
/* If any of the paths is disconnected, the other one is better. If both
|
|
|
* are disconnected, this path is better.*/
|
|
|
if (base->distance == UINT_MAX) {
|
|
|
return false;
|
|
|
} else if (this->distance == UINT_MAX) {
|
|
@@ -218,25 +218,25 @@ bool DistanceAnnotation::IsBetter(const
|
|
|
/* If the other path doesn't have capacity left, but this one has,
|
|
|
* the other one is worse (thus, return false).
|
|
|
* If both paths are out of capacity, do the regular distance
|
|
|
* comparison. */
|
|
|
return this->free_capacity > 0 ? false : (base->distance + dist < this->distance);
|
|
|
}
|
|
|
}
|
|
|
|
|
|
/**
|
|
|
* Determines if an extension to the given Path with the given parameters is
|
|
|
* better than this path.
|
|
|
* @param base Other path.
|
|
|
* @param cap Capacity of the new edge to be added to base.
|
|
|
* @param free_cap Capacity of the new edge to be added to base.
|
|
|
* @param dist Distance of the new edge.
|
|
|
* @return True if base + the new edge would be better than the path associated
|
|
|
* with this annotation.
|
|
|
*/
|
|
|
bool CapacityAnnotation::IsBetter(const CapacityAnnotation *base, uint cap,
|
|
|
int free_cap, uint dist) const
|
|
|
{
|
|
|
int min_cap = Path::GetCapacityRatio(min(base->free_capacity, free_cap), min(base->capacity, cap));
|
|
|
int this_cap = this->GetCapacityRatio();
|
|
|
if (min_cap == this_cap) {
|
|
|
/* If the capacities are the same and the other path isn't disconnected
|
|
|
* choose the shorter path. */
|