Доброго времени суток всем.
У меня очень простой вопрос, на который я не смог найти ответа, боюсь, из-за отсутствия терминологии. В графике пакета r как считаются веса? Считаются ли они затратами и, следовательно, уменьшают пропускную способность ребра, или они действительно считаются пропускной способностью ребра?
Большое Вам спасибо
В igraph веса - это атрибуты ребер, которые представляют трение или стоимость перемещения этого ребра в детали, а не вместимость или пропускная способность края. Низкий вес обеспечивает низкую сумму весов пути, а get.shortest.paths() возвращает путь с наименьшей суммой весов при запуске без отключения весов на взвешенном графе.
В этом примере кода показан график с разными кратчайшими путями в взвешенном и невзвешенном режиме и объясняется, почему путь рассчитывается по-разному.
library(igraph)
# Colours for the weighted edges
N <- 22
set.seed(7890123)
# Make a random graph with randomly weighted edges coloured in gray
g <- erdos.renyi.game(N, .2, type="gnp", directed=F, loops=F, weighted=T)
E(g)$weight <- sample(1:40, length(E(g)), replace=T)
#E(g)$weight <- E(g)$weight/10
E(g)$color <- "gray"
V(g)$size <- 4
V(g)$size[c(1,N)] <- 12
# Look how the shortest path is calculated differently when taken the graph weihgt into acocunt
(weighted.path <- unlist(get.shortest.paths(g, 1, N)$vpath) )
(unweighted.path <- unlist(get.shortest.paths(g, 1, N, weights=NA)$vpath) )
# Set weights and colours of shortest paths to visualise them
E(g, path=weighted.path)$color <- "red"
E(g, path=unweighted.path)$color <- "green"
# plot the graph with red shortest weighted path, and green shortest path
same.sahpe <- layout_with_fr(g)
plot(g, vertex.color="white", vertex.label=NA, edge.weight=2, edge.width=(E(g)$weight/5), layout=same.sahpe)
# The two paths look like this. Even though path-length might be longer, a weighted
# shortest path is determined using the sum of path-weights. As with path-lengths, the
# lowest value is the path most easily travelled by. In this case, the weighted alternative
# has a longer path but with lower friction.
data.frame(path.length=c(length(weighted.path),
length(unweighted.path)
),
weight.sum=c(sum(E(g, path=unlist(weighted.path))$weight),
sum(E(g, path=unlist(unweighted.path))$weight)
)
)
Увидеть, что самый короткий невзвешенный путь между двумя большими вершинами имеет длину 4, но проходит по довольно толстым зеленым краям. Кратчайший взвешенный путь имеет наименьшую сумму весов и проходит больше шагов (5), но по клиньям с меньшим весом, что приводит к меньшей сумме весов или более низкой стоимости путешествия по части, если хотите.
g вы можете перевернуть веса вверх ногами, как вы предлагаете выше, используя E(g)$weight <- max(E(g)$weight) - E(g)$weight.
- person nJGL; 18.01.2019
size, равный 4: V(g)$size <- 4, а затем два узла (1 и N) увеличиваются V(g)$size[c(1,N)] <- 12
- person nJGL; 18.11.2020
Если вы читаете официальную документацию в пакете R igraph - https://igraph.org/r/doc/strength.html
вы обнаружите, что веса упоминаются как:
«Весовой вектор. Если граф имеет атрибут ребра веса, то он используется по умолчанию. Если граф не имеет атрибута ребра веса и этот аргумент равен NULL, то выдается предупреждение и вызывается степень».
Но также:
https://igraph.org/r/doc/edge_attr.html
объясняет, что края даны как атрибут веса
