Construire une matrice dépendant de deux marches aléatoires dans un graphe

Question

Je travaille sur un projet et j'en suis arrivé à ce point, mais en fait je suis bloqué depuis une semaine, j'ai essayé beaucoup d'idées mais tous les essais pour coder mon algorithme ont échoué.

Supposons que nous ayons le graphique simple suivant :

les bords sont, dans l'ordre, les suivants 1--3 , 1--4 , 3--2

Pour chaque arête, une marche aléatoire est définie sur chaque sommet pour se déplacer vers l'un de ses voisins comme :

Pour le premier bord, v1=1 ,v2=3, n1=3,4 y n2=1,2 dans l'ordre, de sorte que les mouvements possibles de v1 et v2 sont :

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

Pour le deuxième bord, v1=1 ,v2=4, n1=3,4 y n2=1 dans l'ordre, de sorte que les mouvements possibles de v1 et v2 sont :

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

Pour le troisième bord, v1=3 ,v2=2, n1=1,2 y n2=3 dans l'ordre, de sorte que les mouvements possibles de v1 et v2 sont :

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

Pour l'ensemble du graphique, il n'y a que 8 mouvements possibles J'ai donc 8 variables pour construire la matrice des contraintes

Désignons les mouvements par des x (selon leur ordre d'apparition), c'est-à-dire

(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

Je veux construire la matrice des contraintes requises en fonction de ces mouvements, le nombre de contraintes sera égal à \sum{i} ( number of neighbors for v1(i) * number of neighbors for v2(i) ) qui est de 10 dans notre graphique.

Mon algorithme pour construire cette matrice est le suivant :

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

La matrice obtenue selon cet algorithme sera la suivante :

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

Ce que je n'ai pas fait : Comment faire savoir à la matrice qu'il y a un mouvement et la remplacer par 1 dans sa position et s'il n'y a pas de mouvement la remplacer par 0 dans sa position.

Mon code est le suivant :

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"))
  ...
  ...
  ...
  }

Je ne cherche pas quelqu'un pour écrire le code, ce que je veux c'est l'idée de permettre au programme de différencier les mouvements possibles et de stocker les 1 et les 0 dans la position appropriée pour le mouvement qui en résulte.

Merci beaucoup pour toute aide

Answer 1

Voici une solution en deux parties

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

L'ordre des lignes est différent, mais je pense que ce n'est pas un problème. De plus, pour un bord unique, vous pouvez utiliser edgeMoves(e) y edgeConstraints(e) * 1 .