From 1f457376b478257b88d4a857f5ec1b6155442dd7 Mon Sep 17 00:00:00 2001 From: Norbert Preining Date: Sun, 20 Sep 2020 03:03:26 +0000 Subject: CTAN sync 202009200303 --- support/dktools/dk4bml.ctr | 585 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 585 insertions(+) create mode 100644 support/dktools/dk4bml.ctr (limited to 'support/dktools/dk4bml.ctr') diff --git a/support/dktools/dk4bml.ctr b/support/dktools/dk4bml.ctr new file mode 100644 index 0000000000..86acc9edb7 --- /dev/null +++ b/support/dktools/dk4bml.ctr @@ -0,0 +1,585 @@ +%% 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 : */ -- cgit v1.2.3