subgraph match with function graph.subisomorphic.lad(gr1,gr2,induced = TRUE, map = FALSE)

[MonicaStefu]

I have 2 graphs of order N = 8, gr1 edges: [1] 1--6 1--7 1--8 2--7 3--8 4--8 5--8 gr 2 edges: 1 -- 5 6 7 8 2 -- 5 6 7 8 3 -- 5 6 7 8 4 -- 7 8 5 -- 1 2 3 8 6 -- 1 2 3 8 7 -- 1 2 3 4 8 -- 1 2 3 4 5 6

and the function
graph.subisomorphic.lad(gr1,gr2,induced = TRUE, map = FALSE) closes R and returns to Linux Ubuntu 14.04.2 LTS, Release 14.04. with the message * Error in `/usr/lib/R/bin/exec/R': double free or corruption (out): 0x0000000002a2f0d0 * Aborted (core dumped)

The input file is temp_Test31_4370.txt and its content is

Graph 31, order 8. 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 1 1 1 0 0 0

Graph 4370, order 8. 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0

The program which is a reproducible example is below. The working directory for the program is Rwork and the directory for imput files is InputMCS inside Rwork.

strhead <- function(s,n) { ## if(n<0) ss=substr(s,1,nchar(s)+n) ## x=substr(x,start,stop) else ss=substr(s,1,n) return(ss) }

ReadClean <- function(y){ ## y=filename.zzz | f. citeste rindurile care incep cu 1 sau cu 0 erg <- c() file <- scan(y, what="numeric", sep=";") for(i in 1:length(file)){ if (strhead(file[i],1) == "0" || strhead(file[i],1) == "1") ## if primul caracter din file[i] e 0 sau 1, if (substr(file[i],1,1) == "0" || substr(file[i],1,1) == "1")
erg <- c(erg,file[i]) }

print(erg)

      return(erg)
      }

Help Function 1, Converts a String with Numbers - x, into a List/ vector of Integers y*

list2Int <- function(x){ y <- c() for(i in 1:length(x)){ y <- c(y,as.integer(x[i])) } return(y) }

Main Function, Returns a list of Adjacency Matrix* ## y=filename.zzz, n=dimensiunea

GengConvertAdzenz <- function(y){ t <- 0 erg <- list() nvek <- c() cleanFile <- ReadClean(y) for(i in 1:length(cleanFile)){ intlist <- list2Int(unlist(strsplit(cleanFile[i]," "))) n=length(intlist) nvek <- c(nvek,intlist) t <- t+1 if(t == n){ m <- matrix(nvek,n,n,TRUE)

print(m)

                erg <- append(erg,list(m))
                t <- 0
                nvek <- c()
             }
          }
        return(erg)

}

GenGraphK <- function(m){ gr_k <- graph.adjacency(m, mode=c("undirected"), weighted=NULL, diag=FALSE) return(gr_k) }

setwdir<-function(){ sdir <- readline("input dir, implicit InputMCS:") dir=getwd() if (sdir==""){ dir=paste0(dir,"/InputMCS")} else{ dir=paste(dir,sdir,sep = "/")}

setwd(dir)

return(dir)

} readFiles <-function(){ erg1 <- list() dir_i <- getwd() dir <- setwdir() setwd(dir) print(dir) file_list <- list.files(dir,pattern="*.txt",include.dirs = FALSE) print(file_list) for (file in file_list){ erg <- GengConvertAdzenz(file) erg1 <- append(erg1,erg) } setwd(dir_i) return(erg1) }

MainPrg <- function(){ library(igraph) erg <- readFiles()

graphs 31 and 4370 gives crash

  i <- 1
        m <- erg[[i]]       ##m=GenAdjMatrix(erg,n,i)
        n1=length(m[1,])
        gr1=GenGraphK(m)
    j <- 2
            m <- erg[[j]]   ##m=GenAdjMatrix(erg,n,j)
            gr2=GenGraphK(m)
            n2=length(m[1,])
            cat("graf1:")
          str(gr1)
            cat("graf2:")
            str(gr2)
    print("zzzzzzzzzzzzxxxxxxxxxxxxxx")
    match <- graph.subisomorphic.lad(gr1,gr2,induced = TRUE, map = FALSE)
    print(paste("match: ",match[1]))

}

In fact the program has to find the size of Maximum Common Subgraph for a all the pairs of 2 graph in the list of .txt files in the InputMCS directory. The result is a triangular matrix. So it should work for graphs of any (and different) sizes. The program works ok for graphs of N = 5,6,7 and crashes for graph of order N=8. I combined just graphs of orders 3 and 7 till now. If you want, I send you also another examples of graphs where it crash, but maybe I can sent you the program and the input file till N=9 to test it.

Hope that the solve of the problem will be quickly, else please tell me to find another solution. I'm more than a week late with my program.

Thanks, Monica

[MonicaStefu]

I should have used the function for isomorphism for graphs of same order, N=8.

[gaborcsardi]

Well, it should not crash anyway..... however your example is very long and I have a hard time reading through it....

[MonicaStefu]

In the meantime I made another program. I'll write tomorrow perhaps, I can't now. I'll look again. I gives error on multicore, I should send you the program /another example.

[MonicaStefu]

Here is another example, I sent it to you by mail on gmail address the program + input file in 28 Apr. I checked and on Windows works ok and on Linux Ubuntu crashes. Now it's a subgraph of size 7 and a graph of size 8.

SGraph 121, v. 2-8, order 8. 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 1 0 0 1 0 0 1 0 1 1 1 0 0

Graph 4573, order 8. 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0

you can load the graphs in the program in any way you want, if you ask I'll make a shorter program for input. The problem is that at the end of the program I print the graphs and then use the function and it crashes. * Error in `/usr/lib/R/bin/exec/R': double free or corruption (out): 0x0000000001b50860 * Aborted (core dumped)

tomorrow I'll check again the example with first pair of graphs, I checked yesterday and it seems ok on Windows. I haven't too much time.

[MonicaStefu]

For the first graphs, 31 and 4370, both of vertex size 8, it's the same case, it works on windows 7 and it crashes on Ubuntu. It would be good to check how it works on others Linux versions and to see if the crash it's from R or from Ubuntu.

[szhorvat]

There was a crash bug in LAD, but it was fixed in the C core for version 0.8