如何从一组同构三角形中 return 只有一个三角形？

Question

原题是here.

How to calcultate a probability that a graph with 6 vertices and 5 edges has a triangle?

我想模拟一下。我将创建 triangle 图，然后生成具有 n=6 个顶点和 m=5 个边的 1,000 个随机图，并找到三角形的分布。

现在我用一个三角形创建了一个 g 图，subgraph_isomorphisms() 函数 returns 6 同构三角形。然后我使用 unique() 函数来找到一个三角形。但是结果是6.

library(igraph) 

g          <- graph_from_literal( A--B, B--C, C--A, B--D, D--E, E--F)
triangle   <- graph_from_literal( A--B, B--C, C--A) 

ntriangles <- 0

iso <- subgraph_isomorphisms(triangle, g) 

motifs <- lapply(iso, function (x) { induced_subgraph(g, x) }) 
ntriangles <- length(unique(motifs))  
ntriangles

问题。 如何 return 一组同构三角形中只有一个三角形？

Answer 1

一种解决方案是将每个基序的边缘列表聚合成一个 data.frame 并使用 dplyr 的 distinct 来过滤唯一值：

library(dplyr)
edgelist <- do.call(rbind,
                    lapply(1:length(motifs), function(x) get.edgelist(motifs[[x]])))
edgelist <- data.frame(edgelist) %>% distinct() %>% as.matrix()
graph_from_edgelist(edgelist, directed = F)

这return秒：

> graph_from_edgelist(edgelist, directed = F)
IGRAPH e275587 UN-- 3 3 -- 
+ attr: name (v/c)
+ edges from e275587 (vertex names):
[1] A--B A--C B--C

EDIT 这是另一种方法，它更短，更接近建议的 OP：

motifs <- lapply(iso, function (x) { get.edgelist(induced_subgraph(g, x)) })   
ntriangles <- length(unique(motifs))  
ntriangles

这里我只是提取了包含顶点的边列表。如果没有唯一的 graph_id 和存储在 igraph 对象中的其他信息，unique 将 return 以下内容：

> length(unique(motifs))
[1] 1

如何从一组同构三角形中 return 只有一个三角形？

How to return only one triangle from the set of isomorphic triangles?

r

isomorphism

igraph