Advertisement
_who___

max

Mar 1st, 2024
525
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 3.32 KB | None | 0 0
  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