minimal spanning tree

from scipy.optimize import linprog
import numpy as np
import networkx as nx
import matplotlib.pyplot as plt
np.set_printoptions(threshold=np.inf)

def random_matrix(N, max_value):
    graph = np.zeros((N, N))
    for i in range(N):
        edges = np.random.choice(np.delete(np.arange(N), i), 2, replace=False)
        for j in edges:
            graph[i, j] = np.random.randint(1, 100)

    return graph

def visualize_overlapping_graphs(graph1_array, graph2_array, node_color='pink', edge_color1='lightgray', edge_color2='black'):
  graph1 = nx.from_numpy_array(graph1_array)
  graph2 = nx.from_numpy_array(graph2_array)
  combined_graph = nx.compose(graph1, graph2)
  pos = nx.circular_layout(combined_graph, scale=0.8)  # Круговое расположение
  nx.draw(combined_graph, pos, node_color=node_color, with_labels=False)
  edges1 = list(graph1.edges())
  nx.draw_networkx_edges(combined_graph, pos, edgelist=edges1, edge_color=edge_color1, width=2)
  edges2 = list(graph2.edges())
  nx.draw_networkx_edges(combined_graph, pos, edgelist=edges2, edge_color=edge_color2, width=1)
  plt.show()

def visualize_overlapping_oriented_circular_graphs(graph1_array, graph2_array, node_color='pink', edge_color1='lightgray', edge_color2='black'):
    from scipy.optimize import linprog
    import numpy as np
    import networkx as nx
    import matplotlib.pyplot as plt
    np.set_printoptions(threshold=np.inf)

    def random_matrix(N, max_value):
        graph = np.zeros((N, N))
        for i in range(N):
            edges = np.random.choice(np.delete(np.arange(N), i), 2, replace=False)
            for j in edges:
                graph[i, j] = np.random.randint(1, 100)

        return graph

    def visualize_overlapping_graphs(graph1_array, graph2_array, node_color='pink', edge_color1='lightgray',
                                     edge_color2='black'):
        graph1 = nx.from_numpy_array(graph1_array)
        graph2 = nx.from_numpy_array(graph2_array)
        combined_graph = nx.compose(graph1, graph2)
        pos = nx.circular_layout(combined_graph, scale=0.8)  # Круговое расположение
        nx.draw(combined_graph, pos, node_color=node_color, with_labels=False)
        edges1 = list(graph1.edges())
        nx.draw_networkx_edges(combined_graph, pos, edgelist=edges1, edge_color=edge_color1, width=2)
        edges2 = list(graph2.edges())
        nx.draw_networkx_edges(combined_graph, pos, edgelist=edges2, edge_color=edge_color2, width=1)
        plt.show()

    def visualize_overlapping_oriented_circular_graphs(graph1_array, graph2_array, node_color='pink',
                                                       edge_color1='lightgray', edge_color2='black'):
        graph1 = nx.from_numpy_array(graph1_array, create_using=nx.DiGraph)
        graph2 = nx.from_numpy_array(graph2_array, create_using=nx.DiGraph)
        combined_graph = nx.compose(graph1, graph2)
        pos = nx.circular_layout(combined_graph)  # Расположение с фиксированным seed
        nx.draw(graph1, pos, node_color=node_color, with_labels=False, arrows=True)  # Убираем номера вершин
        edges1 = list(graph1.edges())
        nx.draw_networkx_edges(graph2, pos, edgelist=edges1, edge_color=edge_color1, width=2)
        edges2 = list(graph2.edges())
        nx.draw_networkx_edges(combined_graph, pos, edgelist=edges2, edge_color=edge_color2, width=1)
        plt.show()

    N = 17

    d = random_matrix(N, 100)

    c = -d.flatten()

    b_eq = np.ones(N)
    b_ub = np.ones(N)

    A_eq = np.zeros((N, N ** 2))

    for i in range(N):
        a = np.zeros((N, N))
        for j in range(N):
            if d[i][j] != 0:
                a[i][j] = 1
        a = a.flatten()
        A_eq[i] = a

    A_ub = np.zeros((N, N * N))
    for i in range(N):
        for j in range(N):
            if d[i][j] != 0:
                A_ub[i][j + i * N] = 1

    b_l = np.zeros(N ** 2)
    b_u = d.flatten()
    bounds = list(zip(b_l, b_u))

    res = linprog(c, b_ub=b_ub, bounds=bounds, A_ub=A_ub, A_eq=A_eq, b_eq=b_eq)
    result = np.reshape(res.x, (N, N)) * d

    visualize_overlapping_graphs(d, result)
    print(result)

    M = 500

    D = np.random.randint(50, 100, size=(N, N))
    np.fill_diagonal(D, 0)
    print(D)

    c2 = np.concatenate((-D.flatten(), np.zeros(N * 2)))

    b_eq2 = np.ones(N)
    b_ub2 = np.array([M] * N)
    print(b_ub2)
    A_eq2 = np.zeros((N, N ** 2 + 2 * N))
    for i in range(N):
        a = np.zeros((N, N))
        zh = np.zeros(2 * N)
        for j in range(N):
            if D[i][j] != 0:
                a[i][j] = 1
                zh[N + j] = 1
        zh[i] = 1
        a = np.concatenate((a.flatten(), zh))
        A_eq2[i] = a
    np.savetxt("A_eq.txt", A_eq2, fmt='%d')

    A_ub2 = np.zeros((N, N * N + 2 * N))
    for i in range(N):
        for j in range(N):
            if D[i][j] != 0:
                A_ub2[i][j + i * N] = -1
            A_ub2[i][j + N ** 2 + N] = -M
    np.savetxt("A_ub.txt", A_ub2, fmt='%d')

    b_l2 = np.zeros(N ** 2 + 2 * N)
    b_u2 = np.concatenate((D.flatten(), np.ones(2 * N)))
    bounds2 = list(zip(b_l2, b_u2))
    print(bounds2)

    res = linprog(c=c2, b_ub=b_ub2, bounds=bounds2, A_ub=A_ub2, A_eq=A_eq2, b_eq=b_eq2)
    result = np.reshape(res.x[:N * N], (N, N)) * D

    print(result)
    visualize_overlapping_oriented_circular_graphs(D, result)

N = 17

d = random_matrix(N, 100)

c = -d.flatten()

b_eq = np.ones(N)
b_ub = np.ones(N)

A_eq = np.zeros((N, N**2))

for i in range(N):
    a = np.zeros((N, N))
    for j in range(N):
        if d[i][j] != 0:
            a[i][j] = 1
    a = a.flatten()
    A_eq[i] = a

A_ub = np.zeros((N, N*N))
for i in range(N):
    for j in range(N):
        if d[i][j] != 0:
            A_ub[i][j+i*N] = 1

b_l = np.zeros(N**2)
b_u = d.flatten()
bounds = list(zip(b_l, b_u))

res = linprog(c, b_ub=b_ub, bounds=bounds, A_ub=A_ub, A_eq=A_eq, b_eq=b_eq)
result = np.reshape(res.x, (N, N)) * d

visualize_overlapping_graphs(d, result)
print(result)


M = 500

D = np.random.randint(50, 100, size=(N, N))
np.fill_diagonal(D, 0)
print(D)

c2 = np.concatenate((-D.flatten(), np.zeros(N*2)))

b_eq2 = np.ones(N)
b_ub2 = np.array([M]*N)
print(b_ub2)
A_eq2 = np.zeros((N, N**2 + 2*N))
for i in range(N):
    a = np.zeros((N, N))
    zh = np.zeros(2*N)
    for j in range(N):
        if D[i][j] != 0:
            a[i][j] = 1
            zh[N + j] = 1
    zh[i] = 1
    a = np.concatenate((a.flatten(), zh))
    A_eq2[i] = a
np.savetxt("A_eq.txt", A_eq2, fmt='%d')

A_ub2 = np.zeros((N, N*N+2*N))
for i in range(N):
    for j in range(N):
        if D[i][j] != 0:
            A_ub2[i][j+i*N] = -1
        A_ub2[i][j + N**2+N] = -M
np.savetxt("A_ub.txt", A_ub2, fmt='%d')

b_l2 = np.zeros(N**2 + 2*N)
b_u2 = np.concatenate((D.flatten(), np.ones(2*N)))
bounds2 = list(zip(b_l2, b_u2))
print(bounds2)

res = linprog(c=c2, b_ub=b_ub2, bounds=bounds2, A_ub=A_ub2, A_eq=A_eq2, b_eq=b_eq2)
result = np.reshape(res.x[:N*N], (N, N)) * D

print(result)
visualize_overlapping_oriented_circular_graphs(D, result)