Spatial Graphs

Table of Contents

• Background
• Assumptions
  • Vicinity
  • Bounding policy
  • Directionality
• Example

Note

The objective of this section is to understand the concepts and assumptions required to define the modality of dispersal of a species across a landscape. Because dispersal is so tightly related to graph connectivity and performance, this will require to:

1. transform a quetzal::geography::landscape into a quetzal::geography::graph.
2. select the desired assumptions to control the level of connectivity in the graph.

1. understand how assumptions define the number of edges in the resulting spatial graph.

Background

The challenge of replicating a demographic process within a discrete landscape can be framed as a process on a spatial graph. In this graph, the vertices represent the cells of the landscape grid, while the edges link the areas where migration occurs.

The quantity of edges in this graph significantly influences both complexity and performance. For instance, in a landscape containing \(n\) cells, considering migration between any two arbitrary locations would result in a complete graph with \(\frac{n(n-1)}{2}\) edges, which could pose computational difficulties. A number of alternative assumptions can be made to control the computational feasibility.

All these choices are independently represented in the code and can be extended (although that may require some efforts).

Assumptions

Vicinity

Constructing a spatial graph first requires to account for the modality of dispersal between the vertices (locations) of the graph. That is, from one source vertex, define which vertices can be targeted: this is the concept of vicinity, or neighborhood.

We distinguish at least 3 modalities:

• connect_4_neighbors: each cell of the landscape grid is connected only to its cardinal neighbors (N, E, S, W).
• connect_8_neighbors: each cell of the landscape grid is connected only to its cardinal (N, E, S, W) and intercardinal (NE, SE, SW, NW) neighbors.
• connect_fully: each cell of the landscape grid is connected to all others: the graph is complete.

Bounding policy

Similarly, assumptions we make about the model's behavior at the bounds of the finite landscape influence the connectivity of the graph. We distinguish at least three bounding modalities:

• mirror: cells at the borders of the landscape are connected to their neighbors, without any further modification. In this case the individuals moving between cells will be reflected into the landscape.
• sink: cells at the borders of the landscape will be connected to a sink vertex: individuals that migrate past the boundaries of the landscape escape into the world and never come back.
• torus: the 2D landscape becomes a 3D torus world, as vertices on opposite borders are linked to their symmetric vertex: individuals that cross the Northern (resp. Western) border reappear on the Southern (resp. Eastern) border.

Directionality

Finally, a last assumption we make about the population process that impacts the graph representation is the directionality of the process:

• isotropy: the migration process is independent of the direction of movement. Moving from vertex \(u\) to \(v\) follows the same rules as moving from \(v\) to \(u\): the edge \(( u,v)\) is the same as \((v,u)\).
• anisotropy migration will distinguish between \(( u,v)\) and \((v,u)\), doubling the number of edges in the graph.

Example

Input

#include "quetzal/geography.hpp"
 
#include <cassert>
#include <filesystem>
#include <ranges>
 
namespace geo = quetzal::geography;
 
int main()
{
    auto file1 = std::filesystem::current_path() / "data/bio1.tif";
    auto file2 = std::filesystem::current_path() / "data/bio12.tif";
 
    // The raster have 10 bands that we will assign to 2001 ... 2010.
    std::vector<int> times(10);
    std::iota(times.begin(), times.end(), 2001);
 
    // Initialize the landscape: for each var a key and a file, for all a time series.
    using landscape_type = geo::landscape<>;
    auto land = landscape_type::from_file({{"bio1", file1}, {"bio12", file2}}, times);
 
    // Our graph will not store any useful information
    using vertex_info = geo::no_property;
    using edge_info = geo::no_property;
 
    // Few of the possible assumptions combinations
    auto graph1 = geo::from_grid(land, vertex_info(), edge_info(), geo::connect_fully(), geo::isotropy(), geo::mirror());
    auto graph2 = geo::from_grid(land, vertex_info(), edge_info(), geo::connect_4_neighbors(), geo::isotropy(), geo::sink());
    auto graph3 = geo::from_grid(land, vertex_info(), edge_info(), geo::connect_8_neighbors(), geo::anisotropy(), geo::torus());
 
    std::cout << "Graph 1 has " << graph1.num_vertices() << " vertices, " << graph1.num_edges() << " edges." << std::endl;
    std::cout << "Graph 2 has " << graph2.num_vertices() << " vertices, " << graph2.num_edges() << " edges." << std::endl;
    std::cout << "Graph 3 has " << graph3.num_vertices() << " vertices, " << graph3.num_edges() << " edges." << std::endl;
}

Output

Graph 1 has 9 vertices, 36 edges.
Graph 2 has 10 vertices, 20 edges.
Graph 3 has 9 vertices, 48 edges.

---