NAME

cru_prop - specification of a computable vertex property

SYNOPSIS

#include <cru/cru.h>

typedef struct cru_prop_s
{
   struct cru_fold_s vertex;
   struct cru_fold_s incident;
   struct cru_fold_s outgoing;
} *cru_prop;

DESCRIPTION

Some cru library functions depend on arbitrary user-defined properties of the vertices in a graph, which applications can specify in a structure of this type so that the library function can compute one for each vertex. The result computed for each vertex can depend in general on the vertex, the labels on its incident and outgoing edges, and its adjacent vertices in both directions.

The property is computed according to these calling conventions.

• First cru calls the functions referenced by the map fields in the incident and outgoing folds. For each incident edge, it passes the local vertex as the left parameter, the edge label as the middle parameter, and the adjacent vertex as the right parameter to the map function in the incident fold. For each outgoing edge, it passes the local vertex as the left parameter, the edge label as the middle parameter, and the adjacent vertex as the right parameter to the map function in the outgoing fold. Note that the local vertex is always the left parameter regardless of the edge's direction.
• Following the usual calling conventions for cru_fold structures, the incident map results are reduced by the reduction function in the incident fold, and similarly the outgoing map results are reduced by the reduction function in the outgoing fold.
• Then cru calls the map function in the vertex fold, passing the result from the incident reduction as the left parameter, the vertex as the middle parameter, and the result from the outgoing reduction as the right parameter. The result returned by the map function referenced by the vertex fold is taken to be the property of interest.

Either or both of the incident and outgoing fields is allowed to be omitted or filled with zeros. If so, the corresponding result value passed to the map function in the vertex field is NULL.

When this structure is part of a cru_mapreducer, the reduction in the vertex field is used to compute a cumulative result for the whole graph per usual cru_fold calling conventions subject to a slight restriction: only the simpler form of evaluation is enabled, where both operands to the reduction, its output, and the map function's output are of the same type. This restriction applies with or without a vacuous case function being defined, but if defined, it determines the result for empty graphs.

ERRORS

If the application represents properties as pointers, it must avoid having them point to any part of the graph that is dynamically allocated. The graph may be subject to reclamation concurrently with access to the properties, so failure to abide by this convention can cause segmentation faults. An easy workaround is to allocate an unshared copy of the relevant data for the property.

NOTES

The cru_prop structure is used as a field in the cru_prop_pair, cru_kernel, cru_mapreducer, cru_stretcher, cru_splitter, and cru_classifier structures.

The restricted form of fold evaluation noted above for mapreduction operations is a performance tradeoff enabling multiple worker threads to participate in a common reduction. Deterministic results in this case depend on algebraically associative and commutative reduction operators.

FILES

/usr/local/include/cru/data_types.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_inducer, 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_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