Advertisement

# max

Mar 1st, 2024
525
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. import numpy as np
2. from scipy.optimize import linprog
3. import networkx as nx
4. import matplotlib.pyplot as plt
5.
6.
7. def max_flow(graph, source, sink):
8.     # Создаем матрицу инцидентности
9.     num_nodes = len(graph)
10.     num_edges = sum(len(edges) for edges in graph.values())
11.     A_eq = np.zeros((num_nodes + num_edges, num_edges))
12.     b_eq = np.zeros(num_nodes + num_edges)
13.     c = np.zeros(num_edges)
14.     edge_index = 0
15.
16.     for i, node in enumerate(graph):
17.         for neighbor, capacity in graph[node].items():
18.             if node != source and node != sink:
19.                 A_eq[i, edge_index] = 1
20.                 A_eq[num_nodes + edge_index, edge_index] = -1
21.                 b_eq[i] = 0
22.                 c[edge_index] = -1
23.                 edge_index += 1
24.             if node == source:
25.                 A_eq[num_nodes + edge_index, edge_index] = -1
26.                 b_eq[num_nodes + edge_index] = -capacity
27.                 c[edge_index] = -1
28.                 edge_index += 1
29.             elif node == sink:
30.                 A_eq[num_nodes + edge_index, edge_index] = 1
31.                 b_eq[num_nodes + edge_index] = capacity
32.                 c[edge_index] = -1
33.                 edge_index += 1
34.
35.     # Решаем задачу линейного программирования
36.     res = linprog(c, A_eq=A_eq, b_eq=b_eq)
37.
38.     # Создаем словарь потока
39.     flow = {}
40.     for node in graph:
41.         flow[node] = {}
42.
43.     # Заполняем значениями потока
44.     edge_index = 0
45.     for i, node in enumerate(graph):
46.         for neighbor, _ in graph[node].items():
47.             flow[node][neighbor] = res.x[edge_index]
48.             edge_index += 1
49.
50.     return flow
51.
52. def visualize_flow(graph, flow):
53.     G = nx.DiGraph()
54.     for node, neighbors in graph.items():
55.         for neighbor, capacity in neighbors.items():
56.             G.add_edge(node, neighbor, capacity=capacity)
57.
58.     pos = nx.spring_layout(G)
59.
60.     plt.figure(figsize=(10, 5))
61.
62.     # Рисуем исходный граф
63.     plt.subplot(1, 2, 1)
64.     nx.draw(G, pos, with_labels=True, node_color='lightblue', node_size=2000, font_size=10)
65.     plt.title('Original Graph')
66.
67.     # Рисуем граф с потоком
68.     plt.subplot(1, 2, 2)
69.     for node, neighbors in graph.items():
70.         for neighbor, capacity in neighbors.items():
71.             flow_value = flow[node][neighbor]
72.             nx.draw_networkx_edge_labels(G, pos, edge_labels={(node, neighbor): str(flow_value)}, label_pos=0.3)
73.
74.     nx.draw(G, pos, with_labels=True, node_color='lightblue', node_size=2000, font_size=10)
75.     plt.title('Graph with Max Flow')
76.
77.     plt.show()
78.
79.
80. # Пример графа для тестирования
81. graph = {
82.     'A': {'B': 10, 'C': 5},
83.     'B': {'D': 15},
84.     'C': {'D': 10},
85.     'D': {}
86. }
87.
88. source = 'A'
89. sink = 'D'
90.
91. # Рассчитываем максимальный поток
92. flow = max_flow(graph, source, sink)
93.
94. # Создаем словарь потока для визуализации
95. flow_dict = {}
96. nodes = list(graph.keys())
97. edge_index = 0
98. for i, node in enumerate(nodes):
99.     flow_dict[node] = {}
100.     for neighbor, _ in graph[node].items():
101.         flow_dict[node][neighbor] = flow[node][neighbor]
102.
103. # Визуализируем поток
104. visualize_flow(graph, flow_dict)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement