NAME

cru_united - merge two equivalence classes in a partition

SYNOPSIS

#include <cru/cru.h>

int cru_united (
   cru_partition p ,
   cru_class x ,
   cru_class y ,
   int *err )

DESCRIPTION

This function is part of a simple and efficient API for manipulating sets of vertices in a graph. Given a partition p previously obtained by the cru_partition_of function, and two classes x and y in p previously obtained by the cru_class_of function, this function modifies the partition in place such that the classes x and y are merged and consumed. That is, any members of either class x or y prior to this invocation become members of the same class subsequently according to the cru_class_of function. If x and y are identical beforehand and the operation completes successfully, it has no effect.

RETURN VALUE

On successful completion, this function returns a non-zero value. Otherwise, it returns zero.

ERRORS

Effects are undefined if either of x or y is not associated with the partition p. For reasons of performance and space efficiency, this error is not detected. It is also an undetected error for an application to make any further reference to either x or y after it is passed to cru_united, as in this example of bad practice.

x = cru_class_of (p, v, err);
cru_united (p, x, y, err);
if (x == cru_class_of (p, v, err))   // unpredictable
   printf ("lucky\n");
else                                 // class may have changed
   printf ("unlucky\n");

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. Positive numbers are for POSIX or user-defined error codes, and negative numbers down to -CRU_MAX_ERR are specific to cru.

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 or invalid usage of the API.

CRU_NULCLS

Either of x or y is NULL rather than a valid cru_class pointer.

CRU_BADCLS

Either of x or y refers to an invalid or corrupted cru_class structure.

CRU_NULPRT

The parameter p is NULL rather than a valid cru_partition pointer.

CRU_BADPRT

The parameter p refers to an invalid or corrupted cru_partition structure.

EXAMPLE

Assume a cru_graph g has mutually unrelated vertices u, v, and w according to a cru_classifier c, and that p is declared as a cru_partition.

p = cru_partition_of (g, c, UNKILLABLE, CONCURRENTLY, err);
if (cru_class_of (p, u, err) != cru_class_of (p, v, err))
   if (cru_class_of (p, v, err) != cru_class_of (p, w, err))
      if (cru_class_of (p, w, err) != cru_class_of (p, u, err))
         printf ("vertices are mutually unrelated as assumed\n");
cru_united(p, cru_class_of(p, u, err), cru_class_of(p, v, err), err);
cru_united(p, cru_class_of(p, v, err), cru_class_of(p, w, err), err);
if (cru_class_of (p, u, err) == cru_class_of (p, v, err))
   if (cru_class_of (p, v, err) == cru_class_of (p, w, err))
      if (cru_class_of (p, w, err) == cru_class_of (p, u, err))
         printf ("cru_united worked as expected\n");

Note that u and w become members of the same class by transitivity.

NOTES

This operation takes amortized inverse Ackerman or near constant time.

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_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_uop, cru_vertex_count, cru_zone

AUTHOR

Dennis Furey (milonga@delayinsensitive.com)

PROJECT PAGE

https://github.com/gueststar/cru