10 #include "../stdafx.h"
11 #include "../core/pool_func.hpp"
14 #include "../safeguards.h"
30 this->demand = demand;
56 for (NodeID node1 = 0; node1 < this->
Size(); ++node1) {
66 void LinkGraph::Compress()
69 for (NodeID node1 = 0; node1 < this->
Size(); ++node1) {
70 this->
nodes[node1].supply /= 2;
71 for (BaseEdge &edge : this->
nodes[node1].edges) {
72 if (edge.capacity > 0) {
73 uint new_capacity = std::max(1U, edge.capacity / 2);
74 if (edge.capacity < (1 << 16)) {
75 edge.travel_time_sum = edge.travel_time_sum * new_capacity / edge.capacity;
76 }
else if (edge.travel_time_sum != 0) {
77 edge.travel_time_sum = std::max<uint64_t>(1, edge.travel_time_sum / 2);
79 edge.capacity = new_capacity;
94 NodeID first = this->
Size();
95 for (NodeID node1 = 0; node1 < other->
Size(); ++node1) {
97 NodeID new_node = this->
AddNode(st);
103 BaseEdge &new_edge = this->
nodes[new_node].edges.emplace_back(first + e.dest_node);
118 assert(id < this->
Size());
120 NodeID last_node = this->
Size() - 1;
125 this->
nodes.pop_back();
126 for (
auto &n : this->
nodes) {
128 auto [first, last] = std::equal_range(n.edges.begin(), n.edges.end(),
id);
130 auto insert = n.edges.erase(first, last);
132 if (!n.edges.empty() && n.edges.back().dest_node == last_node) {
134 n.edges.back().dest_node = id;
135 n.edges.insert(insert, n.edges.back());
153 NodeID new_node = this->
Size();
169 assert(!this->HasEdgeTo(to));
171 BaseEdge &edge = *this->edges.emplace(std::upper_bound(this->edges.begin(), this->edges.end(), to), to);
188 assert(capacity > 0);
189 assert(usage <= capacity);
190 if (!this->HasEdgeTo(to)) {
191 this->AddEdge(to, capacity, usage, travel_time, mode);
193 this->GetEdge(to)->Update(capacity, usage, travel_time, mode);
203 auto [first, last] = std::equal_range(this->edges.begin(), this->edges.end(), to);
204 this->edges.erase(first, last);
219 assert(this->capacity > 0);
220 assert(capacity >= usage);
223 if (this->travel_time_sum == 0) {
224 this->travel_time_sum =
static_cast<uint64_t
>(this->capacity + capacity) * travel_time;
225 }
else if (travel_time == 0) {
226 this->travel_time_sum += this->travel_time_sum / this->capacity * capacity;
228 this->travel_time_sum +=
static_cast<uint64_t
>(travel_time) * capacity;
230 this->capacity += capacity;
231 this->usage += usage;
233 if (this->travel_time_sum == 0) {
234 this->capacity = std::max(this->capacity, capacity);
235 this->travel_time_sum =
static_cast<uint64_t
>(travel_time) * this->capacity;
236 }
else if (capacity > this->capacity) {
237 this->travel_time_sum = this->travel_time_sum / this->capacity * capacity;
238 this->capacity = capacity;
240 this->usage = std::max(this->usage, usage);
253 assert(this->
Size() == 0);
254 this->
nodes.resize(size);