Найти связанные компоненты в списке вершин треугольника - PullRequest
Новая
       54

Найти связанные компоненты в списке вершин треугольника

1 голос
/ 04 мая 2020

Рассмотрим два графика: 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, но я не могу перевести.

Моя работа находится в этой публикации .

1 Ответ

1 голос
/ 04 мая 2020

Создание графика из ваших лиц довольно просто: каждый триплет дает 3 ребра, соответствующие всем комбинациям членов триплета. Тогда это просто вопрос создания экземпляра объекта networkx Graph и вызова 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]]
...