122 lines
4.9 KiB
C
122 lines
4.9 KiB
C
#include <c_DirectedEulerianCycle.h>
|
|
#include "c_NonrecursiveDirectedDFS.h"
|
|
|
|
c_err_t c_DirectedEulerianCycle_Init(c_DirectedEulerianCycle_t* self, c_Digraph_t* graph, c_Allocator_t* allocator) {
|
|
if (!self || !graph) return C_ERR_PARAM;
|
|
|
|
self->allocator = allocator ? *allocator : c_DefaultAllocator;
|
|
c_VertexIdList_Init(&self->cycle, 0, allocator);
|
|
|
|
/* Edge case: An empty graph with no edges trivially has an empty Eulerian cycle path */
|
|
if (graph->E == 0) return C_SUCCESS;
|
|
|
|
/* 1. Necessary condition verification: In-degree must equal Out-degree for all nodes */
|
|
c_size_t non_isolated_vertex = graph->V;
|
|
for (c_size_t v = 0; v < graph->V; ++v) {
|
|
c_size_t out_deg = c_Digraph_GetOutDegree(graph, v);
|
|
c_size_t in_deg = c_Digraph_GetInDegree(graph, v);
|
|
|
|
if (out_deg != in_deg) {
|
|
return C_SUCCESS; /* No Eulerian cycle exists, return gracefully with empty cycle path */
|
|
}
|
|
if (out_deg > 0 && non_isolated_vertex == graph->V) {
|
|
non_isolated_vertex = v; /* Track a starting node candidates containing edges */
|
|
}
|
|
}
|
|
|
|
if (non_isolated_vertex == graph->V) return C_SUCCESS; // Graph has no edges
|
|
|
|
/* 2. Necessary condition verification: Connectivity check via non-recursive DFS */
|
|
c_NonrecursiveDirectedDFS_t dfs;
|
|
c_err_t err = c_NonrecursiveDirectedDFS_Init(&dfs, graph, non_isolated_vertex, allocator);
|
|
if (err != C_SUCCESS) return err;
|
|
|
|
for (c_size_t v = 0; v < graph->V; ++v) {
|
|
if (c_Digraph_GetOutDegree(graph, v) > 0 && !c_NonrecursiveDirectedDFS_HasPathTo(&dfs, v, graph->V)) {
|
|
c_NonrecursiveDirectedDFS_Destroy(&dfs);
|
|
return C_SUCCESS; /* Graph edges are disconnected */
|
|
}
|
|
}
|
|
c_NonrecursiveDirectedDFS_Destroy(&dfs);
|
|
|
|
/* 3. Hierholzer's Algorithm: Construct the cycle path */
|
|
/* Maintain local tracking copies of current edge indexing to safely 'consume' them */
|
|
c_size_t* edge_index_iterator = (c_size_t*)c_Allocator_Calloc(&self->allocator, graph->V, sizeof(c_size_t));
|
|
if (!edge_index_iterator) return C_ERR_NOMEM;
|
|
|
|
/* Stack setup for path assembly tracking: capacity bounded by E + 1 */
|
|
c_size_t max_stack_cap = graph->E + 1;
|
|
c_size_t* path_stack = (c_size_t*)c_Allocator_Calloc(&self->allocator, max_stack_cap, sizeof(c_size_t));
|
|
if (!path_stack) {
|
|
c_Allocator_Free(&self->allocator, edge_index_iterator);
|
|
return C_ERR_NOMEM;
|
|
}
|
|
|
|
/* Temporary collector stack tracking for final inversion layout */
|
|
c_size_t* output_stack = (c_size_t*)c_Allocator_Calloc(&self->allocator, max_stack_cap, sizeof(c_size_t));
|
|
if (!output_stack) {
|
|
c_Allocator_Free(&self->allocator, edge_index_iterator);
|
|
c_Allocator_Free(&self->allocator, path_stack);
|
|
return C_ERR_NOMEM;
|
|
}
|
|
|
|
c_size_t path_stack_size = 0;
|
|
c_size_t output_stack_size = 0;
|
|
|
|
/* Start the path construction from our candidate node */
|
|
path_stack[path_stack_size++] = non_isolated_vertex;
|
|
|
|
while (path_stack_size > 0) {
|
|
c_size_t curr_v = path_stack[path_stack_size - 1];
|
|
c_AdjList_t* adj = &graph->adj_list[curr_v];
|
|
c_size_t out_degree = (c_size_t)c_UIntArray_GetSize(adj);
|
|
|
|
if (edge_index_iterator[curr_v] < out_degree) {
|
|
c_uint_t target_w = 0;
|
|
err = c_UIntArray_Get(adj, edge_index_iterator[curr_v], &target_w);
|
|
edge_index_iterator[curr_v]++; /* Consume the edge */
|
|
|
|
if (err == C_SUCCESS) {
|
|
path_stack[path_stack_size++] = (c_size_t)target_w;
|
|
}
|
|
} else {
|
|
/* Backtrack step: Node has no remaining active edges out, push to tour results */
|
|
output_stack[output_stack_size++] = curr_v;
|
|
path_stack_size--;
|
|
}
|
|
}
|
|
|
|
/* Push collected route into the formal c_VertexIdList storage layout matching target sequential format */
|
|
while (output_stack_size > 0) {
|
|
c_VertexIdList_Append(&self->cycle, (c_uint_t)output_stack[--output_stack_size]);
|
|
}
|
|
|
|
/* Clean up local working variables */
|
|
c_Allocator_Free(&self->allocator, edge_index_iterator);
|
|
c_Allocator_Free(&self->allocator, path_stack);
|
|
c_Allocator_Free(&self->allocator, output_stack);
|
|
|
|
return C_SUCCESS;
|
|
}
|
|
|
|
void c_DirectedEulerianCycle_Destroy(c_DirectedEulerianCycle_t* self) {
|
|
if (!self) return;
|
|
c_VertexIdList_Destroy(&self->cycle);
|
|
}
|
|
|
|
c_err_t c_DirectedEulerianCycle_GetCycle(c_DirectedEulerianCycle_t* self, c_VertexIdList_t* out_cycle) {
|
|
if (!self || !out_cycle) return C_ERR_PARAM;
|
|
if (!c_DirectedEulerianCycle_HasCycle(self)) return C_ERR_FAIL;
|
|
|
|
c_size_t size = (c_size_t)c_VertexIdList_GetSize(&self->cycle);
|
|
for (c_size_t i = 0; i < size; ++i) {
|
|
c_uint_t val = 0;
|
|
c_err_t err = c_VertexIdList_Get((c_VertexIdList_t*)&self->cycle, i, &val);
|
|
if (err == C_SUCCESS) {
|
|
c_err_t app_err = c_VertexIdList_Append(out_cycle, val);
|
|
if (app_err != C_SUCCESS) return app_err;
|
|
}
|
|
}
|
|
return C_SUCCESS;
|
|
}
|