Структура уровня зависимости от матрицы смежности

Question

У меня есть матрица смежности, например:

        r01-r07 r03 r04 r05 r06 r08-r02 r09 r10 I1 I2 I3 I4
r01-r07       0   0   0   1   0       0   0   0  0  0  0  0
r03           1   0   0   0   0       0   0   0  0  0  0  0
r04           1   0   0   0   0       0   0   0  0  0  0  0
r05           0   0   0   0   0       0   0   0  0  0  0  0
r06           0   1   0   0   0       0   0   0  0  0  0  0
r08-r02       0   1   0   0   0       0   1   0  0  0  0  0
r09           0   0   0   0   0       0   0   0  0  0  0  0
r10           0   0   0   1   0       0   0   0  0  0  0  0
I1            1   0   0   0   0       0   0   0  0  0  0  0
I2            0   0   1   0   0       0   0   0  0  0  0  0
I3            0   0   0   0   0       1   0   0  0  0  0  0
I4            0   0   0   0   0       0   1   0  0  0  0  0

Есть ли способ получить уровень зависимости объекта из матрицы смежности, который показывает, какие объекты находятся на каждом уровне, на 1 или 0?, Например:

       r01-r07 r03 r04 r05 r06 r08-r02 r09 r10 I1 I2 I3 I4
root         0   0   0   0   1       0   0   1  1  1  1  1
level1       0   0   1   0   0       1   0   0  0  0  0  0
level2       0   1   0   0   0       0   1   0  0  0  0  0
level3       1   0   0   0   0       0   0   0  0  0  0  0
level4       0   0   0   1   0       0   0   0  0  0  0  0

Я использую методы graph_from_adjacency_matrix и get.adjedgelist(network, mode = "out") для получения ребер из пакета igraph.

Я могу получить заказ по topo_sort(network, mode = "out")

+ 12/12 vertices, named, from c00e2ba:
 [1] r06     r10     I1      I2      I3      I4      r04     r08-r02 r03     r09     r01-r07 r05

Воспроизводимый пример:

library(igraph)
# Adjacency matrix
x <- matrix(c(0,0,0,1,0,0,0,0,0,0,0,0,
               1,0,0,0,0,0,0,0,0,0,0,0,
               1,0,0,0,0,0,0,0,0,0,0,0,
               0,0,0,0,0,0,0,0,0,0,0,0,
               0,1,0,0,0,0,0,0,0,0,0,0,
               0,1,0,0,0,0,1,0,0,0,0,0,
               0,0,0,0,0,0,0,0,0,0,0,0,
               0,0,0,1,0,0,0,0,0,0,0,0,
               1,0,0,0,0,0,0,0,0,0,0,0,
               0,0,1,0,0,0,0,0,0,0,0,0,
               0,0,0,0,0,1,0,0,0,0,0,0,
               0,0,0,0,0,0,1,0,0,0,0,0), ncol = 12, byrow = TRUE)
colnames(x) <- c("r01-r07", "r03", "r04", "r05", "r06", "r08-r02",
                 "r09", "r10", "I1", "I2", "I3", "I4")
row.names(x) <- c("r01-r07", "r03", "r04", "r05", "r06", "r08-r02",
                 "r09", "r10", "I1", "I2", "I3", "I4")

# Create the network
network <- graph_from_adjacency_matrix(as.matrix(x), mode = "directed")
# Edge list
print(get.adjedgelist(network,mode = "out"))
# Sorted order
print(topo_sort(network, mode = "out"))
# Visualization
plot.igraph(network, vertex.size = 15, edge.arrow.size = 0.5, vertex.label.dist=3,
   layout=layout.kamada.kawai, vertex.label.color="blue", edge.color="black")

Answer 1

Вот один из возможных подходов:

#find the root nodes
deg <- degree(network, mode="in")==0
roots <- names(deg)[deg]

#get all paths from root to every other nodes
sp <- lapply(roots, all_simple_paths, graph=network)

#get the last node in these paths and number of edges to reach this last node
dat <- do.call(rbind, lapply(unlist(sp, recursive=FALSE), 
    function(x) data.frame(node=names(x)[length(x)], dist=length(x))))

#find the max depth for each non-root node
depth <- tapply(dat$dist, dat$node, max)

#construct required result
ans <- matrix(0L, ncol=length(V(network)), nrow=max(depth))
rownames(ans) <- c("root", paste0("level", seq_len(max(depth)-1)))
colnames(ans) <- names(V(network))
ci <- match(c(roots, names(depth)), colnames(ans))
ans[cbind(c(rep(1, length(roots)), depth), ci)] <- 1L

вывод ans:

       r01-r07 r03 r04 r05 r06 r08-r02 r09 r10 I1 I2 I3 I4
root         0   0   0   0   1       0   0   1  1  1  1  1
level1       0   0   1   0   0       1   0   0  0  0  0  0
level2       0   1   0   0   0       0   1   0  0  0  0  0
level3       1   0   0   0   0       0   0   0  0  0  0  0
level4       0   0   0   1   0       0   0   0  0  0  0  0