66 lines
2.6 KiB
C
66 lines
2.6 KiB
C
|
#include <c_FlowNetwork.h>
|
||
|
|
|
||
|
|
|
||
|
|
/* ================================================================================================================== */
|
||
|
|
/* Flow Network Infrastructure API Primitives */
|
||
|
|
|
||
|
|
c_err_t c_FlowNetwork_Init(c_FlowNetwork_t* self, c_size_t V, c_Allocator_t* alloc) {
|
||
|
|
if (!self) return C_ERR_PARAM;
|
||
|
|
self->allocator = alloc ? *alloc : c_DefaultAllocator;
|
||
|
|
self->V = V;
|
||
|
|
self->E = 0;
|
||
|
|
self->adj_list = NULL;
|
||
|
|
self->edges_pool = NULL;
|
||
|
|
self->edges_cap = 0;
|
||
|
|
|
||
|
|
if (V > 0) {
|
||
|
|
self->adj_list = (c_UIntArray_t*)c_Allocator_Calloc(&self->allocator, V, sizeof(c_UIntArray_t));
|
||
|
|
if (!self->adj_list) return C_ERR_NOMEM;
|
||
|
|
for (c_size_t i = 0; i < V; ++i) c_UIntArray_Init(&self->adj_list[i], 0, alloc);
|
||
|
|
}
|
||
|
|
return C_SUCCESS;
|
||
|
|
}
|
||
|
|
|
||
|
|
void c_FlowNetwork_Destroy(c_FlowNetwork_t* self) {
|
||
|
|
if (!self) return;
|
||
|
|
if (self->adj_list) {
|
||
|
|
for (c_size_t i = 0; i < self->V; ++i) c_UIntArray_Destroy(&self->adj_list[i]);
|
||
|
|
c_Allocator_Free(&self->allocator, self->adj_list);
|
||
|
|
}
|
||
|
|
if (self->edges_pool) c_Allocator_Free(&self->allocator, self->edges_pool);
|
||
|
|
memset(self, 0, sizeof(*self));
|
||
|
|
}
|
||
|
|
|
||
|
|
c_err_t c_FlowNetwork_AddEdge(c_FlowNetwork_t* self, c_size_t from, c_size_t to, double capacity) {
|
||
|
|
if (!self || from >= self->V || to >= self->V || capacity < 0.0) return C_ERR_PARAM;
|
||
|
|
|
||
|
|
/* Expand pool space to accommodate BOTH the forward edge and its residual twin (+2 entries) */
|
||
|
|
if (self->E + 2 > self->edges_cap) {
|
||
|
|
c_size_t old_cap = self->edges_cap;
|
||
|
|
c_size_t new_cap = old_cap == 0 ? 8 : old_cap * 2;
|
||
|
|
c_FlowEdge_t* new_pool = (c_FlowEdge_t*)c_Allocator_Realloc(
|
||
|
|
&self->allocator, self->edges_pool, old_cap * sizeof(c_FlowEdge_t), new_cap * sizeof(c_FlowEdge_t)
|
||
|
|
);
|
||
|
|
if (!new_pool) return C_ERR_NOMEM;
|
||
|
|
self->edges_pool = new_pool;
|
||
|
|
self->edges_cap = new_cap;
|
||
|
|
}
|
||
|
|
|
||
|
|
c_size_t forward_id = self->E;
|
||
|
|
c_size_t residual_id = self->E + 1;
|
||
|
|
|
||
|
|
/* Push edge pairs sequentially to lock bitwise XOR reverse mapping property */
|
||
|
|
self->edges_pool[forward_id] = (c_FlowEdge_t){ .from = from, .to = to, .capacity = capacity, .flow = 0.0 };
|
||
|
|
self->edges_pool[residual_id] = (c_FlowEdge_t){ .from = to, .to = from, .capacity = 0.0, .flow = 0.0 };
|
||
|
|
|
||
|
|
/* Wire edge pointer handles into both adjacency lists to track backward residual flow channels */
|
||
|
|
c_err_t err = c_UIntArray_Append(&self->adj_list[from], (c_uint_t)forward_id);
|
||
|
|
if (err != C_SUCCESS) return err;
|
||
|
|
err = c_UIntArray_Append(&self->adj_list[to], (c_uint_t)residual_id);
|
||
|
|
if (err != C_SUCCESS) return err;
|
||
|
|
|
||
|
|
self->E += 2;
|
||
|
|
return C_SUCCESS;
|
||
|
|
}
|
||
|
|
|