NAME

cru_mutator - specification for overwriting a graph in place

SYNOPSIS

#include <cru/cru.h>

typedef struct cru_mutator_s
{
   struct cru_plan_s mu_plan;
   struct cru_kernel_s mu_kernel;
   struct cru_order_pair_s mu_orders;
} *cru_mutator;

DESCRIPTION

This structure parameterizes the cru_mutated library function with necessary information initialized by the application to overwrite the edges or vertices of a graph in place by user-defined rules. The effect and the direction in which the operation propagates can be localized by the cru_plan structure in the mu_plan field per convention. Alternatively, the mu_plan field may be omitted or zero-filled, in which case the whole graph is modified with an unconstrained traversal priority.

The values overwritten onto the vertices and edges are computed respectively according to the mu_kernel.v_op and mu_kernel.e_op fields following usual cru_kernel calling conventions. That is, vertices are overwritten with the value returned by the function referenced through mu_kernel.v_op.vertex.map, and edge labels are overwritten with the value returned by the function referenced through mu_kernel.e_op.map, neither of which directly modifies its operands. The corresponding reduction fields are not used and may be omitted or NULL.

Further considerations stem from the graph nevertheless being modified in place when these values are overwritten. Following the usual calling conventions for a cru_kernel, when each vertex in the graph is visited, each ternary operator referenced through any of the fields mu_kernel.e_op.map, mu_kernel.v_op.incident.map, or mu_kernel.v_op.outgoing.map is passed the vertex being visited as its left operand, the label of an edge connected to the vertex as its middle operand, and the adjacent vertex at the other end of the edge as the right operand. However, in some cases the operands are those initially appearing in the graph before being mutated, and in other cases they are the modified versions, depending on the following criteria.

• For the operator referenced through the mu_kernel.e_op.map field, the middle operand is always an initial unmodified edge label, and the right operand is always an initial unmodified vertex from the graph as given. However, if a vertex mutation is defined, then the left operand is always the modified form of the vertex.
• For the operator referenced through the mu_kernel.v_op.outgoing.map field, the left operand is always an unmodified vertex. If the traversal priority is remote first and the zone orientation is forward, or if the traversal order is local first and the zone orientation is backwards, then the right operand is a modified vertex. If in either of these cases an edge label mutation is also defined, then the middle operand is a modified edge label, but is otherwise an unmodified edge label. In all other cases, the middle and right operands are in their initial unmodified forms.
• Analogous conditions apply to the mu_kernel.v_op.incident.map field. Its left operand is always an unmodified vertex. If the traversal priority is remote first and the zone orientation is backwards, or if the traversal priority is local first and the zone orientation is forward, then the right operand is a modified vertex. If in either of these cases an edge label mutation is also defined, then the middle operand is a modified edge label, but is otherwise an unmodified edge label. In all other cases, the middle and right operands are in their initial unmodified forms.

If a mu_kernel.v_op.outgoing.bmap is defined instead of a mu_kernel.v_op.outgoing.map, then only the left and middle operands described above are available to it, with the right operand being irrelevant. Similar considerations apply to a mu_kernel.v_op.incident.bmap and a mu_kernel.e_op.bmap. However, the bmap in this context has the advantage of being usable even with unconstrained traversal priorities, unlike the map, because it makes vertex mutations expressible that depend on a vertex being visited and its edges but not on its adjacent vertices. Unconstrained traversal priorities are required for operations on cyclic graphs to avoid deadlock.

The zone orientation, as given by the cru_zone in the mu_plan.zone field, and traversal priority as given by the mu_plan.local_first and mu_plan.remote_first fields, may impose some constraints on the allowed mutations.

• If the traversal priority is unconstrained, then at most one vertex mutation mu_kernel.v_op or edge mutation mu_kernel.e_op may be specified.
• If not all fields of mu_kernel.v_op.outgoing are NULL, then mu_kernel.v_op.outgoing.vacuous_case must refer to an appropriate nullary operator.
• If not all fields of mu_kernel.v_op.incident are NULL, then mu_kernel.v_op.incident.vacuous_case must refer to an appropriate nullary operator.

Because the resulting graph after being modified may have different types of vertices or edges than the given graph, applications specify the new vertex and edge orderings to be associated with it in the mu_orders field. Some inferences about the orders are made by default when parts of the mu_kernel structure are NULL, omitted, or zero-filled.

• If the kernel's vertex operation in mu_kernel.v_op is omitted or zero-filled or the mu_kernel.v_op.vertex.m_free field is identical to the vertex destructor of the given graph, then the vertex ordering mu_orders.v_order is inferred as needed from that of the given graph.
• If the kernel's vertex operation specifies a vertex map through the mu_kernel.v_op.vertex.map field but with a NULL destructor field in mu_kernel.v_op.vertex.m_free, then a default scalar vertex ordering is inferred in the mu_orders.v_order field.
• If the kernel's edge operation in mu_kernel.e_op is omitted, zero-filled, or partially specified, or if the mu_kernel.e_op.m_free field is identical to the given graph's edge destructor, then the edge ordering mu_orders.e_order is inferred as needed from that of the given graph.
• If the kernel's edge operation in mu_kernel.e_op specifies a mutation through the mu_kernel.e_op.map field but with a NULL destructor field in mu_kernel.e_op.m_free, then a default scalar edge label ordering is inferred in the mu_orders.e_order field.

ERRORS

If a necessary vacuous case function is omitted, then the cru_mutated function reports an error of CRU_UNDVAC. If any of the other conditions stated above is not met, then the cru_mutated function reports an error of CRU_INCMUT, for an inconsistent mutation request.

It is an error to omit destructors from the kernel if the results are dynamically allocated and destructors can not be inferred from the given graph. This error is not detectable but will cause memory leaks.

NOTES

Vacuous case functions are required because mutations that depend on the results at adjacent vertices presuppose a graph with at least one vertex lacking prerequisites to avoid deadlock. For this vertex, a vacuous case is necessary.

The limitations on the allowed mutations imposed by the traversal priority are a performance tradeoff. A single pass through the graph updating both vertices and edges and ensuring deterministic results is possible only by disallowing dependences on concurrently updated adjacent vertices or edges.

These conditions imply that vertices can be modified in a way that depends on adjacent vertices only when the order is constrained, but cyclic graphs admit only unconstrained traversal orders. Applications may work around this limitation by performing the required operations in sequence through multiple calls to cru_mutated, thereby implicity barrier synchronizing the operations as of each call. For example, modifying both the vertices and the edges in a cyclic graph would be possible by invoking cru_mutated first with a vertex mutation but no edge mutation, and next with an edge mutation but no vertex mutation defined in the mu_kernel field.

An edge order is necessary for the operations of composition, merging, deduplication, postponement, and stretching existing graphs. For these operations, an edge ordering must be defined or inferrable at some point in advance, so it should be defined or inferrable in the mu_orders.e_order field if any of these operations is anticipated.

FILES

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

/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_inducer, cru_kernel, cru_kill, cru_killed, cru_mapreduced, cru_mapreducer, cru_merged, cru_merger, cru_mutated, 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