max?

import numpy as np
from scipy.optimize import linprog
import matplotlib.pyplot as plt
import networkx as nx

# Define the directed graph representing the network flow
G = nx.DiGraph()
G.add_nodes_from(["S", "A", "B", "C", "D", "T"])
edges = [("S", "A", 3), ("S", "B", 2), ("A", "C", 3), ("A", "D", 2),
         ("B", "C", 1), ("B", "D", 1), ("C", "T", 3), ("D", "T", 2)]
for u, v, w in edges:
    G.add_edge(u, v, capacity=w)

# Visualize the original graph
plt.figure()
pos = nx.circular_layout(G)
nx.draw(G, pos, with_labels=True, node_size=1000, node_color='skyblue')
nx.draw_networkx_edge_labels(G, pos, edge_labels={(u, v): str(d['capacity']) for u, v, d in G.edges(data=True)})
plt.title("Original Network Flow Graph")
plt.show()

# Linear programming problem setup
num_edges = len(G.edges)
num_nodes = len(G.nodes)
c = np.zeros(num_edges)  # Initialize cost function
bounds = [(0, G[u][v]['capacity']) for u, v in G.edges]  # Flow bounds are from 0 to edge capacity

node_indices = {node: i for i, node in enumerate(G.nodes)}
A_ub = np.zeros((num_nodes - 2, num_edges))  # One row for each node except source and sink
b_ub = np.zeros(num_nodes - 2)

# Set up the optimization problem
for i, ((u, v), w) in enumerate(G.edges.items()):
    if u == 'S':
        c[i] = -1  # Maximize flow from the source
    elif v == 'T':
        c[i] = 1  # Minimize flow to the sink

# Flow conservation constraints for nodes except source and sink
for i, node in enumerate(node for node in G.nodes if node not in ('S', 'T')):
    for j, (u, v) in enumerate(G.edges()):
        if v == node:
            A_ub[i, j] = -1  # Outgoing flow decreases
        if u == node:
            A_ub[i, j] = 1   # Incoming flow increases
    b_ub[i] = 0  # Flow conservation for nodes except source and sink

# Solve the linear programming problem
result = linprog(c, A_ub=A_ub, b_ub=b_ub, bounds=bounds, method='highs')
max_flow = -result.fun  # Negate because we minimized the negative flow

# Update graph with flow values
flow_values = result.x
for i, (u, v) in enumerate(G.edges()):
    G[u][v]['flow'] = flow_values[i]

# Visualize the solution graph with flow values
plt.figure()
plt.title("Optimal Flow in the Network")
nx.draw(G, pos, with_labels=True, node_size=1000, node_color='lightgreen')
nx.draw_networkx_edge_labels(G, pos, edge_labels={(u, v): f"{G[u][v]['flow']}/{G[u][v]['capacity']}" for u, v in G.edges()})
plt.show()