在多边图中列出三元组

Question

根据这张图：

import igraph as ig 
g=ig.Graph.Erdos_Renyi(10, 0.5, directed=True)

使用triad_人口普查功能，我们可以很容易地找到它的三合会普查：

^{pr2}$

如果我们打印'tc'，我们会得到如下信息：

003 : -2147483648 | 012 :  5 | 102 :  2 | 021D:  4
021U:  6 | 021C:  8 | 111D:  9 | 111U: 14
030T:  5 | 030C:  3 | 201 :  6 | 120D:  9
120U:  5 | 120C: 21 | 210 : 18 | 300 :  4

也就是说，对于每个空间坐标轴类型，我们都有在图形中找到它的次数。在

与“三合会普查”不同的是，“三合会名单”不仅会给出三合会被发现的次数，而且会给出每次出现的参与者节点。据我所知，这里的问题是“三元组列表算法”不一定与“三元组普查算法”相同，后者的计算成本更低。在

我试着看同构，定义每个三和弦，然后在图中搜索它们：

# Set up the 16 possible triads
triad_dict=dict()

#003 A,B,C, the empty graph.
triad = ig.Graph(n = 3, directed=True)
triad_dict['003'] = triad

#012 A->B, C, the graph with a single directed edge.
triad = ig.Graph(n = 3, directed=True)
triad.add_edges([(0,1)])
triad_dict['012'] = triad

#102 A<->B, C, the graph with a mutual connection between two vertices.
triad = ig.Graph(n = 3, directed=True)
triad.add_edges([(0,1),
                (0,2)])
triad_dict['102'] = triad

#021D A<-B->C, the out-star.
triad = ig.Graph(n = 3, directed=True)
triad.add_edges([(0,1),
               (0,2)])
triad_dict['021D'] = triad

#021U A->B<-C, the in-star.
triad = ig.Graph(n = 3, directed=True)
triad.add_edges([(1,0),
                 (2,0)])
triad_dict['021U'] = triad 

#021C A->B->C, directed line.
triad = ig.Graph(n = 3, directed=True)
triad.add_edges([(0,1),
                 (1,2)])
triad_dict['021C'] = triad 

#111D A<->B<-C.
triad = ig.Graph(n = 3, directed=True)
triad.add_edges([(0,1),
               (0,2)])
triad_dict['111D'] = triad

#111U A<->B->C.
triad = ig.Graph(n = 3, directed=True)
triad.add_edges([(0,1),
               (0,2),(2,0)])
triad_dict['111U'] = triad

#030T A->B<-C, A->C.
triad = ig.Graph(n = 3, directed=True)
triad.add_edges([(0,1),
               (2,1),
               (0,2)])
triad_dict['030T'] = triad

#030C A<-B<-C, A->C.
triad = ig.Graph(n = 3, directed=True)
triad.add_edges([(1,0),
                 (2,1),
                 (0,2)])
triad_dict['030C'] = triad

#201 A<->B<->C.
triad = ig.Graph(n = 3, directed=True)
triad.add_edges([(0,1),(1,0),
                 (1,2),(2,1)])
triad_dict['201'] = triad

#120D A<-B->C, A<->C.
triad = ig.Graph(n = 3, directed=True)
triad.add_edges([(0,1),
                 (0,2),
                 (1,2), (2,1)])
triad_dict['120D'] = triad

#120U A->B<-C, A<->C.
triad = ig.Graph(n = 3, directed=True)
triad.add_edges([(0,1),
                (2,1),
                (0,2), (2,0)])
triad_dict['120U'] = triad

#120C A->B->C, A<->C.
triad = ig.Graph(n = 3, directed=True)
triad.add_edges([(0,1),
                 (1,2),
                 (0,2), (2,0)])
triad_dict['120C'] = triad

#210 A->B<->C, A<->C.
triad = ig.Graph(n = 3, directed=True)
triad.add_edges([(0,1), 
                 (1,2), (2,1),
                 (0,2), (2,0)])
triad_dict['210'] = triad

#300 A<->B<->C, A<->C, the complete graph.
triad = ig.Graph(n = 3, directed=True)
triad.add_edges([(0,1), (1,0),
                (1,2), (2,1),
                (0,2), (2,0)])
triad_dict['300'] = triad

seq = ['300', 
       '210', 
       '120C', '120U', '120D', '201',
       '030C', '030T','111U','111D',
       '021C','021U','021D','102',
       '012',
       '003']

#Search isomorphisms for every triad
isomorphisms = dict()
for key in seq:
    isomorphisms[key] = g.get_subisomorphisms_vf2(triad_dict[key])

但是，如果我们有A<；->；B<；->；C，它将与几个三元组相关联：

A<->B<->C
A->B->C
A<->B->C
etc.

我只想考虑更完整的空间坐标轴（有更多边的空间坐标轴）并放弃它的子空间坐标轴。我们可以清除同构字典中重复的三元组，从高阶（更多边）到低阶，例如：

#Search isomorphisms for every triad
seen = []
for key in seq:
    isos = isomorphisms[key]
    isos = [i for i in isos if i not in seen]
    isomorphisms[key] = isos 
    seen.extend(isos)

但是，这不是一个选项，因为图形表示节点之间的一组对话。如果发生两次不同的对话：

A->B->C->D (1)
A->B->C (2)

（图为多边图）

脚本将删除（1），因为它认为（2）是与（1）相对应的子图，但不一定是真的，因为在本例中，它们代表不同的对话。在

Answer 1

你可以列出子图同构到一个特定的母题，见http://igraph.sourceforge.net/doc/python/igraph.GraphBase-class.html#get_subisomorphisms_vf2

编辑

这实际上是一个错误的答案，因为你会发现包含你正在搜索的模体的诱导子图。见评论。在

不幸的是（目前）唯一的方法是从C中执行，并编写一个回调函数，该函数在每次发现motif时都会被调用。http://igraph.sourceforge.net/doc/html/ch17s03.html#igraph_motifs_randesu_callback