cru_zone - specification of a connected region of a graph
#include <cru/cru.h>
typedef struct
cru_zone_s
{
int
offset;
cru_vertex
initial_vertex;
int
backwards;
} *cru_zone;
This structure specifies the connected region of some existing graph reachable by traversing any path starting from some initial vertex. When initialized by an application and passed to certain cru API functions, it instructs them to operate only on that region instead of the whole graph.
Zones can be oriented backwards or forward. If the backwards field is non-zero, then the zone is oriented backwards. Otherwise, it is oriented forward. A backwards oriented zone consists of all vertices from which the initial vertex is reachable, whereas a forward oriented zone consists of all vertices reachable from the initial vertex.
If the zone consists of the whole graph because no initial vertex is specified, and if the backwards field is non-zero, and if the initial vertex has no incident edges, then only the initial vertex is visited and the operation completes in constant time.
If the offset is non-zero but the initial_vertex is not in the graph passed to the API function along with this zone, then the function reports the error CRU_PARVNF for a vertex not found.
If the zone covers less than the full graph and is to be used in the course of a mutation that changes the vertices or edges to a type requiring a different destructor than the original, then the API function reports an error of CRU_TPCMUT, meaning the operation is disallowed because it would make the graph impossible to reclaim.
Restriction to a zone is supported only for mapreduction, induction, filtering and mutation operations. The cru_zone structure accordingly is part of the cru_mapreducer, cru_inducer, and cru_filter top level structures, and the cru_mutator top level structure by way of its cru_plan.
In the typical case of operating on a whole graph, the application initializes the zone to all zeros, or simply omits mention of it if the structure is declared using C99 designated initializers.
Designating an initial vertex via this structure requires the graph to be searched for it, an asymptotically linear time operation in the number of vertices, before anything else can be done. The search may require the evaluation of equality relations and hash functions associated with the graph. However, time operating on the graph subsequently may be saved if the region is significantly smaller than the whole graph.
/usr/local/include/cru/data_types.h
/usr/local/include/cru/error_codes.h
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_united, cru_uop, cru_vertex_count, cru_zone
Dennis Furey (milonga@delayinsensitive.com)
https://github.com/gueststar/cru