Hello, all Tamas, thanks you for ideas.
I found usefull links http://www.mikedecuir.com/archive/2012/12/finding-triangles-with-r/ https://graph-tool.skewed.de/static/doc/topology.html#graph_tool.topology.subgraph_isomorphism I have tried to implicate the your approach. Unfortunately, I couldn't to map the vertex IDs to edge IDs using get.edge.ids() on step 2. I have tried ei <- get.edge.ids(UG, c(1,2, 2,3, 3,1)) E(UG)[ei] This code works, but I couldn't understand how to use a list in common case. Without step 2, I couldn't to code step 4. Here's my current attempt. library(igraph) d <- matrix(c(0,1,0,1,0, 0,0,1,1,1, 1,0,0,1,1, 0,1,1,0,1, 1,1,1,0,0),nrow=5,ncol=5) G <- graph.adjacency(d) V(G)$label <-c("A","B","C","D","E") V(G)$shape = "none" plot(G, edge.arrow.size=0.5) # Here are the adjacency matrices for each of the four subgraphs d0<-matrix(c(0,1,0,0,0,1,1,0,0),nrow=3,ncol=3) d1<-matrix(c(0,1,0,0,0,1,1,1,0),nrow=3,ncol=3) d2<-matrix(c(0,1,0,1,0,1,1,1,0),nrow=3,ncol=3) d3<-matrix(c(0,1,1,1,0,1,1,1,0),nrow=3,ncol=3) # Turn them into a convenient list sbgCycle.mat<-list(d0,d1,d2,d3) n <- length(list(d0,d1,d2,d3)) # And then into a list of graph objects pattern<-lapply(sbgCycle.mat, graph.adjacency) par(mfrow=c(2,2)) # The four triangles all contain a directed 3-cycle subgraph plot(pattern[[1]], edge.curved=TRUE, xlab='Cycle') plot(pattern[[2]], edge.curved=TRUE, xlab='One reciprocal edge') plot(pattern[[3]], edge.curved=TRUE, xlab='Two reciprocal edges') plot(pattern[[4]], edge.curved=TRUE, xlab='Three reciprocal edges') # 1. Convert the graph to undirected UG <- simplify(G) UG <- as.undirected(UG) #plot(UG) # 2. Search for triangles in the undirected graph triangle <- graph.full(3) sbg.triangle <- graph.get.subisomorphisms.vf2(UG, triangle) ei <- get.edge.ids(UG, c(1,2, 2,3, 3,1)) # work E(UG)[ei] #e1 <- get.edge.ids(UG, c(sbg.triangle[[1]])) # does't work # 3. Search for subisomorphisms in the directed graph to all of the four templates #for(i in 1:n){ # loop 'for' does not work ? rewrite with 'apply' later subisom1 <- subgraph_isomorphisms(pattern[[1]], G, method="lad", induced=TRUE) subisom2 <- subgraph_isomorphisms(pattern[[2]], G, method="lad", induced=TRUE) subisom3 <- subgraph_isomorphisms(pattern[[3]], G, method="lad", induced=TRUE) subisom4 <- subgraph_isomorphisms(pattern[[4]], G, method="lad", induced=TRUE) #} # 4. For each triangle check which pattern it was isomorphic G2 <- G for(i in 1:length(sbg.triangle)) { new_weight <- subgraph_isomorphisms(pattern[[1]], G, method="lad", induced=TRUE) E(G2, path = E(G)[get.edge.ids(???)])$weight = new_weight } -- Mike _______________________________________________ igraph-help mailing list [email protected] https://lists.nongnu.org/mailman/listinfo/igraph-help
