r - 根据图中的两个随机游走构建矩阵

Question

我正在做一个项目，我达到了这一点，但实际上我从一周前就坚持了下来，我尝试了很多想法，但所有尝试编写我的算法的代码都失败了。

假设我们有下面的简单图表:

边的顺序是:1--3, 1--4, 3--2

对于每条边，在每个顶点上定义随机游走以移动到它的邻居之一，例如:

对于第一条边，v1=1 ,v2=3, n1=3,4 和 n2=1,2 依次，所以从 v1 开始的可能移动和 v2 是:

1 to 3,3 to 1
1 to 4,3 to 1
1 to 3,3 to 2
1 to 4,3 to 2

对于第二条边，v1=1 ,v2=4, n1=3,4 和 n2=1 依次是，所以从 v1 到 v2 可能的移动是:

1 to 3,4 to 1
1 to 4,3 to 1

对于第三条边，v1=3 ,v2=2, n1=1,2 和n2=3 依次是，所以从v1和v2开始可能的走法是:

3 to 1,2 to 3
3 to 2,2 to 3

对于整个图，只有 8 种可能的移动，所以我有 8 个变量来构建约束矩阵

让我们用 x 表示移动(根据它们出现的顺序)；即

(1 to 3,3 to 1) to be represented by x_1
(1 to 4,3 to 1) to be represented by x_2
                 :
(3 to 1,2 to 3) to be represented by x_7
(3 to 2,2 to 3) to be represented by x_8

我想根据这些移动构建所需的约束矩阵，约束的数量将等于 \sum{i} (v1(i) 的邻居数 * v2(i) 的邻居数) 在我们的图中是 10。

我构建这个矩阵的算法是:

Step1: 1) select 1st edge, fix v1, v2, n2
       2) change n1 and fill the 1st row of the matrix by 1's in the place of the resulted moves and 0 if there is no similar move on the graph until you finish all elements in n1. 
Step2: move to the 2nd row of the matrix and select the 2nd element of n2 and
       1) loop over n1 
       2) fill the 2nd row by 1's in the place of the resulted moves until you finish all elements in n1. 
Step3: since you selected all elements in n1 and n2 for the vertices in the first edge move to a new row in the matrix 
Step4: Select next edges and do the same work done before until you finish all edges. 
Step5: select the 1st edge again and do the same work but while fixing v1,v2 &n1, loop over n2

根据该算法得到的矩阵为:

1 1 0 0 0 0 0 0
0 0 1 1 0 0 0 0
0 0 0 0 1 1 0 0
0 0 0 0 0 0 1 1
1 0 1 0 0 0 0 0
0 1 0 1 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 1 0
0 0 0 0 0 0 0 1

我没能做到的是:如何让矩阵知道有一个移动并在它的位置用 1 替换它，如果没有移动用 0 替换它的位置位置

我的代码是:

library(igraph)
graph<-matrix(c(1,3,1,4,3,2),ncol=2,byrow=TRUE)
g<-graph.data.frame(d = graph, directed = FALSE)

countercol<-0
for (edge in 1:length(E(g))){
v1<-ends(graph = g, es = edge)[1]
v2<-ends(graph = g, es = edge)[2]

n1<-neighbors(g,v1,mode=c("all"))
n2<-neighbors(g,v2,mode=c("all"))

countercol=countercol+(length(n1)*length(n2))
}

counterrow<-0
for (edge in 1:length(E(g))){
v1<-ends(graph = g, es = edge)[1]
v2<-ends(graph = g, es = edge)[2]

n1<-neighbors(g,v1,mode=c("all"))
n2<-neighbors(g,v2,mode=c("all"))

counterrow=counterrow+(length(n1)+length(n2))
}    

for (edge in 1:length(E(df))){
v1<-ends(graph = df, es = edge)[1]
v2<-ends(graph = df, es = edge)[2]
n1<-neighbors(df,v1,mode=c("all"))
n2<-neighbors(df,v2,mode=c("all"))
  ...
  ...
  ...
  }

我不是在找人写代码，我想要的是让程序区分可能的走法，并在结果走法的合适位置存储 1 和 0。

非常非常感谢任何形式的帮助

Answer 1

这是一个由两部分组成的解决方案

edgeMoves <- function(e) {
  umoves <- sapply(ends(graph = g, es = e), neighbors, graph = g, mode = "all", simplify = FALSE)
  do.call(paste, c(expand.grid(mapply(function(x, y) 
    paste(x, names(y), sep =" to "), ends(graph = g, es = e), umoves, SIMPLIFY = FALSE)), sep = ", "))
}
edgeConstraints <- function(e) {
  v <- ends(graph = g, es = e)
  n1 <- names(neighbors(g, v[1], mode = "all"))
  n2 <- names(neighbors(g, v[2], mode = "all"))
  t(cbind(sapply(n2, function(nn2) moves %in% paste0(v[1], " to ", n1, ", ", v[2], " to ", nn2)),
          sapply(n1, function(nn1) moves %in% paste0(v[1], " to ", nn1, ", ", v[2], " to ", n2))))
}
moves <- do.call(c, sapply(E(g), edgeMoves))
moves
# [1] "1 to 3, 3 to 1" "1 to 4, 3 to 1" "1 to 3, 3 to 2"
# [4] "1 to 4, 3 to 2" "1 to 3, 4 to 1" "1 to 4, 4 to 1"
# [7] "3 to 1, 2 to 3" "3 to 2, 2 to 3"

do.call(rbind, sapply(E(g), edgeConstraints)) * 1
#   [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
# 1    1    1    0    0    0    0    0    0
# 2    0    0    1    1    0    0    0    0
# 3    1    0    1    0    0    0    0    0
# 4    0    1    0    1    0    0    0    0
# 1    0    0    0    0    1    1    0    0
# 3    0    0    0    0    1    0    0    0
# 4    0    0    0    0    0    1    0    0
# 3    0    0    0    0    0    0    1    1
# 1    0    0    0    0    0    0    1    0
# 2    0    0    0    0    0    0    0    1

行顺序不同，但我怀疑这不是问题。此外，对于单边，您可以使用 edgeMoves(e) 和 edgeConstraints(e) * 1。