%% options copyright owner = Dirk Krause copyright year = 2019-xxxx SPDX-License-Identifier: BSD-3-Clause %% header /** @file dk4bml.h Levelize graph using a bit matrix. Levelizing means counting the path length from start nodes (nodes with no predecessor) to a certain node. Levelizing here must be able to handle loops. Two nodes are in the same loop if there is both a path from one node to the other and a path vice versa. Node a is a one-way predecessor of node b if a is a predecessor of b and there is a path from a to b but not path from b to a. This means a and b are not in the same loop. Nodes without a predecessor are level 0 nodes. In each pass all nodes not yet evaluated are checked. A node is evaluated if at least all one-way predecessor nodes are evaluated. The nodes value/level is the maximum value of all (not just the one-way) predecessors already evaluated, increased by one. */ #ifndef DK4BM_H_INCLUDED #if DK4_BUILDING_DKTOOLS4 #include "dk4bm.h" #else #include #endif #endif #ifdef __cplusplus extern "C" { #endif /** Levelize graph nodes. CRT on Windows: Optional. @param pdest Destination array for the node levels. @param szdest Size of destination array. @param pbm Bit matrix representing the graph. @param isrev Flag: Reverse notation is used in pbm. @param erp Error report, may be NULL. @return 1 on success, 0 on error. Error codes: - DK4_E_INVALID_ARGUMENTS
if pdest or pbm is NULL or szdest is 0, - DK4_E_SYNTAX
if the matrix is not square or szdest is smaller then the number of rows, - DK4_E_MATH_OVERFLOW
if a numeric overflow happens in size calculations for temporary data, - DK4_E_MEMORY_ALLOCATION_FAILED
if a memory allocation attempt for temporary data fails. */ int dk4bm_levelize( size_t *pdest, size_t szdest, dk4_bit_matrix_t const *pbm, int isrev, dk4_er_t *erp ); /** Levelize graph nodes. CRT on Windows: Optional. @param pdest Destination array for the node levels. @param szdest Size of destination array. @param pbm Bit matrix representing the graph, must already be expanded. @param isrev Flag: Reverse notation is used in pbm. @param erp Error report, may be NULL. @return 1 on success, 0 on error. Error codes: - DK4_E_INVALID_ARGUMENTS
if pdest or pbm is NULL or szdest is 0, - DK4_E_SYNTAX
if the matrix is not square or szdest is smaller then the number of rows, - DK4_E_MATH_OVERFLOW
if a numeric overflow happens in size calculations for temporary data, - DK4_E_MEMORY_ALLOCATION_FAILED
if a memory allocation attempt for temporary data fails. */ int dk4bm_levelize_expanded( size_t *pdest, size_t szdest, dk4_bit_matrix_t const *pbm, int isrev, dk4_er_t *erp ); #ifdef __cplusplus } #endif %% module #include "dk4bml.h" #include "dk4bf.h" $!trace-include /** 0 as size_t. */ #define SZ0 ((size_t)0U) /** 1 as size_t. */ #define SZ1 ((size_t)1U) /** Mark all nodes without predecessors as evaluated. @param pbm Bit matrix containing reverse graph representation, must be already expanded. @param pbf Bits to mark nodes as evaluated. */ static void dk4bm_i_reverse_start( dk4_bit_matrix_t const *pbm, dk4_bit_field_t *pbf ) { size_t i; /* Current node to inspect */ size_t j; /* Predecessor candidate */ int hp; /* Flag: Have predecessor */ int v; /* Bit value */ $? "+ dk4bm_i_reverse_start" for (i = SZ0; i < pbm->rows; i++) { hp = 0; for (j = SZ0; j < pbm->rows; j++) { if (i != j) { v = 0; if (0 != dk4bm_get(&v, pbm, i, j, NULL)) { if (0 != v) { hp = 1; } } else { i = j = pbm->rows - SZ1; } } } if (0 == hp) { dk4bf_set(pbf, i, 1, NULL); } } $? "- dk4bm_i_reverse_start" } /** Levelize graph nodes from bit matrix containig reversed representation. @param pdest Destination array for the node levels. @param pbm Bit matrix representing the graph, must already be expanded. @param pbf Bit field, which nodes are already evaluated. */ static void dk4bm_i_reverse_levelize( size_t *pdest, dk4_bit_matrix_t const *pbm, dk4_bit_field_t *pbf ) { size_t i; /* Current node to inspect */ size_t j; /* Predecessor candidate */ size_t max; /* Maximum evaluation value found so far */ #if TRACE_DEBUG size_t passno; /* Current pass number */ #endif int ch; /* Flag: Change occured in current pass */ int unev; /* Flag: Node has unevaluated predecessor */ int v; /* Test value */ $? "+ dk4bm_i_reverse_levelize" /* Mark all nodes without predecessor as evaluated. */ dk4bm_i_reverse_start(pbm, pbf); #if TRACE_DEBUG passno = SZ0; #endif do { $? ". pass %lu", (unsigned long)passno ch = 0; for (i = SZ0; i < pbm->rows; i++) { v = 0; $? ". check node %lu", (unsigned long)i if (0 != dk4bf_get(&v, pbf, i, NULL)) { if (0 == v) { $? ". not yet evaluated" /* Current node i is not yet evaluated */ max = SZ0; unev = 0; for (j = SZ0; j < pbm->rows; j++) { if (i != j) { v = 0; if (0 != dk4bm_get(&v, pbm, i, j, NULL)) { if (0 != v) { v = 0; if (0 != dk4bf_get(&v, pbf, j, NULL)) { if (0 != v) { /* Node j is already evaluated */ if (pdest[j] > max) { max = pdest[j]; } } else { /* Node j is not yet evaluated */ v = 0; if(0 != dk4bm_get(&v,pbm,j,i,NULL)){ /* We can not evaluate node i unless i and j are in a loop. */ if (0 == v) { unev = 1; } } else { /* ERROR */ i = j = pbm->rows - SZ1; ch = 0; } } } else { /* ERROR */ i = j = pbm->rows - SZ1; ch = 0; } } } else { /* ERROR */ i = j = pbm->rows - SZ1; ch = 0; } } } /* Evaluate node if no unevaluated predecessors */ if (0 == unev) { pdest[i] = max + SZ1; dk4bf_set(pbf, i, 1, NULL); ch = 1; $? ". pass=%lu node=%lu level=%lu", (unsigned long)passno, (unsigned long)i, (unsigned long)(max + SZ1) } } #if TRACE_DEBUG else { $? ". already evaluated %lu", (unsigned long)(pdest[i]) } #endif } else { /* ERROR */ i = pbm->rows - SZ1; ch = 0; } } #if TRACE_DEBUG passno++; #endif } while(1 == ch); $? "- dk4bm_i_reverse_levelize" } /** Mark all nodes without predecessors as evaluated. @param pbm Bit matrix containing forward graph representation, must be expanded. @param pbf Bits to mark nodes as evaluated. */ static void dk4bm_i_forward_start( dk4_bit_matrix_t const *pbm, dk4_bit_field_t *pbf ) { size_t i; /* Current node to inspect */ size_t j; /* Predecessor candidate */ int hp; /* Flag: Have predecessor */ int v; /* Bit value */ $? "+ dk4bm_i_forward_start" for (i = SZ0; i < pbm->rows; i++) { hp = 0; for (j = SZ0; j < pbm->rows; j++) { if (i != j) { v = 0; if (0 != dk4bm_get(&v, pbm, j, i, NULL)) { if (0 != v) { hp = 1; } } else { i = j = pbm->rows - SZ1; } } } if (0 == hp) { dk4bf_set(pbf, i, 1, NULL); } } $? "- dk4bm_i_forward_start" } /** Levelize graph nodes from bit matrix containig forward representation. @param pdest Destination array for the node levels. @param szdest Size of destination array. @param pbm Bit matrix representing the graph, must already be expanded. @param pbf Bit field, which nodes are already evaluated. */ static void dk4bm_i_forward_levelize( size_t *pdest, dk4_bit_matrix_t const *pbm, dk4_bit_field_t *pbf ) { size_t i; /* Current node to inspect */ size_t j; /* Predecessor candidate */ size_t max; /* Maximum evaluation value found so far */ #if TRACE_DEBUG size_t passno; /* Current pass number */ #endif int ch; /* Flag: Change occured in current pass */ int unev; /* Flag: Node has unevaluated predecessor */ int v; /* Value */ $? "+ dk4bm_i_forward_levelize" /* Mark all nodes without predecessor as evaluated. */ dk4bm_i_forward_start(pbm, pbf); #if TRACE_DEBUG passno = SZ0; #endif do { $? ". pass %lu", (unsigned long)passno ch = 0; for (i = SZ0; i < pbm->rows; i++) { v = 0; $? ". check node %lu", (unsigned long)i if (0 != dk4bf_get(&v, pbf, i, NULL)) { if (0 == v) { $? ". not yet evaluated" /* Current node i is not yet evaluated */ max = SZ0; unev = 0; for (j = SZ0; j < pbm->rows; j++) { if (i != j) { v = 0; if (0 != dk4bm_get(&v, pbm, j, i, NULL)) { if (0 != v) { v = 0; if (0 != dk4bf_get(&v, pbf, j, NULL)) { if (0 != v) { /* Node j is already evaluated */ if (pdest[j] > max) { max = pdest[j]; } } else { /* Node j is not yet evaluated */ v = 0; if(0 != dk4bm_get(&v,pbm,i,j,NULL)){ /* We can not evaluate node i unless i and j are in a loop. */ if (0 == v) { unev = 1; } } else { /* ERROR */ i = j = pbm->rows - SZ1; ch = 0; } } } else { /* ERROR */ i = j = pbm->rows - SZ1; ch = 0; } } } else { /* ERROR */ i = j = pbm->rows - SZ1; ch = 0; } } } /* Evaluate node if no unevaluated predecessors */ if (0 == unev) { pdest[i] = max + SZ1; dk4bf_set(pbf, i, 1, NULL); ch = 1; $? ". pass=%lu node=%lu level=%lu", (unsigned long)passno, (unsigned long)i, (unsigned long)(max + SZ1) } } #if TRACE_DEBUG else { $? ". already evaluated %lu", (unsigned long)(pdest[i]) } #endif } else { /* ERROR */ i = pbm->rows - SZ1; ch = 0; } } #if TRACE_DEBUG passno++; #endif } while(1 == ch); $? "- dk4bm_i_forward_levelize" } static int dk4bm_i_levelize( size_t *pdest, size_t szdest, dk4_bit_matrix_t const *pbm, int isrev, dk4_er_t *erp ) { dk4_bit_matrix_t *bm = NULL; dk4_bit_field_t *bf = NULL; size_t *pres; size_t i; int back = 0; $? "+ dk4bm_i_levelize" bm = dk4bm_open_copy(pbm, erp); if (NULL != bm) { bf = dk4bf_open(bm->columns, erp); if (NULL != bf) { dk4bm_expand(bm, erp); pres = pdest; for (i = 0; i < szdest; i++) { *(pres++) = 0; } if (0 != isrev) { dk4bm_i_reverse_levelize(pdest, bm, bf); } else { dk4bm_i_forward_levelize(pdest, bm, bf); } back = 1; dk4bf_close(bf); } dk4bm_close(bm, 1); } $? "- dk4bm_i_levelize %d", back return back; } static int dk4bm_i_expanded_levelize( size_t *pdest, size_t szdest, dk4_bit_matrix_t const *pbm, int isrev, dk4_er_t *erp ) { dk4_bit_field_t *bf = NULL; size_t *pres; size_t i; int back = 0; $? "+ dk4bm_i_expanded_levelize" bf = dk4bf_open(pbm->columns, erp); if (NULL != bf) { pres = pdest; for (i = 0; i < szdest; i++) { *(pres++) = 0; } if (0 != isrev) { dk4bm_i_reverse_levelize(pdest, pbm, bf); } else { dk4bm_i_forward_levelize(pdest, pbm, bf); } back = 1; dk4bf_close(bf); } $? "- dk4bm_i_expanded_levelize %d", back return back; } int dk4bm_levelize( size_t *pdest, size_t szdest, dk4_bit_matrix_t const *pbm, int isrev, dk4_er_t *erp ) { int back = 0; $? "+ dk4bm_levelize" if ((NULL != pdest) && (0 < szdest) && (NULL != pbm)) { if ((pbm->rows <= szdest) && (pbm->rows == pbm->columns)) { back = dk4bm_i_levelize(pdest, szdest, pbm, isrev, erp); } else { dk4error_set_simple_error_code(erp, DK4_E_SYNTAX); } } else { dk4error_set_simple_error_code(erp, DK4_E_INVALID_ARGUMENTS); } $? "- dk4bm_levelize %d", back return back; } int dk4bm_levelize_expanded( size_t *pdest, size_t szdest, dk4_bit_matrix_t const *pbm, int isrev, dk4_er_t *erp ) { int back = 0; $? "+ dk4bm_levelize_expanded" if ((NULL != pdest) && (0 < szdest) && (NULL != pbm)) { if ((pbm->rows <= szdest) && (pbm->rows == pbm->columns)) { back = dk4bm_i_expanded_levelize(pdest, szdest, pbm, isrev, erp); } else { dk4error_set_simple_error_code(erp, DK4_E_SYNTAX); } } else { dk4error_set_simple_error_code(erp, DK4_E_INVALID_ARGUMENTS); } $? "- dk4bm_levelize_expanded %d", back return back; } /* vim: set ai sw=4 ts=4 : */