这个想法很简单:我使用邻接矩阵而不是直接处理图。我觉得这样会更有效率,而且似乎我是对的。
在邻接矩阵中,a 1表示两个节点之间有一条边,例如第一行可以读为“a和b以及c之间有一个链接”。
从那里我看了你的四种类型,发现如下:
-
对于类型3,n1和n2、n1和n3之间以及n2和n3之间必须有边缘。在邻接矩阵中,我们可以通过遍历每一行(其中每一行表示一个节点及其连接,这是n1)找到它所连接的节点(这将是n2)。然后,在n2行中,我们检查所有连接的节点(这是n3),并保留n1行中有正条目的节点。例如“a,b,c”,a与b有连接。b与c有连接,a也与c有连接
-
对于类型2,它的工作原理几乎与类型3相同。但现在我们想在n1行的n3列中找到0。例如“a,b,d”。A与B有连接,B在D列中有A 1,但A没有。
-
对于类型1,我们只查看n2行,并找到n1行和n2行都有0的所有列。
-
最后,对于类型0,查看n1行中条目为0的所有列,然后检查这些行,并查找所有具有0的列。
这个代码应该适合你。对于1000个节点,我花了大约7分钟(在一台拥有i7-8565u CPU的机器上),这仍然比较慢,但与当前运行解决方案所需的几天时间相去甚远。我已经包括了你照片中的例子,这样你就可以验证结果了。您的代码生成的图形与下面显示的示例不同。代码中的示例图和邻接矩阵都引用了包含的图片。
具有1000个节点的示例使用
networkx.generators.random_graphs.fast_gnp_random_graph
是的。1000是节点数,0.1是创建边的概率,种子只是为了一致性。我已经设置了创建边的概率,因为你提到你的图是稀疏的。
networkx.linalg.graphmatrix.adjacency_matrix
:“如果要纯python邻接矩阵表示,请尝试networkx.convert.to_dict_of_dicts,它将返回字典格式,可以作为稀疏矩阵寻址。”
字典结构有
M
字典(=行),最多
米
字典嵌套在里面。注意,嵌套字典是空的,因此检查它们中的密钥的存在等价于检查上述1或0。
import time
import networkx as nx
def triads(m):
out = {0: set(), 1: set(), 2: set(), 3: set()}
nodes = list(m.keys())
for i, (n1, row) in enumerate(m.items()):
print(f"--> Row {i + 1} of {len(m.items())} <--")
# get all the connected nodes = existing keys
for n2 in row.keys():
# iterate over row of connected node
for n3 in m[n2]:
# n1 exists in this row, all 3 nodes are connected to each other = type 3
if n3 in row:
if len({n1, n2, n3}) == 3:
t = tuple(sorted((n1, n2, n3)))
out[3].add(t)
# n2 is connected to n1 and n3 but not n1 to n3 = type 2
else:
if len({n1, n2, n3}) == 3:
t = tuple(sorted((n1, n2, n3)))
out[2].add(t)
# n1 and n2 are connected, get all nodes not connected to either = type 1
for n3 in nodes:
if n3 not in row and n3 not in m[n2]:
if len({n1, n2, n3}) == 3:
t = tuple(sorted((n1, n2, n3)))
out[1].add(t)
for j, n2 in enumerate(nodes):
if n2 not in row:
# n2 not connected to n1
for n3 in nodes[j+1:]:
if n3 not in row and n3 not in m[n2]:
# n3 is not connected to n1 or n2 = type 0
if len({n1, n2, n3}) == 3:
t = tuple(sorted((n1, n2, n3)))
out[0].add(t)
return out
if __name__ == "__main__":
g = nx.Graph()
g.add_edges_from(
[("E", "D"), ("G", "F"), ("D", "B"), ("B", "A"), ("B", "C"), ("A", "C")]
)
_m = nx.convert.to_dict_of_dicts(g)
_out = triads(_m)
print(_out)
start = time.time()
g = nx.generators.fast_gnp_random_graph(1000, 0.1, seed=42)
_m = nx.convert.to_dict_of_dicts(g)
_out = triads(_m)
end = time.time() - start
print(end)