Construction

Table of Contents

• Background
• Graph from raster
• Graph from landscape
• Graph from abstract grid
• From scratch
  • Sparse Graph
  • Dense Graph

Background

Constructing a spatial graph from a spatial grid, also known as a raster, is a fundamental step in spatial analysis and modeling. Spatial graphs provide a powerful representation of relationships and connectivity between different locations within a geographic area. This process involves transforming the discrete and gridded structure of a spatial grid into a network of vertices and edges, where vertices represent spatial entities (such as cells or locations), and edges capture the spatial relationships and connections between these entities.

There are different ways to build such graph.

Graph from raster

The provided code snippet contains the logic for constructing a spatial graph from a quetzal::geography::raster.

This involves identifying the cells of the raster to map location_type values to the vertices, and defining edges based on the desired connectivity.

Input

#include "quetzal/geography.hpp"
 
#include <filesystem>
#include <ranges>
 
namespace geo = quetzal::geography;
 
int main()
{
    auto file = std::filesystem::current_path() / "data/bio1.tif";
 
    // The raster has 10 bands that we will assign to 2001 ... 2010.
    std::vector<int> times(10);
    std::iota(times.begin(), times.end(), 2001);
 
    // Initialize the landscape
    auto land = geo::raster<>::from_file(file, times);
 
    // Our graph will not store any useful information
    using vertex_info = geo::no_property;
    using edge_info = geo::no_property;
 
    auto graph = geo::from_grid(land, vertex_info(), edge_info(), geo::connect_fully(), geo::isotropy(), geo::mirror());
 
    std::cout << "Graph has " << graph.num_vertices() << " vertices, " << graph.num_edges() << " edges." << std::endl;
 
}

Output

Graph has 9 vertices, 36 edges.

Graph from landscape

In the parlance of quetzal, a quetzal::geography::landscape is just multiple aligned quetzal::geography::raster defined for different spatial quantities: since their grid structure are identical, the logic relating to spatial graph construction is unchanged. The provided code snippet contains the logic for constructing a spatial graph from a quetzal::geography::landscape.

This involves identifying the cells of the landscape to map location_type values to the vertices, and defining edges based on the desired connectivity.

Input

#include "quetzal/geography.hpp"
 
#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;
 
    auto graph = geo::from_grid(land, vertex_info(), edge_info(), geo::connect_fully(), geo::isotropy(), geo::mirror());
 
    std::cout << "Graph has " << graph.num_vertices() << " vertices, " << graph.num_edges() << " edges." << std::endl;
 
}

Output

Graph has 9 vertices, 36 edges.

Graph from abstract grid

The provided code snippet demonstrates how to construct a spatial graph from a user-defined abstract grid. This approach is useful when you either don't have or prefer not to use a geospatial file alongside your code, for example if you don't care about spatial quantities.

This involves identifying the height and width of the space to define linearly-indexed vertices, and defining edges based on the desired connectivity.

Input

#include "quetzal/geography.hpp"
 
namespace geo = quetzal::geography;
 
// User-defined concept of spatial grid
struct MySpatialGrid
{
    // it is just required to define these two functions
    constexpr int width() const { return 30; }
    constexpr int height() const { return 10; }
};
 
int main()
{
 
    static_assert(geo::two_dimensional<MySpatialGrid>, "MySpatialGrid does not fulfill the two_dimensional requirements");
    MySpatialGrid land;
 
    // Our graph will not store any useful information
    using vertex_info = geo::no_property;
    using edge_info = geo::no_property;
 
    auto graph = geo::from_grid(land, vertex_info(), edge_info(), geo::connect_fully(), geo::isotropy(), geo::mirror());
 
    std::cout << "Graph has " << graph.num_vertices() << " vertices, " << graph.num_edges() << " edges." << std::endl;
 
}

Output

Graph has 300 vertices, 44850 edges.

From scratch

The provided code snippet contains the logic for creating a sparse versus dense graph from scratch. This involves dynamically adding vertices and edges based on user-defined conditions, resulting in a graph that represents the desired spatial relationships.

Sparse Graph

Input

#include "quetzal/geography.hpp"
 
namespace geo = quetzal::geography;
 
int main()
{
    using vertex_info = geo::no_property;
    using edge_info = geo::no_property;
    using graph_type = geo::graph<vertex_info, edge_info, geo::sparse, geo::isotropy>;
 
    int num_vertices = 100;
    graph_type graph( num_vertices );
 
    graph.add_edge( 0, 1 );
    graph.add_edge( 0, 2 );
    graph.add_edge( 0, 3 );
    
    std::cout << "Graph has " << graph.num_vertices() << " vertices, " << graph.num_edges() << " edges." << std::endl;
 
}

Output

Graph has 100 vertices, 3 edges.

Dense Graph

Input

#include "quetzal/geography.hpp"
 
namespace geo = quetzal::geography;
 
int main()
{
    using vertex_info = geo::no_property;
    using edge_info = geo::no_property;
    using graph_type = geo::graph<vertex_info, edge_info, geo::dense, geo::anisotropy>;
 
    int num_vertices = 100;
    graph_type graph( num_vertices );
 
    graph.add_edge( 0, 1 );
    graph.add_edge( 0, 2 );
    graph.add_edge( 0, 3 );
    
    std::cout << "Graph has " << graph.num_vertices() << " vertices, " << graph.num_edges() << " edges." << std::endl;
 
}

Output

Graph has 100 vertices, 3 edges.

---