NAME

cru_crosser - specification for a product of two graphs

SYNOPSIS

#include <cru/cru.h>

typedef struct cru_crosser_s
{
   cru_bop v_prod;
   struct cru_sig_s cr_sig;
   struct cru_cbop_s e_prod;
} *cru_crosser;

DESCRIPTION

This structure parameterizes the cru_crossed library function with necessary information initialized by the application to create a new graph from a combination of two given graphs. The v_prod operator takes a pair of vertices, one from each graph, and is expected to return a combined vertex corresponding to them to be included in the product graph. If both input graphs are non-empty, then the product graph always contains at least the vertex obtained from their initial vertices. The e_prod conditional binary operator is applied as follows.

• For each pair of vertices from which a vertex is known to have been obtained by the v_prod operator in the product graph, all pairs of their existing outgoing edges are constructed such that each pair of edges contains one edge from each vertex of the pair.
• For each pair of edges thus constructed, the predicate referenced through the e_prod.bpred field of the conditional binary operator is called with their labels as its operands.
• If the predicate returns zero, no action is taken, but if it returns any non-zero value, then the same pair of edge labels is passed as operands to the binary operator referenced through the e_prod.bop field.
• The value returned by the binary operator is taken as the label on an edge to be included in the product graph. This edge is made to originate from the vertex obtained by the v_prod operator from the origins of the pair of edges.
• The termini of the pair of edges are passed to the v_prod operator to construct the terminus to be included in the product graph of the edge created from the pair of edges.
• The outgoing edges from the termini are used to generate more pairs of edge labels as above for this process to continue until it yields no futher unique vertices or the graph's vertex limit as given by the cr_sig.vertex_limit field is reached.

The predicate field e_prod.bpred in the conditional binary operator can be initialized as NULL, in which case the operator referenced through the e_prod.bop field is invoked unconditionally.

Because the product graph types differ in general from those of the input graphs, the cr_sig field enables the application to associate the relevant orderings and destructors with it.

ERRORS

These errors are reportable for the following reasons by the cru_crossed function given an invalid cru_crosser structure.

CRU_UNDVPR

No vertex product operator is defined.

CRU_UNDEPR

No edge product operator is defined.

NOTES

Graph products are memory intensive because they need memory for both input graphs and the result simultaneously. Moreover, the space needed for the result is proportional in the worst case to the product of the amounts of space needed for each input. Algorithms making use of this operation might benefit from shared representations of vertices and edges at the cost of a user-defined reference counting scheme ensuring thread-safe copying and reclamation.

If the product operators are non-injective, for example by mapping distinct pairs of input vertices to identical output vertices, then it is possible for the product graph to contain duplicate vertices or labels. This situation can be remedied by passing the result returned by cru_crossed through the cru_deduplicated library function, provided the cr_sig field is correctly initialized. As a performance tradeoff, this step is not taken automatically because an application developer in the unusual case of non-injective operators can discern its necessity and plan accordingly.

FILES

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

/usr/local/include/cru/function_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_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_united, cru_uop, cru_vertex_count, cru_zone

AUTHOR

Dennis Furey (milonga@delayinsensitive.com)

PROJECT PAGE

https://github.com/gueststar/cru