Как найти шаблон подграфа в исходном графике?
У меня есть 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")
У меня есть решение от руки выбора motifs[[1]]
, motifs[[7]]
,
Вопрос.
Как автоматически найти списки вершин подграфа шаблона (например, составить подграф)?