Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement