graph-experiments

Description

Graph processing experiments based on boost::graph and GDAL / OGR to load data.

Motivation

This project is not maintained. It has been created in 2019 to prepare work about tour planning at IGNF.

Key Features

• src/egraph/routing/PathTree.h is using Boost Multi-Index to index (visited,cost) to optimize Dijkstra path finding.
• src/egraph/FeatureGraph.h is providing a Boost graph where vertex and edges are OGRFeature from GDAL

Build

• CMake - Building on debian or ubuntu
• CMake - Building with docker
• CMake - Building on windows with Microsoft Visual Studio (nmake) and miniconda

Examples

• example/demo-boost.cpp : Getting started with boost::graph
• example/demo-dijkstra.cpp : Shortest path computation
• example/demo-ogr.cpp : Load FeatureGraph using GDAL/OGR and compute some ShortestPathTree

example/demo-ogr "PG:dbname=gis" "graph.vertex" "graph.edge"
# or
example/demo-ogr "PG:dbname=gis" "graph.vertex" "graph.edge_distance_weighted"

Performance debug

valgrind --tool=callgrind example/demo-ogr 'PG:dbname=gis' 'graph.vertex' 'graph.edge_distance_weighted'
kcachegrind $(ls -tr callgrind.out.* | tail -1)

License

MIT