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) {
59 for (NodeID node2 = 0; node2 < this->
Size(); ++node2) {
67 void LinkGraph::Compress()
70 for (NodeID node1 = 0; node1 < this->
Size(); ++node1) {
71 this->
nodes[node1].supply /= 2;
72 for (NodeID node2 = 0; node2 < this->
Size(); ++node2) {
73 BaseEdge &edge = this->
edges[node1][node2];
74 if (edge.capacity > 0) {
75 edge.
capacity = std::max(1U, edge.capacity / 2);
78 if (edge.travel_time_sum > 0) {
79 edge.travel_time_sum = std::max(1ULL, edge.travel_time_sum / 2);
93 NodeID first = this->
Size();
94 for (NodeID node1 = 0; node1 < other->
Size(); ++node1) {
96 NodeID new_node = this->
AddNode(st);
100 for (NodeID node2 = 0; node2 < node1; ++node2) {
103 forward = other->
edges[node1][node2];
104 backward = other->
edges[node2][node1];
115 new_start = other->
edges[node1][node1];
127 assert(id < this->
Size());
129 NodeID last_node = this->
Size() - 1;
130 for (NodeID i = 0; i <= last_node; ++i) {
131 (*this)[i].RemoveEdge(
id);
135 while (next != INVALID_NODE) {
136 if (next == last_node) {
143 node_edges[id] = node_edges[last_node];
149 this->
nodes.pop_back();
168 NodeID new_node = this->
Size();
169 this->
nodes.emplace_back();
172 this->
edges.
Resize(new_node + 1U, std::max(new_node + 1U, this->
edges.Height()));
180 new_edges[new_node].
next_edge = INVALID_NODE;
182 for (NodeID i = 0; i <= new_node; ++i) {
184 this->
edges[i][new_node].Init();
199 assert(this->
index != to);
220 assert(capacity > 0);
221 assert(usage <= capacity);
222 if (this->
edges[to].capacity == 0) {
223 this->AddEdge(to, capacity, usage, travel_time, mode);
225 (*this)[to].Update(capacity, usage, travel_time, mode);
235 if (this->
index == to)
return;
243 NodeID prev = this->
index;
244 NodeID next = this->
edges[this->
index].next_edge;
245 while (next != INVALID_NODE) {
253 next = this->
edges[next].next_edge;
270 assert(this->edge.capacity > 0);
271 assert(capacity >= usage);
274 if (this->edge.travel_time_sum == 0) {
275 this->edge.travel_time_sum = (this->edge.capacity + capacity) * travel_time;
276 }
else if (travel_time == 0) {
277 this->edge.travel_time_sum += this->edge.travel_time_sum / this->edge.capacity * capacity;
279 this->edge.travel_time_sum += travel_time * capacity;
281 this->edge.capacity += capacity;
282 this->edge.usage += usage;
284 if (this->edge.travel_time_sum == 0) {
285 this->edge.capacity = std::max(this->edge.capacity, capacity);
286 this->edge.travel_time_sum = travel_time * this->edge.capacity;
287 }
else if (capacity > this->edge.capacity) {
288 this->edge.travel_time_sum = this->edge.travel_time_sum / this->edge.capacity * capacity;
289 this->edge.capacity = capacity;
291 this->edge.usage = std::max(this->edge.usage, usage);
304 assert(this->
Size() == 0);
306 this->
nodes.resize(size);
308 for (uint i = 0; i < size; ++i) {
309 this->
nodes[i].Init();
311 for (uint j = 0; j < size; ++j) column[j].
Init();