Как найти шаблон подграфа в исходном графике? - PullRequest
Новая
       64

Как найти шаблон подграфа в исходном графике?

0 голосов
/ 17 ноября 2018

У меня есть graph. Видно, что комплектный подграф A<->B<->C и E<->D<->F (pattern) встречается дважды в graph. Я нашел motifs и взял 1-й и 7-й мотивы из списка igraphs. 

libraty(igraph)
el <- matrix( c("A", "B", 
                "A", "C",
                "B", "A",
            "B", "C", 
            "C", "A",
            "C", "B",
            "C", "E", 
                "E", "D", 
                "E", "F",
                "D", "E",
            "D", "F", 
            "F", "E",
            "F", "D"), 
nc = 2, byrow = TRUE)


graph <- graph_from_edgelist(el)

pattern <- graph.isocreate(size=3, number = 15, directed=TRUE)

iso    <- subgraph_isomorphisms(pattern, graph)      
motifs <- lapply(iso, function (x) { induced_subgraph(graph, x) })

V(graph)$id <- seq_len(vcount(graph))
V(graph)$color <- "white"

par(mfrow=c(1,2))

plot(graph, edge.curved=TRUE, main="Original graph")

m1 <- V(motifs[[1]])$id; m2 <- V(motifs[[7]])$id 

V(graph)[m1]$color="red"; V(graph)[m2]$color="green"

plot(graph, edge.curved=TRUE, main="Highlight graph")

enter image description here

У меня есть решение, выбрав вручную motifs[[1]], motifs[[7]].

Вопрос.

Как автоматически найти списки вершин подграфа шаблона (например, составить подграф)?

...