NAME

cru_data_types - data types defined and used by the cru library

SYNOPSIS

#include <cru/cru.h>

DESCRIPTION

To simplify the API, many parameters to cru functions are encapsulated by nested C structures adhering where possible to consistent and memorable naming conventions. While the functions remain extensively configurable, they can also infer fixed default values for infrequently used fields initialized by the application to zero or NULL in these structures. Applications can conveniently omit these fields in some anticipated common use cases by leveraging C99 style designated initializers. Here are some of the naming conventions.

• All public API type aliases and struct names are prefixed by "cru_" to avoid clashes with other symbols compiled along with the application.
• Any struct name of the form foo_s defined in the header files has a corresponding type alias foo for pointers to that type of structure.
• When an API function is described in this manual as being parameterized by a structure, the formal parameter is always a pointer to the structure.
• Any type alias of the form foo_pair denotes a pointer to a structure of type struct foo_pair_s having exactly two identically typed fields. If foo is a type alias for a pointer to a function, then the fields are of that type. Otherwise, the fields are of type struct foo_s.
• Any type alias of the form foo_quad is a pointer to a structure of type struct foo_quad_s having exactly two fields, both of type struct foo_pair_s.
• Type aliases of the form cru_cxop where x is b, t, or q, generalize binary, ternary, or quarternary operators respectively to conditional versions applicable only if some predicate holds. The structure referenced in each case has field identifiers xop and xpred referring respectively to an operator of type cru_xop and a predicate of type cru_xpred both taking arguments of the same types.
• The name of any function returning a graph and the name of the structure parameterizing it are derived from the same root word. In grammatical terms, the function name is a past participle describing the function's effect on the graph and the structure name is the noun that designates a creator of that effect.

The two type aliases cru_edge and cru_vertex are provided in the header files for void pointers. They are intended to be used optionally for improved readability in application code as type casts where appropriate. They refer respectively to edge labels and vertices in a graph.

Four more type aliases specify only a pointer in the header files with no explicit specification of the corresponding struct. These types are meant to be treated as opaque by applications, obtained only as the returned values of API functions and useful only as parameters to other API functions. The opaque types and their short descriptions are

cru_graph

encapsulation of all components in a graph, its destructors, and its relations

cru_kill_switch

trigger for early return from an API function

cru_partition

representation of a set of subsets of the vertices in a graph

cru_class

representation of an individual subset in a partition.

The remaining types can be broadly classified as base types, derived types, and top level types.

• Fields in the base type structures are limited to scalar values, pointers to functions, and cru_vertex pointers.
• Fields in the derived type structures may be base type structures, conditional operators, or other derived type structures.
• Top level structures contain any of the above and they directly parameterize the API functions.

The base types are

cru_order

the combination of an equality relation and a hash function for a vertex, edge, or property, as part of a cru_order_pair, a cru_classifier, or a cru_filter

cru_destructor_pair

one destructor for the vertices in a graph and one for the edge labels as part of a cru_sig

cru_fold

a specification for a two-stage computation taking some set of operands to an individual result as part of a cru_prop, a cru_inducer, or a cru_kernel

cru_zone

a constraint on the starting point and the direction of a graph traversal as part of a cru_plan, a cru_mapreducer, a cru_inducer, or a cru_filter.

The derived types are

cru_plan

a constraint on not only the zone but the order of a graph traversal as part of a cru_mutator

cru_prop

a specification for deriving a property of a vertex depending on its environment as part of a cru_prop_pair, a cru_kernel, a cru_mapreducer, a cru_stretcher, a cru_splitter, or a cru_classifier

cru_kernel

a combination of a property over the vertices and a fold over the edges in a graph as part of a cru_mutator, a cru_merger, or a cru_filter

cru_prop_pair

one property for the initial and one for the intermediate vertex in a composition operation as part of a cru_composer

cru_order_pair

one order for the vertices and one for the edges in a graph as part of a cru_sig or a cru_mutator

cru_ctop_pair

two potential ways to derive an edge label from a given one and its environment as part of a cru_ctop_quad

cru_ctop_quad

a pair of conditional ternary operator pairs, one for incoming and one for outgoing edges, as part of a cru_splitter

cru_sig

a combined specification of both the orders and the destructors of a graph, as part of a cru_builder, a cru_crosser, or a cru_fabricator.

The remaining types, which are the top level types as noted above, adhere to additional naming conventions for field identifiers. For any top level type cru_foo listed below,

• any field of type struct cru_bar_pair_s or struct cru_bar_quad_s has a field identifier of the form fo_bars
• and any field of any other type struct cru_baz_s corresponding to a type alias listed above has a field identifier of fo_baz.

That is, the field identifier consists of a two letter prefix determined by the top level type alias followed by a suffix determined by the derived type alias, with a plural form for pairs and quadruples. Fields of types not listed above have descriptive identifiers following no standard convention.

Each top level data type corresponds to a similarly named API function having a parameter of that type. They can be categorized as pertaining to graph building, analysis, classification, contraction, and surgery. For building, these three data types specify ways of building a graph from scratch, creating a modified copy of an existing graph, and building a new graph from a pair of graphs.

• cru_builder
• cru_fabricator
• cru_crosser

For analysis, these two data types specify a simple and a more sophisticated way of computing statistics or metrics about a graph.

• cru_mapreducer
• cru_inducer

For classification, this data type describes a way of partitioning a graph into subsets of related vertices.

• cru_classifier

For expansion, these three data type specify ways of inserting additional edges or vertices into a graph.

• cru_stretcher
• cru_splitter
• cru_composer

For contraction, these two data types specify a way of reducing groups of related vertices into single vertices, and a way of selectively removing vertices or edges.

• cru_merger
• cru_filter

For surgery, these two data types describe ways of overwriting vertices or edges in place, or transplanting an edge to a nearby location.

• cru_mutator
• cru_postponer

EXAMPLES

Following the grammatical convention noted above:

• The function that returns a newly built graph, cru_built, is parameterized by a cru_builder.
• A pointer of type cru_builder points to a structure of type struct cru_builder_s.

Pairs can be pairs of structures or pairs of pointers to functions.

• A pointer of type cru_order_pair points to a structure having two fields each of type struct cru_order_s.
• A pointer of type cru_destructor_pair points to a structure having two fields of type cru_destructor, which are pointers to functions.

Conditional operators are named as shown.

• A pointer of type cru_cbop points to a structure of type struct cru_cbop_s having a field named bop of type cru_bop and a field named bpred of type cru_bpred.
• The others are cru_ctop and cru_cqop.

Identifiers for fields of derived types in top level structures are predictable from their types.

• The field of type struct cru_fold_s in a cru_inducer structure has a field identifier of in_fold.
• The field of type struct cru_prop_pair_s in a cru_composer structure has a field identifier of co_props. Note the plural.

NOTES

Suffixing struct names with "_s" was not strictly necessary as an API design choice because type names and struct names inhabit separate name spaces according to C standards, and therefore may coincide without ambiguity. The additional redundancy is intended to help compilers flag certain common errors.

Distinct field identifiers across multiple structures are similarly beneficial though not required by C standards. Their naming convention is meant to afford a desirable redundancy while avoiding a proliferation of gratuitous differences.

FILES

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

/usr/local/include/cru/function_types.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_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