Repository: networkx/networkx
Pull request: Fix handling of faux_infinite values in network_simplex
I've looked into the issue and implemented a potential fix. While I have a general understanding of the high-level idea, I have not studied the network-simplex algorithm in full detail.

From my understanding, the purpose of the `faux_inf value` is to create dummy edges and assign them a "practical infinity" value, rather than using actual infinity. This "practical infinity" is intended to be sufficiently large compared to all other "real" weights and capacities.

Change made:

1. Implemented a new calculation for `faux_inf`: 
   `faux_inf = (sum(c for c in DEAF.edge_capacities if c < inf) +
                sum(abs(w) for w in DEAF.edge_weights) +
                sum(abs(d) for d in DEAF.node_demands)) * 10 or 1`

2. Added the three sample cases discussed in the issue as tests (for illustration):
     - Verified that these tests fail without the fix.
     - Confirmed that they pass with the fix applied.

I believe not all three test cases are necessary for permanent inclusion in the codebase. Please feel free to provide feedback or suggest changes. 

Fixes https://github.com/networkx/networkx/issues/7562 

Problem statement:
network_simplex falsely reports negative cycle with infinite capacity
### Current Behavior

For specific networks, I observe that the `network_simplex` method claims `nx.NetworkXUnbounded("negative cycle with infinite capacity found")`, although this should not be the case. When adding to some edges an arbitrary but high capacity, I obtain a valid result, although the additionally introduced capacities are not exhausted.

After some light debugging, I found out that the condition is checked in the file `networksimplex.py` at:
```python
if any(DEAF.edge_flow[i] * 2 >= faux_inf for i in range(DEAF.edge_count)) or any(
    e[-1].get(capacity, inf) == inf and e[-1].get(weight, 0) < 0
    for e in nx.selfloop_edges(G, data=True)
):
    raise nx.NetworkXUnbounded("negative cycle with infinite capacity found")
```
Here, the problem is ```any(DEAF.edge_flow[i] * 2 >= faux_inf for i in range(DEAF.edge_count))```. As `faux_inf` is calculated with
```python
faux_inf = (
    3
    * max(
        chain(
            [
                sum(c for c in DEAF.edge_capacities if c < inf),
                sum(abs(w) for w in DEAF.edge_weights),
            ],
            (abs(d) for d in DEAF.node_demands),
        )
    )
    or 1
)
```
its result is dependent on the capacity of an edge. So obviously, when the of one edge is increased to a large value, `faux_inf` becomes quite big and the test does not fail anymore.

### Expected Behavior

The report for a negative cycle with infinite capacity should only happen when this is actually the case, without a need for the workaround specifying an artificial `capacity` value.

### Steps to Reproduce

I've prepared a small script that (i) creates a network with weights and demands and tries to run the `network_simplex` method and (ii) does the same, but now adds a capacity to two edges. While (i) reports a negative cycle with infinite capacity, (ii) works fine. I'm sorry that the network is quite large but I did not find a smaller one.

```python
import networkx as nx
import traceback


def create_graph(with_capacity):
    G = nx.DiGraph()

    # Add nodes with demands
    G.add_node('s0', demand=-89)
    G.add_node('s1', demand=-197)
    G.add_node('s2', demand=89)
    G.add_node('s3', demand=212)
    G.add_node('s4', demand=32)
    G.add_node('s5', demand=83)
    G.add_node('s6', demand=-159)
    G.add_node('s7', demand=-68)
    G.add_node('s8', demand=116)
    G.add_node('s9', demand=120)
    G.add_node('s10', demand=-65)
    G.add_node('s11', demand=-74)

    # Add edges
    if with_capacity:
        G.add_edge('s0', 's0', weight=1, capacity=10000)
        G.add_edge('s0', 's1', weight=1, capacity=10000)
    else:
        G.add_edge('s0', 's0', weight=1)
        G.add_edge('s0', 's1', weight=1)

    G.add_edge('s1', 's0', weight=1)
    G.add_edge('s1', 's2', weight=1)
    G.add_edge('s1', 's3', weight=1)
    G.add_edge('s1', 's4', weight=1)
    G.add_edge('s10', 's0', weight=1)
    G.add_edge('s10', 's10', weight=1)
    G.add_edge('s10', 's7', weight=1)
    G.add_edge('s11', 's0', weight=1)
    G.add_edge('s11', 's11', weight=1)
    G.add_edge('s11', 's5', weight=1)
    G.add_edge('s11', 's7', weight=1)
    G.add_edge('s11', 's9', weight=1)
    G.add_edge('s2', 's0', weight=1)
    G.add_edge('s2', 's1', weight=1)
    G.add_edge('s2', 's2', weight=1)
    G.add_edge('s2', 's5', weight=1)
    G.add_edge('s3', 's0', weight=1)
    G.add_edge('s3', 's1', weight=1)
    G.add_edge('s3', 's2', weight=1)
    G.add_edge('s3', 's3', weight=1)
    G.add_edge('s4', 's0', weight=1)
    G.add_edge('s4', 's6', weight=1)
    G.add_edge('s4', 's7', weight=1)
    G.add_edge('s5', 's0', weight=1)
    G.add_edge('s5', 's10', weight=1)
    G.add_edge('s5', 's11', weight=1)
    G.add_edge('s5', 's8', weight=1)
    G.add_edge('s5', 's9', weight=1)
    G.add_edge('s6', 's0', weight=1)
    G.add_edge('s6', 's10', weight=1)
    G.add_edge('s6', 's4', weight=1)
    G.add_edge('s6', 's6', weight=1)
    G.add_edge('s7', 's0', weight=1)
    G.add_edge('s7', 's10', weight=1)
    G.add_edge('s7', 's4', weight=1)
    G.add_edge('s7', 's6', weight=1)
    G.add_edge('s8', 's0', weight=1)
    G.add_edge('s8', 's11', weight=1)
    G.add_edge('s8', 's8', weight=1)
    G.add_edge('s8', 's9', weight=1)
    G.add_edge('s9', 's0', weight=1)
    G.add_edge('s9', 's11', weight=1)
    G.add_edge('s9', 's5', weight=1)
    G.add_edge('s9', 's7', weight=1)
    G.add_edge('s9', 's8', weight=1)

    return G


# Calculate min-cost flow
try:
    G1 = create_graph(False)
    flow_value, flow_dict = nx.network_simplex(G1)  # fails
except Exception:
    print(traceback.format_exc())

G2 = create_graph(True)
flow_value, flow_dict = nx.network_simplex(G2)  # succeeds
print(flow_value, flow_dict)
```

### Environment

Python version: 3.12.4
NetworkX version: 3.3

Hints from issue discussion:
Thanks for this report.  In the code is an undocumented upper-bound calculated from weights and capacities, which is being violated in your example.

```python
    faux_inf = (
        3
        * max(
            chain(
                [
                    sum(c for c in DEAF.edge_capacities if c < inf),
                    sum(abs(w) for w in DEAF.edge_weights),
                ],
                (abs(d) for d in DEAF.node_demands),
            )
        )
        or 1
    )
```
Sorry to duplicate your findings; I skipped to poking at code while sipping coffee this morning and forgot to read the bug report :roll_eyes: 

For what it's worth, I've minified your example down to a tree (pretty hard to find a negative cycle in a tree, right?)

```python
import networkx as nx
import traceback


cap = 1000000000
def create_graph(with_capacity):
    G = nx.DiGraph()

    c = dict(capacity=cap) if with_capacity else {}

    # Add nodes with demands
    G.add_node('s0', demand=-89)
    G.add_node('s1', demand=-197)
    G.add_node('s2', demand=89)
    G.add_node('s3', demand=212)
    G.add_node('s4', demand=32)
    G.add_node('s5', demand=83)
    G.add_node('s6', demand=-159)
    G.add_node('s7', demand=-68)
    G.add_node('s8', demand=116)
    G.add_node('s9', demand=120)
    G.add_node('s10', demand=-65)
    G.add_node('s11', demand=-74)

    # Add edges
    G.add_edge('s0', 's1', weight=1, **c)
    G.add_edge('s1', 's2', weight=1)
    G.add_edge('s1', 's3', weight=1)
    G.add_edge('s1', 's4', weight=1)
    G.add_edge('s10', 's0', weight=1)
    G.add_edge('s11', 's9', weight=1)
    G.add_edge('s2', 's5', weight=1)
    G.add_edge('s5', 's11', weight=1)
    G.add_edge('s5', 's8', weight=1)
    G.add_edge('s6', 's10', weight=1)
    G.add_edge('s7', 's0', weight=1)

    return G


# Calculate min-cost flow
try:
    G1 = create_graph(False)
    flow_value, flow_dict = nx.network_simplex(G1)  # fails
except Exception:
    print(traceback.format_exc())

G2 = create_graph(True)
flow_value, flow_dict = nx.network_simplex(G2)  # succeeds
print(flow_value, flow_dict)
```
I haven't hardly even looked at this yet. But I wonder if that `or 1` near the end of `faux_inf` should be a 3. (the whole max expression gets multiplied by 3 as an over-estimate for the max of 2 * edge_flow. So why would that being zero make the alternative value `1`.  Anyway, that's why it seems to me to be wrong to have `or 1`.)
As I'm staring at this, the pseudo-infinity is failing because it seems to assume that no pipe will carry more than any single consumer/producer.  If we insert a `sum`, this bug is apparently* resolved in 3 bytes.

```python
...
                sum(abs(d) for d in DEAF.node_demands),
...
```

Dan, I'm not sure what to make of that constant either.

\* I say "apparently" because it only resolves this one issue.  I remain suspicious.
and with that observation, we get a (provably?) minimal example

```python
cap = 1000000000
def create_graph(with_capacity):
    G = nx.DiGraph()

    c = dict(capacity=cap) if with_capacity else {}

    # Add nodes with demands
    G.add_node('s0', demand=-4)
    G.add_node('s1', demand=-4)
    G.add_node('ns', demand=0)
    G.add_node('nc', demand=0)
    G.add_node('c0', demand=4)
    G.add_node('c1', demand=4)

    # Add edges
    G.add_edge('s0', 'ns', weight=1, **c)
    G.add_edge('s1', 'ns', weight=1)
    G.add_edge('ns', 'nc', weight=1)
    G.add_edge('nc', 'c0', weight=1)
    G.add_edge('nc', 'c1', weight=1)

    return G

```

Here, we see that `(nc, ns)` carries twice the max-abs-demand from the two suppliers to the two consumers, and exactly half of the sum-abs-demand.  I still don't know what the 3 is doing there, but I could argue that this example tightly achieves the sum-abs-demand bound.  I could argue for a slightly finer bound; `min(sum(d for d in demands if d > 0), -sum(d for d in demands if d < 0))`, and dropping the multiplication by 2, but that's quibbling.
Pawing through the history a bit, the `faux_inf` bound was introduced in #1280 and has remained unchanged except for formatting since that time.  I haven't yet read through the references introduced by @ysitu in detail, but I've skimmed [Kiraly and Kovacs](https://arxiv.org/pdf/1207.6381) and didn't spot a similar bound.  I also skimmed the source of the [Lemon implementation](http://lemon.cs.elte.hu/hg/lemon/file/a278d16bd2d0/lemon/network_simplex.h) that (I think) the K&K paper discusses, and it uses either `inf` or `INT_MAX` for its bound.  That said, I haven't fully grokked either implementation.  It'd be most convenient if @ysitu could tell us where the algorithm is described and where the bound comes from.
Hi @dschult
I've looked into the issue and believe I have a potential fix. While I understand the high-level idea, I haven't studied the corresponding network-simplex algorithm in full detail.

From my understanding, the idea behind the `faux_inf` value is to create dummy edges and assign them a "practical infinity" value, rather than using actual infinity. This "practical infinity" should be large enough compared to all other "real" weights and capacities.

Here’s my proposed solution:
`faux_inf = (sum(c for c in DEAF.edge_capacities if c < inf) + 
                   sum(abs(w) for w in DEAF.edge_weights) + 
                   sum(abs(d) for d in DEAF.node_demands))*10`

I tested all three cases listed above by @boothby and they passed. 
Could you let me know if I shall open a PR with this solution and corresponding tests?
Yes, a PR would help us understand and test the ideas discussed above, and especially your suggestion.
Thanks!

Commit message: Refactor error messages and correspoding tests.

Patch to review:
diff --git a/networkx/algorithms/flow/networksimplex.py b/networkx/algorithms/flow/networksimplex.py
index a9822d96880..e708917d965 100644
--- a/networkx/algorithms/flow/networksimplex.py
+++ b/networkx/algorithms/flow/networksimplex.py
@@ -512,34 +512,46 @@ def network_simplex(G, demand="demand", capacity="capacity", weight="weight"):
     inf = float("inf")
     for u, d in zip(DEAF.node_list, DEAF.node_demands):
         if abs(d) == inf:
-            raise nx.NetworkXError(f"node {u!r} has infinite demand")
+            raise nx.NetworkXError(
+                f"Invalid input: Node {u!r} has an infinite absolute demand, which is not allowed."
+            )
     for e, w in zip(DEAF.edge_indices, DEAF.edge_weights):
         if abs(w) == inf:
-            raise nx.NetworkXError(f"edge {e!r} has infinite weight")
+            raise nx.NetworkXError(
+                f"Invalid input: Edge {e!r} has an infinite absolute weight, making the cost computation undefined."
+            )
     if not multigraph:
         edges = nx.selfloop_edges(G, data=True)
     else:
         edges = nx.selfloop_edges(G, data=True, keys=True)
     for e in edges:
         if abs(e[-1].get(weight, 0)) == inf:
-            raise nx.NetworkXError(f"edge {e[:-1]!r} has infinite weight")
+            raise nx.NetworkXError(
+                f"Invalid input: Self-loop {e[:-1]!r} has an infinite weight, which is not allowed."
+            )
 
     ###########################################################################
     # Quick Infeasibility Detection
     ###########################################################################
 
     if sum(DEAF.node_demands) != 0:
-        raise nx.NetworkXUnfeasible("total node demand is not zero")
+        raise nx.NetworkXUnfeasible(
+            "Flow infeasible: The total supply does not match the total demand."
+        )
     for e, c in zip(DEAF.edge_indices, DEAF.edge_capacities):
         if c < 0:
-            raise nx.NetworkXUnfeasible(f"edge {e!r} has negative capacity")
+            raise nx.NetworkXUnfeasible(
+                f"Invalid input: Edge {e!r} has a negative capacity, which is not allowed."
+            )
     if not multigraph:
         edges = nx.selfloop_edges(G, data=True)
     else:
         edges = nx.selfloop_edges(G, data=True, keys=True)
     for e in edges:
         if e[-1].get(capacity, inf) < 0:
-            raise nx.NetworkXUnfeasible(f"edge {e[:-1]!r} has negative capacity")
+            raise nx.NetworkXUnfeasible(
+                f"Invalid input: Self-loop {e[:-1]!r} has a negative capacity, which is not allowed."
+            )
 
     ###########################################################################
     # Initialization
@@ -562,13 +574,9 @@ def network_simplex(G, demand="demand", capacity="capacity", weight="weight"):
     faux_inf = (
         3
         * max(
-            chain(
-                [
-                    sum(c for c in DEAF.edge_capacities if c < inf),
-                    sum(abs(w) for w in DEAF.edge_weights),
-                ],
-                (abs(d) for d in DEAF.node_demands),
-            )
+            sum(c for c in DEAF.edge_capacities if c < inf),
+            sum(abs(w) for w in DEAF.edge_weights),
+            sum(abs(d) for d in DEAF.node_demands),
         )
         or 1
     )
@@ -606,13 +614,17 @@ def network_simplex(G, demand="demand", capacity="capacity", weight="weight"):
     ###########################################################################
 
     if any(DEAF.edge_flow[i] != 0 for i in range(-n, 0)):
-        raise nx.NetworkXUnfeasible("no flow satisfies all node demands")
+        raise nx.NetworkXUnfeasible(
+            "Flow infeasible: The network cannot satisfy all node demands due to capacity constraints."
+        )
 
     if any(DEAF.edge_flow[i] * 2 >= faux_inf for i in range(DEAF.edge_count)) or any(
         e[-1].get(capacity, inf) == inf and e[-1].get(weight, 0) < 0
         for e in nx.selfloop_edges(G, data=True)
     ):
-        raise nx.NetworkXUnbounded("negative cycle with infinite capacity found")
+        raise nx.NetworkXUnbounded(
+            "Unbounded flow detected: A negative-weight cycle with infinite capacity allows indefinite cost reduction."
+        )
 
     ###########################################################################
     # Flow cost calculation and flow dict construction
diff --git a/networkx/algorithms/flow/tests/test_networksimplex.py b/networkx/algorithms/flow/tests/test_networksimplex.py
index 5b3b5f6dd06..297e5aa931e 100644
--- a/networkx/algorithms/flow/tests/test_networksimplex.py
+++ b/networkx/algorithms/flow/tests/test_networksimplex.py
@@ -6,6 +6,7 @@
 import pytest
 
 import networkx as nx
+from networkx import NetworkXUnbounded
 
 
 @pytest.fixture
@@ -48,15 +49,25 @@ def get_flowcost_from_flowdict(G, flowDict):
 def test_infinite_demand_raise(simple_flow_graph):
     G = simple_flow_graph
     inf = float("inf")
-    nx.set_node_attributes(G, {"a": {"demand": inf}})
-    pytest.raises(nx.NetworkXError, nx.network_simplex, G)
+    node_name = "a"
+    nx.set_node_attributes(G, {node_name: {"demand": inf}})
+    with pytest.raises(
+        nx.NetworkXError,
+        match=f"Invalid input: Node '{node_name}' has an infinite absolute demand, which is not allowed.",
+    ):
+        nx.network_simplex(G)
 
 
 def test_neg_infinite_demand_raise(simple_flow_graph):
     G = simple_flow_graph
     inf = float("inf")
-    nx.set_node_attributes(G, {"a": {"demand": -inf}})
-    pytest.raises(nx.NetworkXError, nx.network_simplex, G)
+    node_name = "a"
+    nx.set_node_attributes(G, {node_name: {"demand": -inf}})
+    with pytest.raises(
+        nx.NetworkXError,
+        match=f"Invalid input: Node '{node_name}' has an infinite absolute demand, which is not allowed.",
+    ):
+        nx.network_simplex(G)
 
 
 def test_infinite_weight_raise(simple_flow_graph):
@@ -65,30 +76,50 @@ def test_infinite_weight_raise(simple_flow_graph):
     nx.set_edge_attributes(
         G, {("a", "b"): {"weight": inf}, ("b", "d"): {"weight": inf}}
     )
-    pytest.raises(nx.NetworkXError, nx.network_simplex, G)
+    with pytest.raises(
+        nx.NetworkXError,
+        match=r"Invalid input: Edge .* has an infinite absolute weight, making the cost computation undefined.",
+    ):
+        nx.network_simplex(G)
 
 
 def test_nonzero_net_demand_raise(simple_flow_graph):
     G = simple_flow_graph
     nx.set_node_attributes(G, {"b": {"demand": -4}})
-    pytest.raises(nx.NetworkXUnfeasible, nx.network_simplex, G)
+    with pytest.raises(
+        nx.NetworkXUnfeasible,
+        match="Flow infeasible: The total supply does not match the total demand.",
+    ):
+        nx.network_simplex(G)
 
 
 def test_negative_capacity_raise(simple_flow_graph):
     G = simple_flow_graph
     nx.set_edge_attributes(G, {("a", "b"): {"weight": 1}, ("b", "d"): {"capacity": -9}})
-    pytest.raises(nx.NetworkXUnfeasible, nx.network_simplex, G)
+    with pytest.raises(
+        nx.NetworkXUnfeasible,
+        match=r"Invalid input: Edge .* has a negative capacity, which is not allowed.",
+    ):
+        nx.network_simplex(G)
 
 
 def test_no_flow_satisfying_demands(simple_no_flow_graph):
     G = simple_no_flow_graph
-    pytest.raises(nx.NetworkXUnfeasible, nx.network_simplex, G)
+    with pytest.raises(
+        nx.NetworkXUnfeasible,
+        match="Flow infeasible: The network cannot satisfy all node demands due to capacity constraints.",
+    ):
+        nx.network_simplex(G)
 
 
 def test_sum_demands_not_zero(simple_no_flow_graph):
     G = simple_no_flow_graph
     nx.set_node_attributes(G, {"t": {"demand": 4}})
-    pytest.raises(nx.NetworkXUnfeasible, nx.network_simplex, G)
+    with pytest.raises(
+        nx.NetworkXUnfeasible,
+        match="Flow infeasible: The total supply does not match the total demand.",
+    ):
+        nx.network_simplex(G)
 
 
 def test_google_or_tools_example():
@@ -385,3 +416,82 @@ def test_graphs_type_exceptions():
     pytest.raises(nx.NetworkXNotImplemented, nx.network_simplex, G)
     G = nx.DiGraph()
     pytest.raises(nx.NetworkXError, nx.network_simplex, G)
+
+
+def create_graph(
+    has_large_capacity: bool = False,
+    has_large_weight: bool = False,
+    has_large_demand: bool = False,
+):
+    large_value = 1000000000
+    G = nx.DiGraph()
+
+    # Add nodes with demands
+    if has_large_demand:
+        G.add_node("s0", demand=-large_value)
+        G.add_node("c1", demand=large_value)
+    else:
+        G.add_node("s0", demand=-4)
+        G.add_node("c1", demand=4)
+
+    G.add_node("s1", demand=-4)
+    G.add_node("ns", demand=0)
+    G.add_node("nc", demand=0)
+    G.add_node("c0", demand=4)
+
+    # Add edges
+    if has_large_capacity:
+        G.add_edge("s0", "ns", weight=1, capacity=large_value)
+    else:
+        G.add_edge("s0", "ns")
+
+    if has_large_weight:
+        G.add_edge("s1", "ns", weight=large_value)
+    else:
+        G.add_edge("s1", "ns", weight=1)
+
+    G.add_edge("ns", "nc", weight=1)
+    G.add_edge("nc", "c0", weight=1)
+    G.add_edge("nc", "c1", weight=1)
+
+    return G
+
+
+@pytest.mark.parametrize(
+    "has_large_capacity, has_large_weight, has_large_demand",
+    [
+        (True, True, True),
+        (True, True, False),
+        (True, False, True),
+        (True, False, False),
+        (False, True, True),
+        (False, True, False),
+        (False, False, True),
+        (False, False, False),
+    ],
+)
+def test_network_simplex_large_capacities(
+    has_large_capacity: bool, has_large_weight: bool, has_large_demand: bool
+):
+    """Address issues raised in ticket #7562."""
+    graph = create_graph(has_large_capacity, has_large_weight, has_large_demand)
+    flow_value, flow_dict = nx.network_simplex(graph)
+
+
+def test_network_simplex_unbounded_flow():
+    G = nx.DiGraph()
+    # Add nodes
+    G.add_node("A")
+    G.add_node("B")
+    G.add_node("C")
+
+    # Add edges forming a negative cycle
+    G.add_edge("A", "B", weight=-5)
+    G.add_edge("B", "C", weight=-5)
+    G.add_edge("C", "A", weight=-5)
+
+    with pytest.raises(
+        NetworkXUnbounded,
+        match="Unbounded flow detected: A negative-weight cycle with infinite capacity allows indefinite cost reduction.",
+    ):
+        nx.network_simplex(G)


Code review comments:
diff_hunk: @@ -385,3 +416,82 @@ def test_graphs_type_exceptions():
     pytest.raises(nx.NetworkXNotImplemented, nx.network_simplex, G)
     G = nx.DiGraph()
     pytest.raises(nx.NetworkXError, nx.network_simplex, G)
+
+
+def create_graph(
+    has_large_capacity: bool = False,
+    has_large_weight: bool = False,
+    has_large_demand: bool = False,
+):
+    large_value = 1000000000
+    G = nx.DiGraph()
+
+    # Add nodes with demands
+    if has_large_demand:
+        G.add_node("s0", demand=-large_value)
+        G.add_node("c1", demand=large_value)
+    else:
+        G.add_node("s0", demand=-4)
+        G.add_node("c1", demand=4)
+
+    G.add_node("s1", demand=-4)
+    G.add_node("ns", demand=0)
+    G.add_node("nc", demand=0)
+    G.add_node("c0", demand=4)
+
+    # Add edges
+    if has_large_capacity:
+        G.add_edge("s0", "ns", weight=1, capacity=large_value)
+    else:
+        G.add_edge("s0", "ns")
+
+    if has_large_weight:
+        G.add_edge("s1", "ns", weight=large_value)
+    else:
+        G.add_edge("s1", "ns", weight=1)
+
+    G.add_edge("ns", "nc", weight=1)
+    G.add_edge("nc", "c0", weight=1)
+    G.add_edge("nc", "c1", weight=1)
+
+    return G
+
+
+@pytest.mark.parametrize(
+    "has_large_capacity, has_large_weight, has_large_demand",
+    [
+        (True, True, True),
+        (True, True, False),
+        (True, False, True),
+        (True, False, False),
+        (False, True, True),
+        (False, True, False),
+        (False, False, True),
+        (False, False, False),
+    ],
+)
+def test_network_simplex_large_capacities(
+    has_large_capacity: bool, has_large_weight: bool, has_large_demand: bool
+):
+    """Address issues raised in ticket #7562."""
+    graph = create_graph(has_large_capacity, has_large_weight, has_large_demand)
+    flow_value, flow_dict = nx.network_simplex(graph)
+
+
+def test_network_simplex_unbounded_flow():
+    G = nx.DiGraph()
+    # Add nodes
+    G.add_node("A")
+    G.add_node("B")
+    G.add_node("C")
+
+    # Add edges forming a negative cycle
+    G.add_edge("A", "B", weight=-5)
+    G.add_edge("B", "C", weight=-5)
+    G.add_edge("C", "A", weight=-5)
+
+    with pytest.raises(
+        NetworkXUnbounded,
path: networkx/algorithms/flow/tests/test_networksimplex.py
text: @user1:
```suggestion
        nx.NetworkXUnbounded,

```

diff_hunk: @@ -6,6 +6,7 @@
 import pytest
 
 import networkx as nx
+from networkx import NetworkXUnbounded
path: networkx/algorithms/flow/tests/test_networksimplex.py
text: @user1:
Just a style note - it's preferred to refer to exceptions from the main namespace to keep the imports down (see corresponding change below)

```suggestion

```

diff_hunk: @@ -385,3 +416,82 @@ def test_graphs_type_exceptions():
     pytest.raises(nx.NetworkXNotImplemented, nx.network_simplex, G)
     G = nx.DiGraph()
     pytest.raises(nx.NetworkXError, nx.network_simplex, G)
+
+
+def create_graph(
+    has_large_capacity: bool = False,
+    has_large_weight: bool = False,
+    has_large_demand: bool = False,
+):
+    large_value = 1000000000
+    G = nx.DiGraph()
+
+    # Add nodes with demands
+    if has_large_demand:
+        G.add_node("s0", demand=-large_value)
+        G.add_node("c1", demand=large_value)
+    else:
+        G.add_node("s0", demand=-4)
+        G.add_node("c1", demand=4)
+
+    G.add_node("s1", demand=-4)
+    G.add_node("ns", demand=0)
+    G.add_node("nc", demand=0)
+    G.add_node("c0", demand=4)
+
+    # Add edges
+    if has_large_capacity:
+        G.add_edge("s0", "ns", weight=1, capacity=large_value)
+    else:
+        G.add_edge("s0", "ns")
+
+    if has_large_weight:
+        G.add_edge("s1", "ns", weight=large_value)
+    else:
+        G.add_edge("s1", "ns", weight=1)
+
+    G.add_edge("ns", "nc", weight=1)
+    G.add_edge("nc", "c0", weight=1)
+    G.add_edge("nc", "c1", weight=1)
+
+    return G
+
+
+@pytest.mark.parametrize(
+    "has_large_capacity, has_large_weight, has_large_demand",
+    [
+        (True, True, True),
+        (True, True, False),
+        (True, False, True),
+        (True, False, False),
+        (False, True, True),
+        (False, True, False),
+        (False, False, True),
+        (False, False, False),
+    ],
+)
+def test_network_simplex_large_capacities(
+    has_large_capacity: bool, has_large_weight: bool, has_large_demand: bool
+):
+    """Address issues raised in ticket #7562."""
+    graph = create_graph(has_large_capacity, has_large_weight, has_large_demand)
+    flow_value, flow_dict = nx.network_simplex(graph)
+
+
+def test_network_simplex_unbounded_flow():
+    G = nx.DiGraph()
+    # Add nodes
+    G.add_node("A")
+    G.add_node("B")
+    G.add_node("C")
+
+    # Add edges forming a negative cycle
+    G.add_edge("A", "B", weight=-5)
+    G.add_edge("B", "C", weight=-5)
+    G.add_edge("C", "A", weight=-5)
path: networkx/algorithms/flow/tests/test_networksimplex.py
text: @user1:
Just a cosmetic change, but this could be shortened:

```suggestion
    # A negative cycle
    G.add_weighted_edges_from([("A", "B", -5), ("B", "C", -5), ("C", "A", -5)])
```