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:enter image description here

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

  • 1
    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
  • 2
    @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

Here's a solution consisting of two parts

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, let me know if I should add any explanations– JuliusFeb 20 at 2:34
  • Thanks for this nice code, In fact I wrote something but it is more complicated!! I will understand your code and if there is something strange I will ask..thanks again– user8003788Feb 20 at 16:56
  • Thanks again for this great help, it is working very well but I am following it and trying to understand how it could be possible to let it work on each edge alone(i.e to build the resulted matrix from only an edge not all edges together)?– user8003788Feb 23 at 16:57
  • The second question is how could I know that the firs 1 in your resulted matrix is related to the first move (1 to 3,3 to 1)? i.e I don't understand how you indexed the moves ? for example if I want to know what is the move represented by one in the first row and column, what I call? and thanks in advance– user8003788Feb 23 at 17:01
  • @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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.