NAME

cru_filter - specification for selectively removing edges and vertices

SYNOPSIS

#include <cru/cru.h>

typedef struct cru_filter_s
{
   cru_qpred thinner;
   struct cru_zone_s fi_zone;
   struct cru_kernel_s fi_kernel;
   struct cru_order_s fi_order;
} *cru_filter;

DESCRIPTION

This structure parameterizes the cru_filtered library function with necessary information initialized by the application to remove edges or vertices from a graph selectively based on user-defined criteria. Activities can be restricted to a section of the graph by the cru_zone structure in the fi_zone field. Alternatively, the fi_zone field may be omitted or zero-filled, in which case the whole graph is affected.

For each vertex in the graph, a test property is evaluated according to the structure given by fi_kernel.v_op field with the usual cru_prop calling conventions if one is specified. The interpretation of the test result differs depending on whether the thinner field is specified. The thinner field, if non-NULL, provides further edge filtering functionality explained below following an explanation of the simpler case where the thinner field is NULL. In this case, vertices are kept or removed on this basis:

• The results of a fold over each of the incoming and the outgoing sets of edges, if defined respectively in the fi_kernel.v_op.incident or fi_kernel.v_op.outgoing structures, are passed respectively as the left and right operands to the ternary operator referenced by the fi_kernel.v_op.vertex.map field if one is specified, with the vertex being visited passed as the middle operand.
• If a ternary operator referenced by the fi_kernel.v_op.vertex.map field returns NULL, then the vertex being visited is deleted from the graph. If it returns any other value, the vertex is kept.
• If the fi_kernel.v_op.vertex.map field is omitted or NULL but at least one of the incident or outgoing fold structures is specified, then the criterion for vertex retention devolves to the disjunction of their results. That is, if either yields a result other than NULL, then the vertex is kept.
• If neither the vertex map nor the folds are defined, then no vertices are filtered directly, but may be removed if they become unreachable due to edge filtering.
• The fi_kernel.v_op.vertex.reduction field and the fi_kernel.v_op.vertex.vacuous_case field are not used and may be omitted or initialized to NULL.

With regard to edge filtering, if the thinner field is NULL and the fi_kernel.e_op.map field is not, then edges are kept or removed on this basis:

• When each vertex in the graph is visited, if a decision to keep it is made as described above, then each of its outgoing edges connected to a vertex that is also being kept is tested.
• For each edge being tested, the ternary operator referenced through the fi_kernel.e_op.map field is passed the vertex being visited as the left operand, the edge label as its middle operand, and the adjacent vertex via that edge as the right operand.

What happens next depends on whether an ordering is defined by the cru_order structure in the fi_order field or whether the field is zero-filled.

• If no ordering is defined, then each edge being tested is deleted whenever the fi_kernel.e_op.map operator returns NULL.
• If an ordering is defined in the fi_order field, then the edges local to the vertex being visited are partitioned into classes based on equivalence of their labels under the ordering, and each class is reduced with the fi_kernel.e_op.reduction field following the usual cru_fold calling conventions. If the result of the reduction is NULL, then all edges in the class are deleted. Otherwise, all are kept.

If the fi_kernel.e_op.map field is NULL, then no edges are filtered directly but may be deleted as a consequence of being connected to a deleted vertex.

The remainder of this section pertains to filtering when the thinner field refers to a user-defined quarternary predicate.

If the thinner field is defined (i.e., non-NULL), then no vertices are deleted unless they become unreachable. However, the vertices are still tested by the fi_kernel.v_op probe in the same way as above if it is defined. The test result or lack thereof indicates only whether any outgoing edges from the tested vertex should be deleted.

• If a fi_kernel.v_op probe is specifed and its test result is non-NULL, then no outgoing edges from the tested vertex are deleted.
• If the vertex probe is not specified or its test result is NULL, and if no fold is specified in the fi_kernel.e_op field, all outgoing edges from the vertex being tested are admitted for consideration as described below.
• If the vertex probe is not specified or its test result is NULL, and if a map is is specified in the fi_kernel.e_op.map field but no reduction is specified in the fi_kernel.e_op.reduction field, then all outgoing edges from the vertex being tested for which the map returns NULL are deleted, and the surviving ones are admitted for consideration as described below.
• If the probe is not specified or its test result is NULL, and an ordering is defined in the fi_order field, and both the fi_kernel.e_op.map field and the fi_kernel.e_op.reduction field are specified, then the outgoing edges from the vertex being tested are partitioned into equivalence classes based on the ordering and each class as a whole is deleted or kept depending on the result of the reduction over that class.

The set of edges or the set of classes of edges obtained as above is then filtered further according to the thinner predicate as follows.

• If the edges have been partitioned into classes, all members of the minimum class with respect to the predicate are kept, and all members of any other classes are deleted.
• If the edges have not been partitioned into classes, only the single minimum edge with respect to the predicate is kept, and all other outgoing edges from the vertex being tested are deleted.

To this end, the application should initialize the thinner field to refer to a relational predicate on edges with the desired effect. That is, it should be antisymmetric and it should return a non-zero value whenever its left operand is preferable to be kept in the graph. As a quarternary predicate, its four operands are an edge label, the terminal vertex of the edge thus labeled, another edge label, and the latter edge's terminus in that order. As always, the predicate must not modify its operands but may assign the error code.

ERRORS

If an ordering is defined by the fi_order field but no edge filter is defined by fi_kernel.e_op field, then an error of CRU_INCFIL is reported by the cru_filtered function, for an inconsistent cru_filter structure.

If an ordering is specified by the fi_kernel.e_order field and a thinner is also specified, then the thinner should be defined consistently with the ordering insofar as equivalent edges under the ordering are also equivalent with respect to the thinner. This condition is necessary because comparison of classes is based on comparison of arbitrarily selected members of the classes. This condition is not enforceable by cru but failure to meet it may lead to non-deterministic results.

EXAMPLES

This function

uintptr_t
even (void *l, uintptr_t vertex, void *r, int *err)
{
   return ! (vertex & 1);
}

in this cru_filter

struct cru_filter_s f = {
   .fi_kernel = {
      .v_op = {
         .vertex = {
            .map = (cru_top) even}}}};

calls for the retention of even numbered vertices in a graph of numerical vertices and the removal of all others, whereas this cru_filter

struct cru_filter_s f = {
   .fi_kernel = {
      .e_op = {
         .map = (cru_top) even}}};

specifies the removal of odd-numbered edges in a graph whose edges are numerically labeled.

NOTES

It is not impossible for vertices outside of a zone of the graph restricted by the fi_zone to be affected by filtering within the zone.

• If the zone is defined as the reachable segment in the backward direction from an initial vertex, and edges originating inside the zone but terminating outside it are deleted, then their termini could become unreachable and therefore deleted despite being outside the zone.
• If the zone is defined as the reachable segment in the forward direction from an initial vertex, then edges originating outside the zone but terminating inside it could be deleted due to their termini being deleted, thereby reducing the number of outgoing edges seen by vertex outside the zone.

A cru_filter structure specifying only a thinner field is valid, and calls for all edges except the minimum outgoing edge from each vertex to be deleted.

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