#функция, которая получает подграф из матрицы смежности matrix: numpy array, solution:list
def subgraph(matrix, solution):
    #лямбда для поиска индексов 0 и 1
    get_indices = lambda x, xs: [i for (y, i) in zip(xs, range(len(xs))) if x == y]
    #индексы на которых 0 и 1
    indices_zero = get_indices(0,solution)
    indices_one = get_indices(1,solution)
    #переводим матрицу смежности в list
    matrix = matrix.tolist()
#     print (indices_zero, indices_one)
    size = len(matrix)
    shape = len(solution)
    # вставляем нули в строках матрицы
    for i in range (0, size):
        for index in indices_zero:
            matrix[i][index] = 0
    # вставляем нулевые строки
    for index in indices_zero:
        matrix[index] = [0]*size
    return np.array(matrix)
# находим, сколько поимели с графа
def profit(adjacency_matrix):
    # инициализируем нулем
    profit = 0
    # находим размер матрицы смежности
    m = adjacency_matrix.shape[0]
    # идём по верхнему треугольнику
    for i in range (0, m):
        for j in range (i+1,m):
            if i == j:
                # если это вершина, то прибавляем её вес на коэффициент
                profit+=0.5*adjacency_matrix[i][j]
            else:
                # если ребро, то уменьшаем на коэффициент* вес ребра
                profit-=0.5*adjacency_matrix[i][j]
    return profit
# проверяем, удовлетворяет ли граф бюджетным ограничениям
def check_budget(adjacency_matrix, budget_bound):
    costs = 0
    m = adjacency_matrix.shape[0]
    for i in range (0, m):
        for j in range (i+1,m):
            if i != j:
                costs+=adjacency_matrix[i][j]
            # вершины не считаем, считаем косты по рёбрам
    if costs <= budget_bound:
        return True
    return False
import itertools
n = 5
#генерим всевозможные комбинации вершин
lst = [list(i) for i in itertools.product([0, 1], repeat=n)]
n = 5
subgraphs = [1]*2**n
graph = Graph(n, 5 ,5)
adj_matr = graph.adjacency_matrix()
vertices = graph.vertices()
# в цикле проходим по всем кандидатам и записываем, какой профит поимели и удовлетворяет ли бюджетным ограничениям
for i in range (0, n):
    adj_matr[i][i] = vertices[0][i]
for i in range(0, 2**n):
    cand = subgraph(adj_matr,lst[i])
#     visualize_graph(cand,vertices)
    subgraphs[i] = (profit(cand), check_budget(cand, 20))
maximum = -np.inf
indices = []
for i in range(0, 2**n):
    if subgraphs[i][1] == True and subgraphs[i][0] >= maximum:
        indices.append(i)
        maximum = subgraphs[i][0]