бмо графы 1

import numpy as np
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D
import networkx as nx
from scipy.spatial import distance
from scipy.spatial import distance_matrix
import itertools


vertex_k = 100 # Замените на ваше значение для коэффициента аппроксимации вершин
edge_k =1  # Замените на ваше значение для коэффициента растяжения ребер
wedge_k = 1 # Замените на ваше значение для коэффициента изгиба клиньев
np.random.seed(12)
vectors = [np.random.randint(-6, 7, 3) for _ in range(100)]


# Выбираем три случайные точки (вектора)
indices = np.random.choice(len(vectors),10, replace=False)
selected_vectors = [vectors[i] for i in indices]
#print(indices)

# Вычисляем матрицу расстояний между всеми векторами
distances = distance_matrix(selected_vectors, selected_vectors)

# Заменяем диагональные элементы на бесконечность
np.fill_diagonal(distances, np.inf)
#print(distances)
# Создаем список пар (расстояние, вектор)
dist_vector_pairs = [(np.min(dist), vec) for dist, vec in zip(distances, selected_vectors)]
#print(dist_vector_pairs)
# Сортируем список пар по расстоянию
dist_vector_pairs.sort(key=lambda x: x[0])
#print(dist_vector_pairs)
# Извлекаем отсортированные векторы
sorted_vectors = [pair[1] for pair in dist_vector_pairs]
#print(sorted_vectors)
selected_vectors =sorted_vectors
# Создаем граф
# Вычисляем матрицу расстояний между всеми векторами
distances = distance_matrix(selected_vectors, selected_vectors)
# Заменяем диагональные элементы на бесконечность
np.fill_diagonal(distances, np.inf)
#print(distances)
G = nx.Graph()

#Добавляем вершины в граф
for i in range(len(selected_vectors)):
    G.add_node(i)

visited = set()  # Создаем множество для хранения посещенных вершин

for i in range(len(selected_vectors)):
    # Находим ближайшую вершину к текущей вершине
    nearest_vertex = np.argmin(distances[i])
    print("ближайшие вершины")
    print(i, nearest_vertex)

    # Проверяем, была ли уже посещена ближайшая вершина
    if i not in visited:
        # Если вершина не была посещена, добавляем ребро
        G.add_edge(i, nearest_vertex)
        # Добавляем вершину в множество посещенных вершин
        visited.add(nearest_vertex)
        print(visited)
    else:
        # Если вершина уже была посещена, пропускаем ее
        print("пропуск вершины")
        print(i, nearest_vertex)
        continue


def DFS(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    for next_node in set(graph[start]) - visited:
        DFS(graph, next_node, visited)
    return visited

# Проверяем, является ли граф связным
connected = len(DFS(G, 0)) == len(G)

if not connected:
    # Граф не связный, находим несвязанные компоненты
    components = [list(c) for c in nx.connected_components(G)]
    # Соединяем компоненты, добавляя ребра между их вершинами
    for i in range(len(components) - 1):
        G.add_edge(components[i][0], components[i+1][0])




# Расчет энергии вершины
def calculate_vertex_energy(vertex, vectors, k):
    energy = 0
    for vector in vectors:
        energy += np.linalg.norm(vertex - vector)**2
    return k * energy

# Расчет энергии ребра
def calculate_edge_energy(edge, vectors, k):
    v1, v2 = vectors[edge[0]], vectors[edge[1]]
    return k * np.linalg.norm(v1 - v2)**2

# Расчет энергии клина
def calculate_wedge_energy(wedge, vectors, k):
    v1, v2, v3 = vectors[wedge[0]], vectors[wedge[1]], vectors[wedge[2]]
    return k * np.linalg.norm(v1 + v3 - 2*v2)**2

#global max_wedge_energy
#max_wedge_energy=-np.inf# Инициализируем максимальную энергию клина как минус бесконечность
max_energy_wedge = None  # Инициализируем клин с максимальной энергией как None
edge_combination=0

# Расчет энергии графа
def calculate_energy(graph, vectors):
    #vertex_k = 0.5 # Замените на ваше значение для коэффициента аппроксимации вершин
    #edge_k = 0.5 # Замените на ваше значение для коэффициента растяжения ребер
    #wedge_k = 0.5 # Замените на ваше значение для коэффициента изгиба клиньев
    global max_wedge_energy
    max_wedge_energy=-np.inf

    energy = 0
    for node in graph.nodes:
        energy += calculate_vertex_energy(vectors[int(node)], vectors, vertex_k)
    for edge in graph.edges:
        energy += calculate_edge_energy(edge, vectors, edge_k)

    # Добавляем энергию клина для всех подграфов из трех вершин
    for nodes in itertools.combinations(graph.nodes, 3):
        #print(nodes)
        if graph.has_edge(nodes[0], nodes[1]) and graph.has_edge(nodes[0], nodes[2]):
            wedge_energy = calculate_wedge_energy(nodes, vectors, wedge_k)
            #print("Энергия клина:")
            #print(p1)
            if wedge_energy > max_wedge_energy:
                max_wedge_energy = wedge_energy
                max_energy_wedge = nodes
                edge_combination=1
            energy += wedge_energy
        elif graph.has_edge(nodes[0], nodes[1]) and graph.has_edge(nodes[1], nodes[2]):
            wedge_energy = calculate_wedge_energy(nodes, vectors, wedge_k)
            if wedge_energy > max_wedge_energy:
                max_wedge_energy = wedge_energy
                max_energy_wedge = nodes
                edge_combination=2
                #print("Энергия клина:")
            #print(p1)
            energy +=wedge_energy
        elif graph.has_edge(nodes[0], nodes[2]) and graph.has_edge(nodes[1], nodes[2]):
            wedge_energy = calculate_wedge_energy(nodes, vectors, wedge_k)
            if wedge_energy > max_wedge_energy:
                max_wedge_energy = wedge_energy
                max_energy_wedge = nodes
                edge_combination=3
            #print("Энергия клина:")
            #print(p1)
            energy += wedge_energy
    return energy

energy = calculate_energy(G, selected_vectors)
print(f'Энергия графа: {energy}')


# Визуализация проекции графа и векторов
fig = plt.figure()
ax = fig.add_subplot(111, projection='3d')

# Отображаем все векторы на графике
for vector in vectors:
    ax.scatter(vector[0], vector[1], vector[2], color='b')

# Отображаем выбранные векторы на графике
for vector in selected_vectors:
    ax.scatter(vector[0], vector[1], vector[2], color='r')

# Добавляем ребра между вершинами
for edge in G.edges:
    ax.plot([selected_vectors[edge[0]][0], selected_vectors[edge[1]][0]],
            [selected_vectors[edge[0]][1], selected_vectors[edge[1]][1]],
            [selected_vectors[edge[0]][2], selected_vectors[edge[1]][2]], 'r-')
#for edges in G.edges:
#    print(edges)

# Добавляем оси
ax.set_xlabel('X')
ax.set_ylabel('Y')
ax.set_zlabel('Z')
plt.show()