在三角形顶点列表中查找连接的组件

Question

考虑两个图，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中出现了，但我无法翻译

我的作品在这个post中找到

Answer 1

从您的面生成图形非常简单：每个三元组生成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]]