NAME

cru_merger - specification for simplifying a graph by equivalence

SYNOPSIS

#include <cru/cru.h>

typedef struct cru_merger_s
{
   struct cru_classifier_s me_classifier;
   struct cru_order_pair_s me_orders;
   struct cru_kernel_s me_kernel;
   cru_pruner pruner;
} *cru_merger;

DESCRIPTION

This structure parameterizes the cru_merged library function with necessary information initialized by the application to reduce classes of related vertices in a graph to single vertices.

• The me_classifier field defines an equivalence relation on the vertices in a graph by the usual cru_classifier calling conventions.
• The vertex operation in the me_kernel.v_op field specifies the method of reducing the set of vertices in a class to a single vertex according to the usual cru_prop calling conventions.
• The edge operation in the me_kernel.e_op field specifies the way a set of edges is reduced to a single edge according to the usual cru_fold calling conventions.
• The pruner field provides for the selective deletion of edges following the usual cru_pruner calling conventions.
• Because the resulting graph after being merged 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 me_orders field.

The sets of edges the kernel reduces are determined by the classes of mutually related vertices, and the result of reducing a set of edges is allowed to depend on the results of reducing the classes containing the edges' origins and termini.

• Any two edges are assigned to the same set of edges whenever their respective origins and termini are assigned to the same sets of vertices according to the cru_classifier.
• For each edge in a set to be reduced, the me_kernel.e_op.map operation is passed the edge's label as the middle operand and the vertices obtained by reducing the classes containing the edge's origin and terminus as the respective left and right operands.
• Because the origins of all edges in any set to be reduced belong to the same class and the termini belong to the same class, the same left operand and the same right operand are passed to the map for each edge in the set.

Some inferences are made by default when parts of this structure are NULL, omitted, or zero-filled.

• If the me_classifier field is omitted or zero-filled, then one is inferred that puts every vertex in a class by itself.
• If the pruner field is NULL, then no edges are deleted.
• If the kernel's vertex operation in me_kernel.v_op is omitted or zero-filled, then the vertex ordering in the me_orders.v_order field is inferred from that of the given graph.
• If the kernel's vertex operation specifies a vertex reduction through the me_kernel.v_op.vertex.reduction field but with a NULL destructor field in me_kernel.v_op.vertex.r_free, then a default scalar vertex ordering is inferred in the me_orders.v_order field.
• If the kernel's edge operation in me_kernel.e_op is omitted or zero-filled, then the edge ordering in the me_orders.e_order field is inferred from that of the given graph, and the edges are deduplicated rather than being reduced. In this case, there may be multiple similarly directed edges between the same two vertices left in the resulting graph, but only with mutually distinct labels.
• If the kernel's edge operation in me_kernel.e_op specifies a reduction through the me_kernel.e_op.reduction field but with a NULL destructor field in me_kernel.e_op.r_free, then a default scalar edge label ordering is inferred in the me_orders.e_order field.

ERRORS

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.

The me_classifier field and the me_kernel.v_op field must be both initialized or both zero-filled, because either is useless without the other. If only one is initialized, then the cru_merged function reports an error of CRU_INCMRG, for a conflicting merge specification.

NOTES

An edge order associated with a given graph is necessary for merging it, but need not be defined for the resulting graph in the me_orders field. However, the edge ordering is necessary for further merging of the result, as well as for composition, deduplication, postponement, and stretching it. If any of these operations is anticipated after merging, applications should define an edge ordering.

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_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