Lightweight Adjacency Lists

Provides an S3 class to represent graph adjacency lists using 'vctrs'. Allows for creation, subsetting, combining, and pretty printing of these lists. Adjacency lists can be easily converted to zero-indexed lists, which allows for easy passing of objects to low-level languages for processing.

adj

adj provides a lightweight adjacency list class for R, built on the vctrs package. Adjacency lists are validated on creation, automatically reindex when subsetted or indexed, and support pretty-printing. Lists can be easily converted to a zero-index basis, which allows for easy passing of objects to low-level languages for processing. Creation of adjacency lists from shapefiles is supported through an optional dependency on geos.

Installation

You can install the development version of adj from GitHub with:

# install.packages("pak")
pak::pak("alarm-redist/adj")

Examples

adj comes loaded with example data for the seven bridges of Königsberg.

library(adj)
data("konigsberg")

konigsberg
#>   area     bridge_to       x      y
#> 1    A B, B, C, C, D 20.5100 54.706
#> 2    B       A, A, D 20.5115 54.709
#> 3    C       A, A, D 20.5110 54.703
#> 4    D       A, B, C 20.5170 54.705

We can build an adjacency graph using the unique identifiers of each area.

a = adj(konigsberg$bridge_to, ids = konigsberg$area, duplicates = "allow")
print(a, n = 5)
#> <adj[4]>
#> [1] {2, 2, 3, 3, 4} {1, 1, 4}       {1, 1, 4}       {1, 2, 3}

Alternatively, we can create an adjacency list from a list of integers. Here, we set duplicates = "remove" to remove any duplicate edges.

adj(c(2, 3, 3), c(1, 3), c(1, 1, 2), duplicates = "remove")
#> <adj[3]>
#> [1] {2, 3} {1, 3} {1, 2}

Once created, adjacency lists can be subsetted using standard R indexing, and the internal indices will be automatically updated.

a[1:2]
#> <adj[2]>
#> [1] {2, 2} {1, 1}
rev(a)
#> <adj[4]>
#> [1] {4, 3, 2}    {4, 4, 1}    {4, 4, 1}    {3, 3, 2, …}

Quotient graphs can be created from adjacency lists and a grouping vector. Here, we create a quotient graph by grouping the two islands (areas A and D) together.

adj_quotient(a, c("AD", "B", "C", "AD"))
#> <adj[3]>
#> [1] {2, 3} {1}    {1}

Finally, adjacency lists can be converted to a matrix or zero-indexed.

as.matrix(a)
#>      [,1] [,2] [,3] [,4]
#> [1,]    0    2    2    1
#> [2,]    2    0    0    1
#> [3,]    2    0    0    1
#> [4,]    1    1    1    0

adj_zero_index(a)
#> [[1]]
#> [1] 1 1 2 2 3
#> 
#> [[2]]
#> [1] 0 0 3
#> 
#> [[3]]
#> [1] 0 0 3
#> 
#> [[4]]
#> [1] 0 1 2