File size: 4,422 Bytes
26225c5 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 |
/*=============================================================================
* Tools for manipulating nearest-neighbors graph defined on regular grids
*
* A grid graph in dimension D is defined by the following parameters:
* D - the number of dimensions
* shape - array of length D, giving the grid size in each dimension
* connectivity - defines the neighboring relationship;
* corresponds to the _square_ of the maximum Euclidean distance between
* two neighbors;
* if less than 4, it defines the number of coordinates allowed
* to simultaneously vary (+1 or -1) to define a neighbor; in that case,
* each level l of connectivity in dimension D adds binom(D, l)*2^l
* neighbors; corresponding number of neighbors for D = 2 and 3:
*
* connectivity | 1 2 3
* --------------------------
* 2D | 4 8 (8)
* 3D | 6 18 26
*
* note that a connectivity of 4 or more includes neighbors whose
* coordinates might differ by 2 or more from the coordinates of the
* considered vertex. Interestingly, in dimension 4 or more, including
* all surrounding vertices would then also include vertices from a "more
* distant" surround: the neighbor v + (2, 0, 0, 0) is at the same
* distance as the neighbor v + (1, 1, 1, 1).
*
* A graph with V vertices and E edges is represented either as edge list
* (array of E edges given as ordered pair of vertices), or as forward-star,
* where edges are numeroted so that all edges originating from a same vertex
* are consecutive, and represented by the following parameters:
* first_edge - array of length V + 1, indicating for each vertex, the first
* edge starting from the vertex (or, if there are none, starting from
* the next vertex); the first value is always zero and the last value is
* always the total number of edges
* adj_vertices - array of length E, indicating for each edge, its ending
* vertex
*
* Vertices of the grid are indexed in _column-major_ order, that is indices
* increase first along the first dimension specified in the 'shape' array
* (in the usual convention in 2D, this corresponds to columns), and then along
* the second dimension, and so on up to the last dimension.
* Indexing in _row-major_ order (indices increase first along the last
* dimension and so on up to the first) can be obtained by simply reverting
* the order of the grid dimensions in the shape array (in 2D, this amounts to
* transposition).
*
* Parallel implementation with OpenMP API
*
* Hugo Raguet 2019
*===========================================================================*/
#pragma once
#include <cstddef>
/* vertex_t is supposed to be an unsigned integer type able to hold the total
* number of _vertices_ of the manipulated graphs;
* edge_t is supposed to be an unsigned integer type able to hold the total
* number of _edges_ of the manipulated graphs */
/* compute the number of edges in the resulting graph */
template <typename vertex_t = unsigned int, typename conn_t = unsigned char>
size_t num_edges_grid_graph(size_t D, vertex_t* shape, conn_t connectivity);
/* compute the graph structure */
template <typename vertex_t = unsigned int, typename conn_t = unsigned char>
void edge_list_grid_graph(size_t D, vertex_t* shape, conn_t connectivity,
vertex_t* edges, conn_t* connectivities = nullptr,
vertex_t offset_u = 0, vertex_t offset_v = 0,
conn_t recursive_connectivity = 0, bool recursive_call = false);
/* edges is an array of length twice the number of edges, already allocated;
* connectivities is an array of length the number of edges, already allocated;
* the number of edges can be found using the num_edges_grid_graph function;
* connectivities are computed unless corresponding argument is null */
/* convert edge list to forward-star representation */
template <typename vertex_t = unsigned int, typename edge_t = vertex_t>
void edge_list_to_forward_star(vertex_t V, size_t E, const vertex_t* edges,
edge_t* first_edge, edge_t* reindex);
/* first_edge is an array of length V + 1, already allocated;
* reindex is the permutation indices so that all edges starting from a
* same vertex are consecutive, array of length E, already allocated;
* adj_vertices can be thus deduced from the edges by permuting the ending
* vertices according to reindex */
|