NAME

cru_inducer - inductive graph metric computation specification

SYNOPSIS

#include <cru/cru.h>

typedef struct cru_inducer_s
{
   cru_uop boundary_value;
   struct cru_zone_s in_zone;
   struct cru_fold_s in_fold;
} *cru_inducer;

DESCRIPTION

This structure parameterizes the cru_induced library function with necessary information initialized by the application to compute an arbitrary user-defined metric about a graph. The computation can pertain to a section of the graph restricted by the cru_zone structure in the in_zone field. Alternatively, the in_zone field may be omitted or zero-filled, in which case the whole graph is used and a forward zone orientation is inferred.

Unlike a mapreduction, this operation constrains the order for visiting the vertices, and unlike a mutation, the traversal priority is fixed as remote first.

• Each vertex is visited and a result computed for it starting at those most distant from the initial vertex and finishing at the initial vertex.
• The result computed at each vertex depends on the vertex itself and on the results obtained at its adjacent prerequisite vertices.
• The prerequisites are accessed via the outgoing edges if the in_zone field specifies a forward orientation, and the incoming edges otherwise.
• The result overall is that of the initial vertex.

The value associated with each vertex having no prerequisites is either the value returned by the nullary operator referenced through the in_fold.vacuous_case field, or the unary operator referenced by the boundary_value field applied to the vertex. The latter takes precedence if it is not NULL. To compute the result associated with any vertex having prerequisites, these steps are taken.

• For each edge connecting the vertex to a prerequisite, the ternary operator referenced through the in_fold.map field is passed the vertex as its left operand, the edge label as its middle operand, and the result computed at the prerequisite as its right operand.
• The set of the results returned by the ternary operator and a vacuous case result returned by the function referenced through the in_fold.vacuous_case field are then reduced by the binary operator referenced through the in_fold.reduction field following usual cru_fold calling conventions.

Note that the in_fold.map ternary operator is passed the same vertex as its left operand for each of its prerequisites' results on the right, and that this calling convention is independent of the edge's direction.

Ordinarily, the in_fold.map and at least one of the in_fold.vacuous_case or boundary_value fields must be defined to point to appropriate operators. The in_fold.map field may be left unspecified when the boundary_value field is defined and the in_zone field specifies an initial vertex and traversal direction such that the initial vertex has no prerequisites. The map is not needed in this case because only the initial vertex is visited and the result is given by the boundary value. Where the map is not needed, neither is the in_fold.reduction required.

If all three of the fields in_fold.m_free, in_fold.r_free and in_fold.reduction are NULL, then a binary operator is inferred for the in_fold.reduction that returns the lesser of its two operands interpreted as unsigned integers.

ERRORS

The err parameter is used to report any events preventing successful completion of the requested operation to the caller. If *err is zero on entry and the operation does not succeed, then *err is assigned a non-zero number. If the operation does not succeed because a user-defined callback function reports an error, then the number reported by the callback function is assigned to *err. Positive numbers are for POSIX or user-defined error codes, negative numbers down to -CRU_MAX_ERR are specific to cru, and other negative numbers are allowed as user-defined error codes.

Values of *err listed below refer to errors that are detected and handled. Unlisted values in the range of -CRU_INT_ERR through -CRU_MAX_ERR likely indicate internal errors attributable to bugs in cru. Any other unlisted values may indicate memory corruption, invalid usage of the API, or conditions relevant to user-defined callback functions.

CRU_UNDMAP

The in_fold.map field is NULL but needed to be specified.

CRU_UNDRED

The in_fold.reduction field is NULL and not inferrable.

CRU_UNDVAC

The in_fold.vacuous_case field is NULL.

EXAMPLE

An example of a situation in which the in_fold.map field need not be specified is an induction over a graph g built with no edges terminating on the initial vertex. Specifying the structure

struct cru_inducer_s i = {
   .boundary_value = (cru_uop) my_root_evaluator,
   .in_zone = {
      .backwards = 1}};

causes my_root_evaluator to be passed the initial vertex of g in the invocation

result = cru_induced (g, &i, UNKILLABLE, SEQUENTIALLY, err);

and its return value to be assigned to the result. No other vertices are visited, so in this example no performance penalty accrues to sequential operation. If an inital vertex were specified explicitly in the in_zone field differing from the initial vertex used to build the graph, then g would have be searched for it and performance might be affected. For this operation to be useful, typically the graph g will have been mutated since being built with the effect of storing or encoding some worthwhile result in the initial vertex.

FILES

/usr/local/include/cru/data_types.h

/usr/local/include/cru/error_codes.h

SEE ALSO

cru, cru_bop, cru_bpred, cru_builder, cru_built, cru_cbop, cru_classifier, cru_class_of, cru_class_size, cru_composed, cru_composer, cru_connect, cru_connector, cru_cqop, cru_crossed, cru_crosser, cru_ctop, cru_ctop_pair, cru_ctop_quad, cru_data_types, cru_deduplicated, cru_destructor, cru_destructor_pair, cru_edge_count, cru_fabricated, cru_fabricator, cru_filter, cru_filtered, cru_fold, cru_free_kill_switch, cru_free_later, cru_free_now, cru_free_partition, cru_function_types, cru_get, cru_hash, cru_induced, cru_kernel, cru_kill, cru_killed, cru_mapreduced, cru_mapreducer, cru_merged, cru_merger, cru_mutated, cru_mutator, cru_new_kill_switch, cru_nop, cru_order, cru_order_pair, cru_partition_of, cru_plan, cru_postponed, cru_postponer, cru_prop, cru_prop_pair, cru_pruner, cru_qop, cru_qpred, cru_set, cru_sig, cru_singleton, cru_split, cru_splitter, cru_spread, cru_strerror, cru_stretch, cru_stretched, cru_stretcher, cru_subconnector, cru_terminus_count, cru_top, cru_tpred, cru_united, cru_uop, cru_vertex_count, cru_zone

AUTHOR

Dennis Furey (milonga@delayinsensitive.com)

PROJECT PAGE

https://github.com/gueststar/cru