For using the igraph C library
typedef enum {
IGRAPH_METRIC_EUCLIDEAN = 0,
IGRAPH_METRIC_L2 = IGRAPH_METRIC_EUCLIDEAN,
IGRAPH_METRIC_MANHATTAN = 1,
IGRAPH_METRIC_L1 = IGRAPH_METRIC_MANHATTAN
} igraph_metric_t;
Values:
|
The Euclidean distance, i.e. L2 metric. |
|
The Manhattan distance, i.e. L1 metric. |
igraph_error_t igraph_delaunay_graph(igraph_t *graph, const igraph_matrix_t *points);
This function is experimental and its signature is not considered final yet. We reserve the right to change the function signature without changing the major version of igraph. Use it at your own risk.
This function constructs the graph corresponding to the Delaunay triangulation of an n-dimensional spatial point set.
The current implementation uses Qhull.
Reference:
Barber, C. Bradford, David P. Dobkin, and Hannu Huhdanpaa. The Quickhull Algorithm for Convex Hulls. ACM Transactions on Mathematical Software 22, no. 4 (1996): 469–83. https://doi.org/10.1145/235815.235821.
Arguments:
|
A pointer to the graph that will be created. |
|
A matrix containing the points that will be used to create the graph. Each row is a point, dimensionality is inferred from the column count. There must not be duplicate points. |
Returns:
Error code. |
Time complexity: According to Theorem 3.2 in the Qhull paper, O(n log n) for d <= 3 and O(n^floor(d/2) / floor(d/2)!) where n is the number of points and d is the dimensionality of the point set.
igraph_error_t igraph_nearest_neighbor_graph(igraph_t *graph,
const igraph_matrix_t *points,
igraph_metric_t metric,
igraph_int_t k,
igraph_real_t cutoff,
igraph_bool_t directed);
This function constructs the k nearest neighbor graph of a given point
set. Each point is connected to at most k spatial neighbors within a
radius of cutoff.
Arguments:
|
A pointer to the graph that will be created. |
|
A matrix containing the points that will be used to create the graph. Each row is a point, dimensionality is inferred from the column count. |
|
The distance metric to use. See |
|
At most how many neighbors will be added for each vertex, set to a negative value to ignore. |
|
Maximum distance at which connections will be made, set to a
negative value or |
|
Whether to create a directed graph. |
Returns:
Error code. |
Time complexity: O(n log(n)) where n is the number of points.
igraph_error_t igraph_spatial_edge_lengths(
const igraph_t *graph,
igraph_vector_t *lengths,
const igraph_matrix_t *points,
igraph_metric_t metric);
This function is experimental and its signature is not considered final yet. We reserve the right to change the function signature without changing the major version of igraph. Use it at your own risk.
The length of each edge is computed based on spatial coordinates. The length
can be employed by several igraph functions, such as igraph_voronoi(),
igraph_betweenness(), igraph_closeness() and others.
Arguments:
|
The graph whose edge lengths are to be computed. |
|
An initialized vector. Length will be stored here, in the order of edge IDs. It will be resized as needed. |
|
A matrix of vertex coordinates. Each row contains the coordinates of the corresponding vertex, in the order of vertex IDs. Arbitrary dimensional point sets are supported. |
|
The distance metric to use. See |
Returns:
Error code. |
See also:
|
Time complexity: O(|E| d) where |E| is the number of edges and d is the dimensionality of the point set.
igraph_error_t igraph_convex_hull_2d(
const igraph_matrix_t *data,
igraph_vector_int_t *resverts,
igraph_matrix_t *rescoords);
The convex hull is determined by the Graham scan algorithm. See the following reference for details:
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Pages 949-955 of section 33.3: Finding the convex hull.
Arguments:
|
vector containing the coordinates. The length of the vector must be even, since it contains X-Y coordinate pairs. |
|
the vector containing the result, e.g. the vector of
vertex indices used as the corners of the convex hull. Supply
|
|
the matrix containing the coordinates of the selected
corner vertices. Supply |
Returns:
Error code:
|
Time complexity: O(n log(n)) where n is the number of vertices.
| ← Chapter 13. Bipartite, i.e. two-mode graphs | Chapter 15. Graph operators → |