|
@@ -148,131 +148,131 @@ public:
|
|
|
/**
|
|
|
* Constructor.
|
|
|
* @param job Link graph job to work with.
|
|
|
*/
|
|
|
FlowEdgeIterator(LinkGraphJob &job) : job(job)
|
|
|
{
|
|
|
for (NodeID i = 0; i < job.Size(); ++i) {
|
|
|
StationID st = job[i].Station();
|
|
|
if (st >= this->station_to_node.size()) {
|
|
|
this->station_to_node.resize(st + 1);
|
|
|
}
|
|
|
this->station_to_node[st] = i;
|
|
|
}
|
|
|
}
|
|
|
|
|
|
/**
|
|
|
* Setup the node to retrieve edges from.
|
|
|
* @param source Root of the current path tree.
|
|
|
* @param node Current node to be checked for outgoing flows.
|
|
|
*/
|
|
|
void SetNode(NodeID source, NodeID node)
|
|
|
{
|
|
|
const FlowStatMap &flows = this->job[node].Flows();
|
|
|
FlowStatMap::const_iterator it = flows.find(this->job[source].Station());
|
|
|
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.
|
|
|
* @param source_node Node where the algorithm starts.
|
|
|
* @param paths Container for the paths to be calculated.
|
|
|
*/
|
|
|
template<class Tannotation, class Tedge_iterator>
|
|
|
void MultiCommodityFlow::Dijkstra(NodeID source_node, PathVector &paths)
|
|
|
{
|
|
|
typedef std::set<Tannotation *, typename Tannotation::Comparator> AnnoSet;
|
|
|
Tedge_iterator iter(this->job);
|
|
|
uint size = this->job.Size();
|
|
|
AnnoSet annos;
|
|
|
paths.resize(size, NULL);
|
|
|
for (NodeID node = 0; node < size; ++node) {
|
|
|
Tannotation *anno = new Tannotation(node, node == source_node);
|
|
|
anno->UpdateAnnotation();
|
|
|
annos.insert(anno);
|
|
|
paths[node] = anno;
|
|
|
}
|
|
|
while (!annos.empty()) {
|
|
|
typename AnnoSet::iterator i = annos.begin();
|
|
|
Tannotation *source = *i;
|
|
|
annos.erase(i);
|
|
|
NodeID from = source->GetNode();
|
|
|
iter.SetNode(source_node, from);
|
|
|
for (NodeID to = iter.Next(); to != INVALID_NODE; to = iter.Next()) {
|