Ngraph

A neighborhood graph defines a neighborhood relation among a set of SObjects. It creates Adjacencies for this relation. Operations create a neighborhood graph for a space and return the neighbors or adjacencies of a given SObject. Subclasses:

Implementations:

Ngraph_Best
An object's neighbors are its best (or worst, given a flag) neighbors from a base ngraph, according to a user-specified metric function.
Constructor args: best metric function, bool worst?.
Ngraph_Boolean
An object's neighbors are those objects that pass a user-specified test.
Constructor args: test function.
Ngraph_Closure
An object's neighbors are the n-fold closure of its neighbors in a base ngraph.
Constructor args: int n.
Ngraph_Combination
An object's adjacencies are the union/intersection/difference of those in a set of base ngraphs.
Constructor args: union/intersection/difference?.
Ngraph_Explicit
An object's neighbors are given by a user-specified function or by explicit add/remove calls.
Constructor args: neighborhood function.
Ngraph_Filter
An object's adjacencies are those in a base ngraph that pass a test.
Constructor args: adjacency predicate.
Ngraph_Inverse
An object's adjacencies are in the opposite direction from those in a base ngraph.
Ngraph_K_Nearest
An object's neighbors are the closest k objects within some radius.
Constructor args: double radius, int k.
Ngraph_Mesh_Dual
A mesh ngraph encodes adjacencies among neighboring mesh elements (e.g. triangles). For example, for the Delaunay mesh, the mesh ngraph is the Voronoi graph.
Ngraph_Near
An object's neighbors are all objects within some radius.
Constructor args: double radius.
Ngraph_Reachable
The ngraph's adjacencies are those reachable in a base ngraph from a given set of objects within a given set of steps.
Constructor args: Space from, int radius.
Ngraph_Subgraph
The ngraph's adjacencies are those in a base ngraph or passing involving a set of objects explicitly specified or implicitly specified by a function.
Constructor args: Space nodes or test function.
Ngraph_Substructure
An object's neighbors are the neighbors of any of its constituent objects in another ngraph.
Constructor args: Ngraph for constituent objects, Abstractor.
Ngraph_Symmetric
The ngraph's adjacencies either are those in a base ngraph that are undirected, or are extended from a base ngraph to be undirected.
Constructor args: subgraph/extended-graph?.

Member functions:

adjacencies: Ngraph . SObject -> Adjacencies
Returns the adjacencies from the object.
adjacency: Ngraph . SObject . SObject -> Adjacency
Returns the adjacency from the first object to the secon, if it exists.
aggregate: Ngraph . Space -> void
Builds the ngraph for the space.
derive: Ngraph -> void
Derives another ngraph from the given ngraph.
is_neighbor: Ngraph . SObject . SObject -> bool
Tests if two sobjects are adjacent in the ngraph.
space: Ngraph -> Space
Returns the space for which the ngraph was built.
neighbors: Ngraph . SObject -> Space
Returns the space containing the neighbors of the object.

Secondary operations:

search_dfs_to_goal: Ngraph . Paths start . (SObject->bool) good . SObjects finish . Paths answers -> void
Starting from the initial paths, expands depth-first through nodes satisfying the predicate until reaching a goal. Stores answer paths in the final container. A path is a sequence of objects.
search_dfs_to_depth : Ngraph . Paths start . (SObject->bool) . int depth . int which_paths . Paths -> void
Starting from the initial paths, expands depth-first through nodes satisfying the predicate until reaching depth. Stores answer paths in the final container. A path is a sequence of objects. If which_paths is 0, answer paths must be of the given length; if it is 1, they are the longest paths up to the given length; if it is 2, they are all paths no longer than the given length.