考虑两个图,G1=(V1,E1(,G2=(V2,E2(
V1 = {1,2,3,4,5,6}
V2 = {7,8,9,10,11,12}
在空间中,这些顶点由三角形面连接(每个面有三个顶点(
F1 = [[ 2, 1, 0], [ 0, 3, 2], [ 1, 4, 0], [ 0, 4, 3], [ 5, 1, 2], [ 3, 5, 2], [ 5, 4, 1], [ 4, 5, 3]]
F2 = [[ 8, 7, 6], [ 6, 9, 8], [ 7, 10, 6], [ 6, 10, 9], [11, 7, 8], [ 9, 11, 8], [11, 10, 7], [10, 11, 9]]
以上就是我想要找到的。如果我们得到整个人脸阵列:
faces = [[ 2, 1, 0], [ 0, 3, 2], [ 1, 4, 0], [ 0, 4, 3], [ 5, 1, 2], [ 3, 5, 2],
[ 5, 4, 1], [ 4, 5, 3], [ 8, 7, 6], [ 6, 9, 8], [ 7, 10, 6], [ 6, 10, 9],
[11, 7, 8], [ 9, 11, 8], [11, 10, 7], [10, 11, 9]]
我们能找到连接的组件,并将其分离为F1
和F2
吗?
这个问题的一个版本已经在Mathematica中解决了,但我无法翻译。
我的作品就在这篇文章里。
从你的脸上制作一个图非常简单:每个三元组产生3条边,对应于三元组成员的所有组合。然后只需要实例化networkxGraph
对象并调用networkx.algorithms.components.connected_components
。
#!/usr/bin/env python
"""
Given a list of triangles, find the connected components.
https://stackoverflow.com/q/61584283/2912349
"""
import itertools
import networkx as nx
faces = [[ 2, 1, 0], [ 0, 3, 2], [ 1, 4, 0], [ 0, 4, 3], [ 5, 1, 2], [ 3, 5, 2],
[ 5, 4, 1], [ 4, 5, 3], [ 8, 7, 6], [ 6, 9, 8], [ 7, 10, 6], [ 6, 10, 9],
[11, 7, 8], [ 9, 11, 8], [11, 10, 7], [10, 11, 9]]
#create graph
edges = []
for face in faces:
edges.extend(list(itertools.combinations(face, 2)))
g = nx.from_edgelist(edges)
# compute connected components and print results
components = list(nx.algorithms.components.connected_components(g))
for component in components:
print(component)
# {0, 1, 2, 3, 4, 5}
# {6, 7, 8, 9, 10, 11}
# separate faces by component
component_to_faces = dict()
for component in components:
component_to_faces[tuple(component)] = [face for face in faces if set(face) <= component] # <= operator tests for subset relation
for component, component_faces in component_to_faces.items():
print(component, component_faces)
# (0, 1, 2, 3, 4, 5) [[2, 1, 0], [0, 3, 2], [1, 4, 0], [0, 4, 3], [5, 1, 2], [3, 5, 2], [5, 4, 1], [4, 5, 3]]
# (6, 7, 8, 9, 10, 11) [[8, 7, 6], [6, 9, 8], [7, 10, 6], [6, 10, 9], [11, 7, 8], [9, 11, 8], [11, 10, 7], [10, 11, 9]]