51 lines
1.8 KiB
C
51 lines
1.8 KiB
C
|
#include <c_CPM.h>
|
||
|
|
|
||
|
|
|
||
|
|
c_err_t c_CPM_Init(c_CPM_t* self, c_size_t num_tasks, const double* task_durations, c_Allocator_t* allocator) {
|
||
|
|
if (!self || num_tasks == 0 || !task_durations) return C_ERR_PARAM;
|
||
|
|
|
||
|
|
self->allocator = allocator ? *allocator : c_DefaultAllocator;
|
||
|
|
self->num_tasks = num_tasks;
|
||
|
|
|
||
|
|
/* Internal node architecture layout mapping:
|
||
|
|
* - Task i start node: i
|
||
|
|
* - Task i finish node: i + num_tasks
|
||
|
|
* - Virtual source node: 2 * num_tasks
|
||
|
|
* - Virtual sink node: 2 * num_tasks + 1
|
||
|
|
*/
|
||
|
|
self->source_node = 2 * num_tasks;
|
||
|
|
self->sink_node = 2 * num_tasks + 1;
|
||
|
|
self->V = 2 * num_tasks + 2;
|
||
|
|
|
||
|
|
return C_SUCCESS;
|
||
|
|
}
|
||
|
|
|
||
|
|
|
||
|
|
c_err_t c_CPM_AddDependency(c_CPM_t* self, c_EdgeWeightedDigraph_t* working_graph, c_size_t prereq_task, c_size_t target_task) {
|
||
|
|
if (!self || !working_graph || prereq_task >= self->num_tasks || target_task >= self->num_tasks) return C_ERR_PARAM;
|
||
|
|
|
||
|
|
/* Connect the FINISH node of prereq to the START node of target */
|
||
|
|
return c_EdgeWeightedDigraph_AddEdge(working_graph, prereq_task + self->num_tasks, target_task, 0.0);
|
||
|
|
}
|
||
|
|
|
||
|
|
c_err_t c_CPM_Calculate(c_CPM_t* self, c_EdgeWeightedDigraph_t* working_graph) {
|
||
|
|
if (!self || !working_graph) return C_ERR_PARAM;
|
||
|
|
|
||
|
|
/* Execute the linear Acyclic Longest Path pass from our virtual source anchor */
|
||
|
|
return c_AcyclicLP_Init(&self->lp_engine, working_graph, self->source_node, &self->allocator);
|
||
|
|
}
|
||
|
|
|
||
|
|
void c_CPM_Destroy(c_CPM_t* self) {
|
||
|
|
if (!self) return;
|
||
|
|
c_AcyclicLP_Destroy(&self->lp_engine);
|
||
|
|
self->num_tasks = 0;
|
||
|
|
self->source_node = 0;
|
||
|
|
self->sink_node = 0;
|
||
|
|
self->V = 0;
|
||
|
|
}
|
||
|
|
|
||
|
|
c_err_t c_CPM_GetCriticalPath(c_CPM_t* self, c_VertexIdList_t* out_critical_edges) {
|
||
|
|
if (!self || !out_critical_edges) return C_ERR_PARAM;
|
||
|
|
return c_AcyclicLP_PathTo(&self->lp_engine, self->sink_node, out_critical_edges);
|
||
|
|
}
|