Edge direction in an undirected graph

[idshklein]

Hi, I'm trying to get points from a specified distance from an edge start point edges using rgeos::gInterpolate in an undirected graph. However, I found that when using an undirected graph, the "from" column id is always smaller than the "to" column id, but this is not reflected in the line direction, i.e it is sometimes opposite to the order of the nodes. This causes confusion when trying to figure out edge direction using only the node ids. I provide a reproducible example using the roxel network, examining both directed and undirected options for roxel:

library(tidyverse)
library(sf)
#> Linking to GEOS 3.8.0, GDAL 3.0.4, PROJ 6.3.1
library(lwgeom)
#> Linking to liblwgeom 3.0.0beta1 r16016, GEOS 3.8.0, PROJ 6.3.1
library(sfnetworks)

net1 <- as_sfnetwork(roxel,directed = T)
enet1 <- net1 %>% 
  activate(edges) %>% 
  as_tibble() %>% 
  as_tibble() %>% 
  mutate(start = st_startpoint(geometry),
         end = st_endpoint(geometry)) 
# enet1$from > enet1$to
nnet1 <- net1 %>% 
  activate(nodes) %>% 
  as_tibble() %>% 
  mutate(rn = row_number()) %>% 
  as_tibble()
res <- enet1 %>% 
  select(from,to,start,end) %>% 
  left_join(nnet1, by = c("from" = "rn")) %>% 
  left_join(nnet1, by = c("to" = "rn")) 
vec <- c()
for (i in 1:nrow(res)){
  vec <- c(vec,res$start[i] %>% identical(res$geometry.x[i]))
}
res[!vec,]
#> # A tibble: 0 x 6
#> # ... with 6 variables: from <int>, to <int>, start <GEOMETRY [°]>,
#> #   end <GEOMETRY [°]>, geometry.x <GEOMETRY [°]>, geometry.y <GEOMETRY [°]>
net1 <- as_sfnetwork(roxel,directed = F)

enet1 <- net1 %>% 
  activate(edges) %>% 
  as_tibble() %>% 
  as_tibble() %>% 
  mutate(start = st_startpoint(geometry),
         end = st_endpoint(geometry)) 
nnet1 <- net1 %>% 
  activate(nodes) %>% 
  as_tibble() %>% 
  mutate(rn = row_number()) %>% 
  as_tibble()
res <- enet1 %>% 
  select(from,to,start,end) %>% 
  left_join(nnet1, by = c("from" = "rn")) %>% 
  left_join(nnet1, by = c("to" = "rn")) 
vec <- c()
for (i in 1:nrow(res)){
  vec <- c(vec,res$start[i] %>% identical(res$geometry.x[i]))
}
res[!vec,] %>% as.data.frame() %>% head()
#>   from  to                     start                       end
#> 1   45  46 POINT (7.535567 51.94936) POINT (7.536936 51.94885)
#> 2   41 105 POINT (7.533678 51.94837) POINT (7.533754 51.94862)
#> 3   62 108  POINT (7.525955 51.9514)  POINT (7.52604 51.95099)
#> 4   29 121 POINT (7.541849 51.95792) POINT (7.540002 51.95732)
#> 5  160 161 POINT (7.527782 51.94409)  POINT (7.527693 51.9442)
#> 6   18 166 POINT (7.534147 51.94654) POINT (7.534918 51.94681)
#>                  geometry.x                geometry.y
#> 1 POINT (7.536936 51.94885) POINT (7.535567 51.94936)
#> 2 POINT (7.533754 51.94862) POINT (7.533678 51.94837)
#> 3  POINT (7.52604 51.95099)  POINT (7.525955 51.9514)
#> 4 POINT (7.540002 51.95732) POINT (7.541849 51.95792)
#> 5  POINT (7.527693 51.9442) POINT (7.527782 51.94409)
#> 6 POINT (7.534918 51.94681) POINT (7.534147 51.94654)

^{Created on 2020-10-12 by the reprex package (v0.3.0)}

Session info

``` r devtools::session_info() #> - Session info --------------------------------------------------------------- #> setting value #> version R version 4.0.2 (2020-06-22) #> os Windows 7 x64 SP 1 #> system x86_64, mingw32 #> ui RTerm #> language (EN) #> collate English_United Kingdom.1252 #> ctype English_United Kingdom.1252 #> tz Asia/Jerusalem #> date 2020-10-12 #> #> - Packages ------------------------------------------------------------------- #> package * version date lib source #> assertthat 0.2.1 2019-03-21 [1] CRAN (R 4.0.2) #> backports 1.1.7 2020-05-13 [1] CRAN (R 4.0.0) #> blob 1.2.1 2020-01-20 [1] CRAN (R 4.0.2) #> broom 0.7.0 2020-07-09 [1] CRAN (R 4.0.2) #> callr 3.4.3 2020-03-28 [1] CRAN (R 4.0.2) #> cellranger 1.1.0 2016-07-27 [1] CRAN (R 4.0.2) #> class 7.3-17 2020-04-26 [1] CRAN (R 4.0.2) #> classInt 0.4-3 2020-04-07 [1] CRAN (R 4.0.2) #> cli 2.0.2 2020-02-28 [1] CRAN (R 4.0.2) #> colorspace 1.4-1 2019-03-18 [1] CRAN (R 4.0.2) #> crayon 1.3.4 2017-09-16 [1] CRAN (R 4.0.2) #> DBI 1.1.0 2019-12-15 [1] CRAN (R 4.0.2) #> dbplyr 1.4.4 2020-05-27 [1] CRAN (R 4.0.2) #> desc 1.2.0 2018-05-01 [1] CRAN (R 4.0.2) #> devtools 2.3.1 2020-07-21 [1] CRAN (R 4.0.2) #> digest 0.6.25 2020-02-23 [1] CRAN (R 4.0.2) #> dplyr * 1.0.0 2020-05-29 [1] CRAN (R 4.0.2) #> e1071 1.7-3 2019-11-26 [1] CRAN (R 4.0.2) #> ellipsis 0.3.1 2020-05-15 [1] CRAN (R 4.0.2) #> evaluate 0.14 2019-05-28 [1] CRAN (R 4.0.2) #> fansi 0.4.1 2020-01-08 [1] CRAN (R 4.0.2) #> forcats * 0.5.0 2020-03-01 [1] CRAN (R 4.0.2) #> fs 1.4.2 2020-06-30 [1] CRAN (R 4.0.2) #> generics 0.0.2 2018-11-29 [1] CRAN (R 4.0.2) #> ggplot2 * 3.3.2 2020-06-19 [1] CRAN (R 4.0.2) #> glue 1.4.1 2020-05-13 [1] CRAN (R 4.0.2) #> gtable 0.3.0 2019-03-25 [1] CRAN (R 4.0.2) #> haven 2.3.1 2020-06-01 [1] CRAN (R 4.0.2) #> highr 0.8 2019-03-20 [1] CRAN (R 4.0.2) #> hms 0.5.3 2020-01-08 [1] CRAN (R 4.0.2) #> htmltools 0.5.0 2020-06-16 [1] CRAN (R 4.0.2) #> httr 1.4.1 2019-08-05 [1] CRAN (R 4.0.0) #> igraph 1.2.5 2020-03-19 [1] CRAN (R 4.0.2) #> jsonlite 1.7.0 2020-06-25 [1] CRAN (R 4.0.2) #> KernSmooth 2.23-17 2020-04-26 [1] CRAN (R 4.0.2) #> knitr 1.29 2020-06-23 [1] CRAN (R 4.0.2) #> lifecycle 0.2.0 2020-03-06 [1] CRAN (R 4.0.2) #> lubridate 1.7.9 2020-06-08 [1] CRAN (R 4.0.2) #> lwgeom * 0.2-5 2020-06-12 [1] CRAN (R 4.0.2) #> magrittr 1.5 2014-11-22 [1] CRAN (R 4.0.2) #> memoise 1.1.0 2017-04-21 [1] CRAN (R 4.0.2) #> modelr 0.1.8 2020-05-19 [1] CRAN (R 4.0.2) #> munsell 0.5.0 2018-06-12 [1] CRAN (R 4.0.2) #> pillar 1.4.6 2020-07-10 [1] CRAN (R 4.0.2) #> pkgbuild 1.1.0 2020-07-13 [1] CRAN (R 4.0.2) #> pkgconfig 2.0.3 2019-09-22 [1] CRAN (R 4.0.2) #> pkgload 1.1.0 2020-05-29 [1] CRAN (R 4.0.2) #> prettyunits 1.1.1 2020-01-24 [1] CRAN (R 4.0.2) #> processx 3.4.3 2020-07-05 [1] CRAN (R 4.0.2) #> ps 1.3.3 2020-05-08 [1] CRAN (R 4.0.2) #> purrr * 0.3.4 2020-04-17 [1] CRAN (R 4.0.2) #> R6 2.4.1 2019-11-12 [1] CRAN (R 4.0.2) #> Rcpp 1.0.5 2020-07-06 [1] CRAN (R 4.0.2) #> readr * 1.3.1 2018-12-21 [1] CRAN (R 4.0.2) #> readxl 1.3.1 2019-03-13 [1] CRAN (R 4.0.2) #> remotes 2.2.0 2020-07-21 [1] CRAN (R 4.0.2) #> reprex 0.3.0 2019-05-16 [1] CRAN (R 4.0.2) #> rlang 0.4.6 2020-05-02 [1] CRAN (R 4.0.2) #> rmarkdown 2.3 2020-06-18 [1] CRAN (R 4.0.2) #> rprojroot 1.3-2 2018-01-03 [1] CRAN (R 4.0.2) #> rvest 0.3.5 2019-11-08 [1] CRAN (R 4.0.0) #> scales 1.1.1 2020-05-11 [1] CRAN (R 4.0.2) #> sessioninfo 1.1.1 2018-11-05 [1] CRAN (R 4.0.2) #> sf * 0.9-5 2020-07-14 [1] CRAN (R 4.0.2) #> sfnetworks * 0.3.1 2020-09-03 [1] Github (luukvdmeer/sfnetworks@799203a) #> stringi 1.4.6 2020-02-17 [1] CRAN (R 4.0.0) #> stringr * 1.4.0 2019-02-10 [1] CRAN (R 4.0.2) #> testthat 2.3.2 2020-03-02 [1] CRAN (R 4.0.2) #> tibble * 3.0.3 2020-07-10 [1] CRAN (R 4.0.2) #> tidygraph 1.2.0 2020-05-12 [1] CRAN (R 4.0.2) #> tidyr * 1.1.0 2020-05-20 [1] CRAN (R 4.0.2) #> tidyselect 1.1.0 2020-05-11 [1] CRAN (R 4.0.2) #> tidyverse * 1.3.0 2019-11-21 [1] CRAN (R 4.0.2) #> units 0.6-7 2020-06-13 [1] CRAN (R 4.0.2) #> usethis 1.6.1 2020-04-29 [1] CRAN (R 4.0.2) #> utf8 1.1.4 2018-05-24 [1] CRAN (R 4.0.2) #> vctrs 0.3.1 2020-06-05 [1] CRAN (R 4.0.2) #> withr 2.2.0 2020-04-20 [1] CRAN (R 4.0.2) #> xfun 0.15 2020-06-21 [1] CRAN (R 4.0.2) #> xml2 1.3.2 2020-04-23 [1] CRAN (R 4.0.2) #> yaml 2.2.1 2020-02-01 [1] CRAN (R 4.0.0) #> #> [1] D:/R-4.0.2/library ```

I would expect that the direction of the edge in the edges geometry column would match the order of the from - to points.

[agila5]

Hi @idshklein, maybe it's just me but I really don't understand the bug and the expected output. Could you please add more details or more comments in the reprex? Sorry and thanks!

[luukvdmeer]

However, I found that when using an undirected graph, the "from" column id is always smaller than the "to" column id, but this is not reflected in the line direction, i.e it is sometimes opposite to the order of the nodes. This causes confusion when trying to figure out edge direction using only the node ids.

I understand the confusion. Putting the smaller node ID value in the from column is done automatically by tidygraph for undirected networks, and hard to change since we sub-class tbl_graph. To not reverse the linestring geometries of the "affected" edges was a choice on our side, since in undirected networks, the edges don't have a direction either way, so we argued "edge direction" is not really a thing in that case. Reversing would only add extra, unnecessary computation and slow down network creation.

However, whenever you want to turn your undirected network into a directed one (hence, edge direction does matter), use the spatial morpher to_spatial_directed. This morpher will infer the direction of the edges from the geometries (i.e. from the first node in the linestring, to the last node in the linestring), and not from the node IDs in the to and from columns, as the to_directed morpher of tidygraph will do.

So I would either morph the network into a directed one before figuring out direction (probably the preferred way conceptually), or using lapply in combination with st_startpoint or st_boundary on the geometry column, if you are only interested in the first point of the edge linestring.

Note to self: this should be documented in the vignettes

[luukvdmeer]

This is now documented in the main vignette, see here.