NAME

cru_deduplicated - fuse duplicate edges and vertices in a graph

SYNOPSIS

#include <cru/cru.h>

cru_graph cru_deduplicated (
   cru_graph g ,
   cru_kill_switch k ,
   unsigned lanes ,
   int *err )

DESCRIPTION

This function detects duplicate vertices and edges in a graph g according to the orderings specified at the time of its creation, and fuses the duplicates.

• If two different vertices in the given graph are identical according to the equality relation, then there is only one vertex identical to both of them in the result.
• Any outgoing edge from either of the original vertices becomes an outgoing edge from the resulting vertex, and any incoming edge to either vertex becomes an incoming edge to the result.
• Any two identically labeled edges in the same direction between the same two vertices are replaced by a single edge having that label.

The value passed through k may be either a cru_kill_switch previously obtained by the cru_new_kill_switch function or a NULL pointer denoted alternatively by UNKILLABLE. If code running in another thread passes the kill switch to cru_kill while the operation is in progress, then the operation is interrupted. In this case, the graph g is reclaimed.

The lanes parameter specifies the number of worker threads to be used for the operation. Higher numbers up to the number of CPU cores on the host are conducive to higher performance.

• A value of 0, denoted alternatively by CONCURRENTLY, requests a number of threads equal to the number of cores.
• A value of 1, denoted alternatively by SEQUENTIALLY, requests single threaded operation.

For purposes of memory management, the graph g is consumed by cru_deduplicated and must not be used or reclaimed subsequently by the caller.

RETURN VALUE

On successful completion, the returned value is a pointer to a graph derived from g by deduplicating it in place. Applications should treat the returned value as opaque but may pass it as a parameter to other library functions. In the event of any error, a NULL pointer is returned. A NULL pointer is also returned if the graph g is NULL, which in this case represents an empty graph and is not in itself an error.

ERRORS

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.

ENOMEM

There is insufficient memory to allocate all necessary resources.

EAGAIN

Resources or permissions are insufficient to create a thread.

CRU_BADGPH

The parameter g refers to an invalid or corrupted graph.

CRU_BADKIL

The parameter k refers to an invalid or corrupted kill switch structure.

CRU_INTKIL

The operation was stopped by user intervention using the kill switch k.

NOTES

Graphs built by the cru_built function necessarily have mutually distinct vertices but are allowed duplicate edge labels. Graphs with duplicate vertices may nevertheless result from the cru_mutated, cru_fabricated, and cru_crossed library functions depending on user-defined specifications. These graphs may benefit from deduplication.

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

AUTHOR

Dennis Furey (milonga@delayinsensitive.com)

PROJECT PAGE

https://github.com/gueststar/cru