R: Формирование матрицы расстояний

Непосредственное измерение расстояний между населенными пунктами для заполнения матрицы расстояний — трудоёмкая задача. В случае развитой дорожной сети:

• сложно определить кратчайший маршрут движения между пунктами;
• велик объём работы (для \(n\) населенных пунктов число измерений составит \(n^2 - n \over 2 \));
• сложно объединить матрицы расстояний нескольких районов.

Представление дорожной сети в виде графа позволяет привлечь соответствующий инструментарий R для облегчения этой работы.

Сформировать матрицу кратчайших расстояний между всеми парами вершин произвольного связного графа можно при помощи функции floyd.warshall.all.pairs.sp из пакета RBGL. В качестве единственного аргумента эта функция принимает объект класса graph, поддерживаемый одноименным пакетом. Оба этих пакета являются частью проекта Bioconductor, с особенностями их установки и использования можно ознакомиться на соответствующих страницах: RBGL и graph.

Виртуальный класс graph объединяет несколько подклассов, отличающихся способом описания графа. Класс graphAM хранит граф в виде матрицы связности его вершин, класс graphBAM — в виде таблицы с описанием его дуг.

Применим перечисленные инструменты на примере представления в виде графа дорожной сети Можгинского района Удмуртской республики — сформируем и сохраним в формате csv таблицу, первый и второй столбец которой соответствуют узлам дорожной сети (населенным пунктам и перекресткам), а третий столбец — протяженности соединяющих их участков дороги с твёрдым покрытием:

"from";"to";"weight"
"Кр. Яр";"Ломеслуд";3,5
"Камышлы";"Ломеслуд";1,75
"_1";"Ломеслуд";4,55
"_1";"_2";1,75
"_3";"_2";1,05
"_3";"Полянское";2,1
"_3";"Бол. Уча";1,4
"Пазял-Зюмья";"Бол. Уча";2,1
…
"Водзя";"Чежесть-Какси";2,8

На карте результат процесса выглядит так:

Всего — 111 дуг, 96 вершин (в т. ч. 21 перекрёсток и 4 населённых пункта не относящихся к Можгинскому району), примерно 3 человеко-часа работы.

Код R, формирующий матрицу расстояний между всеми населёнными пунктами Можгинского района представлен ниже:

> require("graph")
> require("RBGL")
> mozhga <- read.csv("mozhga.csv", sep=";", dec=",")
> mozhga.BAM <- graphBAM(mozhga) # Формируем граф экспериментального класса graphBAM,
> mozhga.AM <- as(mozhga.BAM, "graphAM") # преобразуем его в стабильный класс graphAM,
> mozhga.dist <- floyd.warshall.all.pairs.sp(mozhga.AM) # вычисляем матрицу расстояний
> d <- mozhga.dist[grep("_", colnames(mozhga.dist), invert=T), # и избавляемся от лишних узлов
+                  grep("_", rownames(mozhga.dist), invert=T)] # (предварены символом "_").

Объект d — искомая матрица расстояний между населенными пунктами Можгинского района.

UPD:

Вместо пакетов graph и RBGL удобнее воспользоваться пакетом igraph. В этом случае код R, формирующий матрицу расстояний, будет выглядеть следующим образом:

> require("igraph")
> mozhga.graph <- graph.data.frame(mozhga, directed=FALSE) # Формируем граф,
> mozhga.dist <- shortest.paths(mozhga.graph) # вычисляем матрицу расстояний
> d <- mozhga.dist[grep("_", colnames(mozhga.dist), invert=T), # и избавляемся от лишних узлов
+                  grep("_", rownames(mozhga.dist), invert=T)] # (предварены символом "_").