somecode

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


def add_unique_vector(vectors, selected_vectors, remaining_indices):

    # Выбираем случайный индекс из оставшихся
    new_index = np.random.choice(remaining_indices)

    # Добавляем новый выбранный вектор
    selected_vectors.append(vectors[new_index])
    remaining_indices = list(remaining_indices - new_index)

    return selected_vectors, remaining_indices


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


# Расчет энергии вершины
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_vertex_energy(vertex, vectors, k, num_nearest):
    # Вычисляем расстояния от вершины до каждого вектора
    distances = [np.linalg.norm(vertex - vector) for vector in vectors]

    # Получаем индексы векторов, отсортированных по расстоянию
    sorted_indices = np.argsort(distances)

    # Выбираем num_nearest ближайших векторов
    nearest_vectors = [vectors[i] for i in sorted_indices[:num_nearest]]

    # Вычисляем энергию вершины
    energy = 0
    for vector in nearest_vectors:
        energy += k * np.linalg.norm(vertex - vector) ** 2
    return 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


# Расчет энергии графа
def calculate_energy(
    graph,
    vectors,
    selected_vectors,
    max_vertex_energy,
    max_edge_energy,
    max_wedge_energy,
    max_energy_vertex,
    max_energy_edge,
    max_energy_wedge,
    edge_combination,
):
    # vertex_k = 0.5 # Замените на ваше значение для коэффициента аппроксимации вершин
    # edge_k = 0.5 # Замените на ваше значение для коэффициента растяжения ребер
    # wedge_k = 0.5 # Замените на ваше значение для коэффициента изгиба клиньев
    max_wedge_energy = (
        -np.inf
    )  # Инициализируем максимальную энергию клина как минус бесконечность
    max_energy_wedge = None  # Инициализируем клин с максимальной энергией как None
    edge_combination = 0
    max_vertex_energy = -np.inf
    max_edge_energy = -np.inf
    max_energy_vertex = 0
    max_energy_edge = None

    energy = 0
    for node in graph.nodes:
        vertex_energy = calculate_vertex_energy(
            selected_vectors[int(node)], vectors, vertex_k, 2
        )
        if vertex_energy > max_vertex_energy:
            max_vertex_energy = vertex_energy
            max_energy_vertex = node
        energy += vertex_energy
    for edge in graph.edges:
        edge_energy = calculate_edge_energy(edge, selected_vectors, edge_k)
        if edge_energy > max_edge_energy:
            max_edge_energy = edge_energy
            max_energy_edge = edge
        energy += edge_energy

    # Добавляем энергию клина для всех подграфов из трех вершин
    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, selected_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, selected_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, selected_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,
        max_vertex_energy,
        max_edge_energy,
        max_wedge_energy,
        max_energy_vertex,
        max_energy_edge,
        max_energy_wedge,
        edge_combination,
    )


# Расчет энергии графа
def calculate_energy1(graph, vectors, selected_vectors):
    vertex_k = 2  # Замените на ваше значение для коэффициента аппроксимации вершин
    edge_k = 1  # Замените на ваше значение для коэффициента растяжения ребер
    wedge_k = 0.25
    energy = 0
    for node in graph.nodes:
        vertex_energy = calculate_vertex_energy(
            selected_vectors[int(node)], vectors, vertex_k, 2
        )
        energy += vertex_energy
    for edge in graph.edges:
        edge_energy = calculate_edge_energy(edge, selected_vectors, edge_k)
        energy += edge_energy

    # Добавляем энергию клина для всех подграфов из трех вершин
    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, selected_vectors, wedge_k)
            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, selected_vectors, wedge_k)
            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, selected_vectors, wedge_k)
            energy += wedge_energy
    return energy


def visualize_graph(vectors, selected_vectors, G):
    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-",
        )

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


def modify_graph(
    G,
    selected_vectors,
    max_vertex_energy,
    max_edge_energy,
    max_wedge_energy,
    max_energy_wedge,
    edge_combination,
    vectors,
    remaining_indices,
):
    if max_vertex_energy >= max_edge_energy and max_vertex_energy >= max_wedge_energy:
        print("hello1")
        # Добавляем новую вершину к вершине с наибольшей энергией
        # max_energy_vertex = vertex_energies.index(max_vertex_energy)
        G.add_node(len(selected_vectors))
        G.add_edge(max_energy_vertex, len(selected_vectors))
        selected_vectors, remaining_indices = add_unique_vector(
            vectors, selected_vectors, remaining_indices
        )
        # selected_vectors.append(np.random.randint(-6, 7, 3))  # Добавляем новый вектор
    elif max_edge_energy >= max_vertex_energy and max_edge_energy >= max_wedge_energy:
        print("hello2")
        # Разбиваем ребро с наибольшей энергией новой вершиной
        # edges = list(G.edges)  # Получаем список всех ребер
        # max_energy_edge = edges[edge_energies.index(max_edge_energy)]  # Находим ребро с максимальной энергией
        G.add_node(len(selected_vectors))
        G.add_edge(max_energy_edge[0], len(selected_vectors))
        G.add_edge(max_energy_edge[1], len(selected_vectors))
        G.remove_edge(max_energy_edge[0], max_energy_edge[1])
        selected_vectors, remaining_indices = add_unique_vector(
            vectors, selected_vectors, remaining_indices
        )  # Добавляем новый вектор
    else:
        print("hello3")
        if edge_combination == 1:
            old_edge_length = np.linalg.norm(
                selected_vectors[max_energy_wedge[0]]
                - selected_vectors[max_energy_wedge[1]]
            )
            new_edge_length = np.linalg.norm(
                selected_vectors[max_energy_wedge[0]]
                - selected_vectors[max_energy_wedge[2]]
            )
            if new_edge_length < old_edge_length:
                # Удаляем старое ребро и добавляем новое
                G.remove_edge(max_energy_wedge[0], max_energy_wedge[1])
                G.add_edge(max_energy_wedge[2], max_energy_wedge[1])
            else:
                G.remove_edge(max_energy_wedge[0], max_energy_wedge[2])
                G.add_edge(max_energy_wedge[2], max_energy_wedge[1])
        elif edge_combination == 2:
            old_edge_length = np.linalg.norm(
                selected_vectors[max_energy_wedge[0]]
                - selected_vectors[max_energy_wedge[1]]
            )
            new_edge_length = np.linalg.norm(
                selected_vectors[max_energy_wedge[1]]
                - selected_vectors[max_energy_wedge[2]]
            )
            print(f"длина старого ребра: {old_edge_length}")
            print(f"длина нового ребра: {new_edge_length }")
            if new_edge_length < old_edge_length:
                # Удаляем старое ребро и добавляем новое
                G.remove_edge(max_energy_wedge[0], max_energy_wedge[1])
                G.add_edge(max_energy_wedge[0], max_energy_wedge[2])
            else:
                G.remove_edge(max_energy_wedge[1], max_energy_wedge[2])
                G.add_edge(max_energy_wedge[0], max_energy_wedge[2])
        elif edge_combination == 3:
            old_edge_length = np.linalg.norm(
                selected_vectors[max_energy_wedge[0]]
                - selected_vectors[max_energy_wedge[2]]
            )
            new_edge_length = np.linalg.norm(
                selected_vectors[max_energy_wedge[1]]
                - selected_vectors[max_energy_wedge[2]]
            )
            if new_edge_length < old_edge_length:
                # Удаляем старое ребро и добавляем новое
                G.remove_edge(max_energy_wedge[0], max_energy_wedge[2])
                G.add_edge(max_energy_wedge[0], max_energy_wedge[1])
            else:
                G.remove_edge(max_energy_wedge[2], max_energy_wedge[1])
                G.add_edge(max_energy_wedge[0], max_energy_wedge[1])
        # print(max_energy_wedge[0])
        # print(max_energy_wedge[1])
        # print(max_energy_wedge[2])
    return G, selected_vectors, remaining_indices


# for edges in G.edges:
# print(edges)


def calculate_psi(g, NP, lambda_):
    return ((g - 1) * NP + 1) ** (1 / lambda_)


def calculate_probabilities(vectors, selected_vectors, k, num_nearest, g, NP, lambda_):
    # Вычисляем psi
    psi_g = calculate_psi(g, NP, lambda_)

    # Вычисляем энергии для всех векторов
    energies = [
        calculate_vertex_energy(vertex, vectors, k, num_nearest) ** psi_g
        for vertex in selected_vectors
    ]

    # Вычисляем сумму энергий
    sum_energies = sum(energies)

    # Вычисляем вероятности
    probabilities = [energy / sum_energies for energy in energies]
    # print(probabilities)
    return probabilities


def select_support_vector(vectors, selected_vectors, k, num_nearest, g, NP, lambda_):
    # Вычисляем вероятности
    probabilities = calculate_probabilities(
        vectors, selected_vectors, k, num_nearest, g, NP, lambda_
    )

    # Выбираем опорный вектор на основе вероятностей
    id = np.random.choice(len(selected_vectors), p=probabilities)
    support_vector = selected_vectors[id]

    return support_vector


def calculate_A(x_min, x_max, x_r, e):
    return (np.arctan((x_max - x_r) / e) - np.arctan((x_min - x_r) / e)) ** -1


def calculate_e(i, g, NP):
    return 1 / ((g - 1) * NP + i + 1) ** (1 / 6)


def generate_potential_offspring(x_min, x_max, x_r, e, A):
    return x_r + e * np.tan((np.random.rand() - 0.5) * A)


def crossover(selected_vectors, support_vector, potential_offspring, q):
    # Создаем mutant_vectors, равный по размеру selected_vectors
    mutant_vectors = np.copy(selected_vectors)

    # Выбираем случайные q индексов
    random_indices = np.random.choice(len(selected_vectors), q, replace=False)

    # Заменяем случайные q векторов mutant_vectors на соответствующие векторы из selected_vectors
    for i in random_indices:
        mutant_vectors[i] = selected_vectors[i]

    # Для оставшихся векторов
    for l in range(len(selected_vectors)):
        if l not in random_indices:
            # Выбираем случайное число
            p = np.random.rand()

            # Вычисляем CR_{l,g}
            CR_lg = 0.9 if p > 0.1 else p

            # Для каждой координаты j в векторе
            for j in range(3):
                # Применяем операцию в зависимости от rand(0,1) и CR_{l,g}
                if np.random.rand() < 1.0 - CR_lg:
                    mutant_vectors[l, j] = potential_offspring[l, j]

    # Заменяем вектор в mutant_vectors, соответствующий support_vector в selected_vectors, на support_vector
    for i in range(len(selected_vectors)):
        if np.array_equal(selected_vectors[i], support_vector):
            mutant_vectors[i] = support_vector

    return mutant_vectors


def generate_offspring(selected_vectors, support_vector, g, NP, lambda_):
    # Вычисляем x_min и x_max для каждой координаты
    x_min = np.min(selected_vectors, axis=0)
    x_max = np.max(selected_vectors, axis=0)

    # Создаем список для хранения потенциальных потомков
    potential_offspring = []

    # Для каждого вектора в selected_vectors
    for i in range(NP):
        # Для каждой координаты в векторе
        for j in range(3):
            # Вычисляем x_r, e и A
            x_r = support_vector[j]
            e = calculate_e(i, g, NP)
            A = calculate_A(x_min[j], x_max[j], x_r, e)

            # Генерируем потенциального потомка
            x_star = generate_potential_offspring(x_min[j], x_max[j], x_r, e, A)

            # Добавляем потенциального потомка в список
            potential_offspring.append(x_star)

    # Преобразуем список потенциальных потомков в массив NumPy
    potential_offspring = np.array(potential_offspring).reshape(NP, 3)

    return potential_offspring


def selection(G, vectors, selected_vectors, mutant_vectors, energy):
    # Для каждого вектора в selected_vectors
    for i in range(len(selected_vectors)):
        vec = selected_vectors
        vec[i] = mutant_vectors[i]
        en = calculate_energy1(G, vectors, vec)
        # print(f'Энергия главная: {energy}')
        # print(f'Энергия пересчитанная: {en}')
        # Если энергия mutant_vectors[i] меньше, чем энергия selected_vectors[i]
        if en < energy:
            # Заменяем selected_vectors[i] на mutant_vectors[i]
            selected_vectors[i] = mutant_vectors[i]

    return selected_vectors


def data():
    n = 12

    # Создаем случайную последовательность n-2 от 0 до n-1
    prufer_sequence = np.random.randint(0, n, n - 2)

    # Восстанавливаем дерево по коду Прюфера
    G1 = nx.from_prufer_sequence(prufer_sequence)

    # Укладываем вершины графа на плоскость методом Фрухтермана-Рейнгольда
    pos = fruchterman_reingold_layout(G1, dim=3)

    # Берем точки на ребрах графа
    edge_points = [pos[node] for node in G1.nodes]
    # [(pos[edge[0]] + pos[edge[1]]) / 2 for edge in G.edges]

    # Смещаем каждую точку на случайный вектор с нормальным распределением
    vectors = []
    for point in edge_points:
        for _ in range(5):  # Создаем три смещенные точки для каждой точки на ребре
            vectors.append(point + np.random.normal(size=3) * 0.05)
    return vectors


vertex_k = 2  # Замените на ваше значение для коэффициента аппроксимации вершин
edge_k = 1  # Замените на ваше значение для коэффициента растяжения ребер
wedge_k = 0.25  # Замените на ваше значение для коэффициента изгиба клиньев
np.random.seed(8)

vectors = []
vectors = data()

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


# Выбираем три случайные точки (вектора)
indices = np.random.choice(len(vectors), 3, replace=False)
selected_vectors = [vectors[i] for i in indices]
# print(indices)
# Создаем список всех индексов
all_indices = set(range(len(vectors)))

# Удаляем уже выбранные индексы
remaining_indices = list(all_indices - set(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

# Проверяем, является ли граф связным
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])
# print(f'входные данные: {selected_vectors}')
# visualize_graph(vectors, selected_vectors, G)


# global max_wedge_energy

# print(max_vertex_energy)

(
    energy,
    max_vertex_energy,
    max_edge_energy,
    max_wedge_energy,
    max_energy_vertex,
    max_energy_edge,
    max_energy_wedge,
    edge_combination,
) = calculate_energy(
    G,
    vectors,
    selected_vectors,
    max_vertex_energy,
    max_edge_energy,
    max_wedge_energy,
    max_energy_vertex,
    max_energy_edge,
    max_energy_wedge,
    edge_combination,
)
print(f"Энергия графа: {energy}")
print(f"Энергия точки: {max_vertex_energy}")
print(f"Энергия ребра: {max_edge_energy}")
print(f"Энергия клина: {max_wedge_energy}")
print(f"Энергия комбинация клина: {edge_combination}")

# visualize_graph(vectors, selected_vectors, G)
# remaining_indices=modify_graph(G, selected_vectors, max_vertex_energy, max_edge_energy, max_wedge_energy, max_energy_wedge, edge_combination,vectors,remaining_indices)
# visualize_graph(vectors, selected_vectors, G)
NP = 10
# Для каждой итерации g от 1 до NP
# Для каждой итерации от 0 до 10
for iteration in range(5):
    # Для каждой итерации g от 1 до NP
    for g in range(1, NP + 1):
        # Выбираем опорный вектор
        support_vector = select_support_vector(
            vectors, selected_vectors, vertex_k, 2, g, NP, 4
        )

        # Генерируем потенциальных потомков
        potential_offspring = generate_offspring(
            selected_vectors, support_vector, g, NP, 1
        )

        # Выполняем операцию кроссовера
        mutant_vectors = crossover(
            selected_vectors,
            support_vector,
            potential_offspring,
            int(len(selected_vectors) / 3),
        )

        # Выполняем операцию отбора
        selected_vectors = selection(
            G, vectors, selected_vectors, mutant_vectors, energy
        )
    G, selected_vectors, remaining_indices = modify_graph(
        G,
        selected_vectors,
        max_vertex_energy,
        max_edge_energy,
        max_wedge_energy,
        max_energy_wedge,
        edge_combination,
        vectors,
        remaining_indices,
    )
    # visualize_graph(vectors, selected_vectors, G)
    (
        energy,
        max_vertex_energy,
        max_edge_energy,
        max_wedge_energy,
        max_energy_vertex,
        max_energy_edge,
        max_energy_wedge,
        edge_combination,
    ) = calculate_energy(
        G,
        vectors,
        selected_vectors,
        max_vertex_energy,
        max_edge_energy,
        max_wedge_energy,
        max_energy_vertex,
        max_energy_edge,
        max_energy_wedge,
        edge_combination,
    )
    print(f"Энергия графа: {energy}")
    print(f"Энергия точки: {max_vertex_energy}")
    print(f"Энергия ребра: {max_edge_energy}")
    print(f"Энергия клина: {max_wedge_energy}")
    print(f"Энергия комбинация клина: {edge_combination}")
visualize_graph(vectors, selected_vectors, G)