summaryrefslogtreecommitdiff
path: root/support/dktools/dk4bml.ctr
diff options
context:
space:
mode:
authorNorbert Preining <norbert@preining.info>2020-09-20 03:03:26 +0000
committerNorbert Preining <norbert@preining.info>2020-09-20 03:03:26 +0000
commit1f457376b478257b88d4a857f5ec1b6155442dd7 (patch)
tree2a06a60551dea362cf8cb0cb0ba66c78608717c4 /support/dktools/dk4bml.ctr
parentac690ca29ad5bf8a5203a65fd6252f7b564f4727 (diff)
CTAN sync 202009200303
Diffstat (limited to 'support/dktools/dk4bml.ctr')
-rw-r--r--support/dktools/dk4bml.ctr585
1 files changed, 585 insertions, 0 deletions
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 <dktools-4/dk4bm.h>
+#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<br>
+ if pdest or pbm is NULL or szdest is 0,
+ - DK4_E_SYNTAX<br>
+ if the matrix is not square or szdest is smaller then the number of rows,
+ - DK4_E_MATH_OVERFLOW<br>
+ if a numeric overflow happens in size calculations for
+ temporary data,
+ - DK4_E_MEMORY_ALLOCATION_FAILED<br>
+ 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<br>
+ if pdest or pbm is NULL or szdest is 0,
+ - DK4_E_SYNTAX<br>
+ if the matrix is not square or szdest is smaller then the number of rows,
+ - DK4_E_MATH_OVERFLOW<br>
+ if a numeric overflow happens in size calculations for
+ temporary data,
+ - DK4_E_MEMORY_ALLOCATION_FAILED<br>
+ 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 : */