# Build a matrix depending on two random walks in a graph

I am working on a project and I reached this point but in fact I am stuck on it since one week ago, I tried many ideas but all trials to code my algorithm failed.

Suppose we have the following simple graph:

the edges in order are: 1--3, 1--4, 3--2

For each edge, a random walk is defined on each vertex to move to one of it's neighbors like:

For the first edge, v1=1 ,v2=3, n1=3,4 and n2=1,2 in order, so the possible moves from v1 and v2 are:

1 to 3,3 to 11 to 4,3 to 11 to 3,3 to 21 to 4,3 to 2

For the second edge, v1=1 ,v2=4, n1=3,4 and n2=1 in order,so the possible moves from v1 and v2 are:

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

For the third edge, v1=3 ,v2=2, n1=1,2 and n2=3 in order,so the possible moves from v1 and v2 are:

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

For the whole graph there are just 8 possible moves so I have 8 variables to construct the constraints matrix

Let us denote the moves by x's (according to their order of occurrences); i.e

(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

I want to build the required constraints matrix depending on these moves, the number of constraints will equal \sum{i} ( number of neighbors for v1(i) * number of neighbors for v2(i) ) which is 10 in our graph.

My algorithm to build this matrix is:

Step1: 1) select 1st edge, fix v1, v2, n22) 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 and1) 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

The resulted matrix according to this algorithm will be:

1 1 0 0 0 0 0 00 0 1 1 0 0 0 00 0 0 0 1 1 0 00 0 0 0 0 0 1 11 0 1 0 0 0 0 00 1 0 1 0 0 0 00 0 0 0 1 0 0 00 0 0 0 0 1 0 00 0 0 0 0 0 1 00 0 0 0 0 0 0 1

What I failed to do is: how to let the matrix know that there is a move and to replace it by 1 in it's position and if there is no move to replace it by 0 in it's position

My code is:

library(igraph)graph<-matrix(c(1,3,1,4,3,2),ncol=2,byrow=TRUE)g<-graph.data.frame(d=graph, directed=FALSE)countercol<-0for (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<-0for (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")).........}

I am not looking for someone to write the code, what I want is the idea to let the program differentiate between the possible moves and store 1's and 0's in the suitable position for the resulted move.

Many Many thanks for any kind of help

• I'm confused what you mean by v1=1 ,v2=3, n1=3,4 and n2=1,2. v means vertice, yes? What does n represent?– InfiniteFlashChessFeb 13 at 18:49
• How are you defining n2 in these examples? I don't understand your description of the problem.– MrFlickFeb 13 at 18:49
• @InfiniteFlashChess neighbours– גלעד ברקןFeb 13 at 18:54
• @InfiniteFlashChess v1, v2 are the first and second vertices consequently while n1, n2 are the neighbors (adjacent and connected vertices) for v1 and v2 consequently– user8003788Feb 13 at 20:30
• @MrFlick n2 are the neighbors (connected and adjacent vertices) to v2 which is the second vertex in any edge. The function neighbors(g,edge) determine these neighbors when specifying the vertex– user8003788Feb 13 at 20:33

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
The row order is different, but I suspect that it is not a problem. Also, for a single edge you may use edgeMoves(e) and edgeConstraints(e) * 1.
• @user8003788, see the update regarding the first request. I didn't create any indices. They are implicitly given by the order of a move in the vector moves (see the part with moves %in%). For instance, if you see ones in columns 2 and 4, you may get the corresponding moves with moves[c(2, 4)].– JuliusFeb 23 at 17:43