10000 minimum_node_cut not handling complete graphs correctly · Issue #8004 · networkx/networkx · GitHub
[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to content

minimum_node_cut not handling complete graphs correctly #8004

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Open
amcandio opened this issue Apr 27, 2025 · 0 comments
Open

minimum_node_cut not handling complete graphs correctly #8004

amcandio opened this issue Apr 27, 2025 · 0 comments

Comments

@amcandio
Copy link
Contributor
amcandio commented Apr 27, 2025 •
edited by dschult
Loading

As a follow up of #7994 I put up a quick property-based test based on in-the-works framework #7981.

import networkx as nx
from hypothesis import strategies as st
from networkx.hypothesis import graph_st
from hypothesis import given

flow_funcs = [
    flow.boykov_kolmogorov,
    flow.dinitz,
    flow.edmonds_karp,
    flow.preflow_push,
    flow.shortest_augmenting_path,
]

def _random_connected_graph(n, prob, seed):
    return nx.compose(
        nx.random_labeled_tree(n, seed=seed),
        nx.erdos_renyi_graph(n, prob, seed=seed),
    )

@given(
    graph_st(
        _random_connected_graph,
        n=st.integers(4, 10),
        prob=st.floats(0, 1)
    ),
    st.one_of([st.just(f) for f in flow_funcs]),
)
def test_random_connected_graph(G, flow_func):
    node_cut = nx.minimum_node_cut(G, flow_func=flow_func)
    H = G.copy()
    H.remove_nodes_from(node_cut)
    assert len(node_cut) == len(G) or not nx.is_connected(H)

Which fails with the following error:

_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _

G = <networkx.classes.graph.Graph object at 0x7f0bd13a5e50>, flow_func = <function boykov_kolmogorov at 0x7f0c1cb49620>

    @given(
        graph_st(
            _random_connected_graph,
            n=st.integers(4, 10),
            prob=st.floats(0, 1)
        ),
        st.one_of([st.just(f) for f in flow_funcs]),
    )
    def test_random_connected_graph(G, flow_func):
        node_cut = nx.minimum_node_cut(G, flow_func=flow_func)
        H = G.copy()
        H.remove_nodes_from(node_cut)
>       assert len(node_cut) == len(G) or not nx.is_connected(H)
E       assert (3 == 4 or not True)
E        +  where 3 = len({1, 2, 3})
E        +  and   4 = len(<networkx.classes.graph.Graph object at 0x7f0bd13a5e50>)
E        +  and   True = <function is_connected at 0x7f0c1cd13ba0>(<networkx.classes.graph.Graph object at 0x7f0bd13e0a50>)
E        +    where <function is_connected at 0x7f0c1cd13ba0> = nx.is_connected
E       Falsifying example: test_random_connected_graph(
E           G=nx.from_edgelist([(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]),
E           flow_func=boykov_kolmogorov,
E       )

Current Behavior

All node cuts is considering n-1 nodes of a K_n as a valid cut.

Expected Behavior

In a complete graph there are no node cuts, so it should either return all nodes or fail

Steps to Reproduce

See description
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Milestone
No milestone
Development

No branches or pull requests
1 participant
@amcandio
0