# flownet <img src='man/figures/logo.png' width="150px" align="right" />

<!-- badges: start -->
[![R-CMD-check](https://github.com/SebKrantz/flownet/actions/workflows/R-CMD-check.yaml/badge.svg)](https://github.com/SebKrantz/flownet/actions/workflows/R-CMD-check.yaml)
[![r-universe](https://sebkrantz.r-universe.dev/badges/flownet)](https://sebkrantz.r-universe.dev)
[![CRAN status](https://www.r-pkg.org/badges/version/flownet)](https://cran.r-project.org/package=flownet) 
[![cran checks](https://badges.cranchecks.info/worst/flownet.svg)](https://cran.r-project.org/web/checks/check_results_flownet.html)
![downloads per month](https://cranlogs.r-pkg.org/badges/flownet?color=blue)
![downloads](https://cranlogs.r-pkg.org/badges/grand-total/flownet?color=blue)
[![Codecov test coverage](https://codecov.io/gh/SebKrantz/flownet/graph/badge.svg)](https://app.codecov.io/gh/SebKrantz/flownet)
[![minimal R version](https://img.shields.io/badge/R%3E%3D-3.5.0-6666ff.svg)](https://cran.r-project.org/)
[![dependencies](https://tinyverse.netlify.app/badge/flownet)](https://CRAN.R-project.org/package=flownet)
<!-- badges: end -->

**Transport Modeling: Network Processing, Route Enumeration, and Traffic Assignment**

`flownet` provides efficient tools for transportation modeling in R, supporting network processing, route enumeration, and traffic assignment tasks. It implements the path-sized logit (PSL) model for traffic assignment and provides powerful utilities for network processing/preparation.

### Key Features

- **Path-Sized Logit Model**: Stochastic traffic assignment accounting for route overlap
- **Network Processing**: Convert LINESTRINGs to network graphs and consolidate/simplify them
- **Route Enumeration**: Efficient algorithm for finding alternative routes between origin-destination pairs
- **High Performance**: [fastverse](https://fastverse.org/fastverse/) packages and custom C implementations for critical path operations
- **Multithreading**: Asynchronous parallelism using [`mirai`](https://github.com/r-lib/mirai) for faster processing of large networks

## Installation

```r
# Install from CRAN
install.packages("flownet")

# Install development version from R-universe
install.packages("flownet", repos = c("https://sebkrantz.r-universe.dev", getOption("repos")))

```

### Dependencies

- `collapse` (>= 2.1.5) - Fast data transformations and memory efficient programming
- `kit` (>= 0.0.5) - Fast tabulation and vectorized switches
- `igraph` (>= 2.1.4) - Graph operations and shortest path algorithms
- `sf` (>= 1.0.0) - Spatial data handling
- `geodist` (>= 0.1.1) - Fast geodesic distance computations
- `leaderCluster` (>= 1.5.0) - Fast spatial clustering for network simplification
- `mirai` (>= 2.5.2) - Asynchronous parallelism for R
- `progress` (>= 1.2.3) - Progress bars for long-running operations

## Quick Start

Below I provide some boilerplate code. See also the [introductory vignette](https://sebkrantz.github.io/flownet/articles/introduction.html) for richer examples.

### Basic Usage

``` r
library(flownet)

# Create a small graph data frame
graph <- data.frame(from = c(1, 2, 2, 3),
                    to = c(2, 3, 4, 4), cost = c(5, 3, 2, 4))

# Prepare OD matrix with the same node IDs as in graph
od_matrix_long <- data.frame(from = c(1, 2, 3),
                             to = c(4, 4, 4), flow = c(100, 80, 60))

# Run traffic assignment (and route enumeration)
result <- run_assignment(graph, od_matrix_long, angle.max = NA)
#> Created graph with 4 nodes and 4 edges...
#> Computed distance matrix of dimensions 4 x 4 ...

# Access results
result$final_flows
#> [1] 100.00000  16.13649 196.13649  43.86351
```

### Working with Spatial Networks

```r
library(flownet)
library(sf)

# Read network from shapefile and create undirected graph (optional)
graph <- st_read("data/network.shp") |> 
  linestrings_to_graph() |>
  create_undirected_graph()

# Read zone centroids and get nearest nodes
od_zones <- st_read("data/od_zones.shp") |> st_centroid()
nodes <- nodes_from_graph(graph, sf = TRUE)
nearest_nodes <- nodes$node[st_nearest_feature(od_zones, nodes)]

# Consolidate Graph (optional)
graph <- consolidate_graph(graph, keep = nearest_nodes, w = ~ cost)

# Simplify network by keeping only traversed edges along shortest paths (optional)
# Use 'by' for multimodal networks to compute paths separately per mode
graph <- simplify_network(graph, nearest_nodes, cost.column = "cost", by = ~ mode)
```

### Example Workflow

```r
library(fastverse)
fastverse_extend(flownet, sf, mapview)

# 1. Load network and OD zone nodes
network <- st_read("data/network.shp")
od_zones <- st_read("data/od_zones.shp") |> st_centroid()
od_matrix <- fread("data/od_container_flows.csv") |> qM(1)
if(!all(dim(od_matrix) == nrow(od_zones))) stop("zones and OD matrix must match")

# 2. Convert network to graph
graph <- network |>
  linestrings_to_graph() |>
  create_undirected_graph()

# 3. Map zones to nearest network nodes
nodes <- nodes_from_graph(graph, sf = TRUE)
nearest_nodes <- nodes$node[st_nearest_feature(od_zones, nodes)]

# 4. Prepare OD matrix
od_matrix_long <- melt_od_matrix(od_matrix, nodes = nearest_nodes)

# 5. Run assignment
result <- run_assignment(graph, od_matrix_long, cost.column = "cost_column")

# 6. Visualize results (optional)
network$final_flows <- NA_real_
network$final_flows[attr(graph, "group.starts")] <- result$final_flows
mapview(network, zcol = "final_flows")
```

### Included Data

The package includes four example datasets for Africa:

- **`africa_network`**: A road transport network with 2,825 LINESTRING features representing existing roads (2,344 edges) and proposed new links (481 edges). Each edge includes attributes such as distance, travel duration, border crossing costs, terrain ruggedness, and road upgrade costs.

- **`africa_cities_ports`**: 453 African cities with population > 100,000 and international ports. Includes population data, capital status, and port cargo outflows.

- **`africa_segments`**: 14,358 raw network segments representing intersected road routes. Useful for demonstrating network consolidation and simplification functions.

- **`africa_trade`**: Bilateral trade flows between 47 African countries aggregated by HS section (21 product categories). Values represent annual averages over 2012-2022.

The `africa_network`, `africa_cities_ports`, and `africa_segments` datasets are from Krantz, S. (2024). [Optimal Investments in Africa's Road Network](https://doi.org/10.1596/1813-9450-10893). Policy Research Working Paper 10893. World Bank. Replication materials are available at [github.com/SebKrantz/OptimalAfricanRoads](https://github.com/SebKrantz/OptimalAfricanRoads).


## Main Functions

### Traffic Assignment and Route Enumeration

- **`run_assignment()`**:
  - Iterates through OD-pairs generating sensible alternative routes
  - Assigns traffic flows to network edges using path-sized logit model
  - Supports directed and undirected graphs
  - Returns flows and optional path/route information
  - **Key Parameters**:
    - **`beta`** (default: 1): Path-sized logit parameter (beta_PSL)
    - **`detour.max`** (default: 1.5): Maximum detour factor for alternative routes. Higher values consider more routes but increase computation time
    - **`angle.max`** (default: 90): Maximum detour angle in degrees (two-sided)
    - **`return.extra`**: Additional results to return from the route enumeration stage (`"paths"`, `"edges"`, `"counts"`, `"costs"`, `"weights"`)

### Network Processing

- **`linestrings_to_graph()`** - Convert LINESTRING geometries to graph data frame
- **`create_undirected_graph()`** - Convert directed graph to undirected with edge aggregation
- **`consolidate_graph()`** - Consolidate graph by removing intermediate nodes and merging edges
- **`simplify_network()`** - Simplify network using shortest-paths or spatial clustering methods

### Graph Utilities

- **`nodes_from_graph()`** - Extract unique nodes with coordinates from graph
- **`normalize_graph()`** - Normalize node IDs to consecutive integers starting from 1
- **`linestrings_from_graph()`** - Convert graph to LINESTRING geometries
- **`distances_from_graph()`** - Compute distance matrix for all node pairs

### OD Matrix Utilities

- **`melt_od_matrix()`** - Convert origin-destination matrices to long format

## Authors

- Sebastian Krantz
- Kamol Roy

## License

GPL-3

## Citation

If you use `flownet` in your research, please cite:

```r
citation("flownet")
```

