|
@@ -172,83 +172,83 @@ public:
|
|
|
if (it != flows.end()) {
|
|
|
this->it = it->second.GetShares()->begin();
|
|
|
this->end = it->second.GetShares()->end();
|
|
|
} else {
|
|
|
this->it = FlowStat::empty_sharesmap.begin();
|
|
|
this->end = FlowStat::empty_sharesmap.end();
|
|
|
}
|
|
|
}
|
|
|
|
|
|
/**
|
|
|
* Get the next node for which a flow exists.
|
|
|
* @return ID of next node with flow.
|
|
|
*/
|
|
|
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) {
|
|
|
return true;
|
|
|
}
|
|
|
|
|
|
if (free_cap > 0 && base->free_capacity > 0) {
|
|
|
/* If both paths have capacity left, compare their distances.
|
|
|
* If the other path has capacity left and this one hasn't, the
|
|
|
* other one's better (thus, return true). */
|
|
|
return this->free_capacity > 0 ? (base->distance + dist < this->distance) : true;
|
|
|
} else {
|
|
|
/* 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. */
|
|
|
return base->distance == UINT_MAX ? false : (base->distance + dist < this->distance);
|
|
|
} else {
|
|
|
return min_cap > this_cap;
|
|
|
}
|
|
|
}
|
|
|
|
|
|
/**
|
|
|
* A slightly modified Dijkstra algorithm. Grades the paths not necessarily by
|
|
|
* distance, but by the value Tannotation computes. It uses the max_saturation
|
|
|
* setting to artificially decrease capacities.
|
|
|
* @tparam Tannotation Annotation to be used.
|
|
|
* @tparam Tedge_iterator Iterator to be used for getting outgoing edges.
|