Thoughts on a new strategy

[rsokl]

Hi @pckroon . I used your graph_builder strategy to create a new hypothesis strategy that I found to be quite useful. It is designed to generate a graph that has a guaranteed min/max number of connected component, and each component is guaranteed to have a min/max number of nodes.

I'm curious if you would be interested in adding this as a strategy to hypothesis-networkx. I also have tests for this that provides full coverage.

For more details, here is the full signature / docstring. As noted below, it is possible to provide parameters that over-constrain the graphs to be generated, in all such cases the strategy will raise a ValueError telling the user that their specification is unsatisfiable.

@composite
def graphs(
    draw,
    min_nodes: int,
    max_nodes: Optional[int] = None,
    min_num_components: Optional[int] = None,
    max_num_components: Optional[int] = None,
    min_component_size: int = 1,
    max_component_size: Optional[int] = None,
) -> st.SearchStrategy[nx.Graph]:
    """Draws graphs whose number of nodes, number of connected components, and
    size of connected components are constrained.

    Parameters
    ----------
    min_nodes : int
        The minimum number of nodes permitted in a graph.

    max_nodes : Optional[int]
        The largest number of nodes permitted in a graph. Defaults to
        ``10 + min_nodes``.

    min_num_components : Optional[int]
        The minimum number of connected components permitted in a graph.
        Defaults to the smallest permissible number based on ``max_component_size``,
        if such a constraint is specified, and the number of nodes that were drawn.
        Otherwise this defaults to 1.

    max_num_components : Optional[int]
        The maximum number of connected components permitted in a graph.
        Defaults to the largest permissible number based on ``min_component_size``
        and the number of nodes that were drawn.

    min_component_size : int
        The smallest permissible size for a connected component in the a graph. The
        default value is one node.

    max_component_size : Optional[int]
        The largest permissible size for a connected component in the a graph. The
        default value adapts according to the constraints of other parameters to permit
        the largest possible connected component.

    Returns
    -------
    st.SearchStrategy[nx.Graph]

    Notes
    -----
    The parameters provided here have the potential of over-constraining the graphs.
    It is recommended that you either constrain the number of connected components or
    their size, not both.

    Values drawn from this strategy shrink towards a graph with:
        - fewer nodes
        - fewer connected components
        - an even distribution of nodes among its connected components

    Also note that the partition-generation process scales harshly with number of nodes:
    it is inadvisable to draw graphs with more then tens of nodes.""

[pckroon]

Hi,

I'm happy to you're finding it useful :)

I'm definitely open to PRs, especially if you think your graphs will be useful to other people as well. What I don't like about it though is that you lose all possibility of providing input on the node attributes and edge density. Can we come up with an intermediate form which accepts a list (?) of graph_builder created strategies, from which it then draws a number of components? The most common use-case (basically the signature of graphs) should then either be the behaviour with the default arguments, or even be provided as separate function.

What're your thoughts on this?

[mamonu]

@rsokl you wouldn't have that strategy available somewhere , would you? (its 2-3 years later so appreciate that this comment is probably not going to be seen)

I would love to have a look on how to create such a strategy as we are testing some graph functions and would like to use hypothesis and hypothesis-testing for that

[rsokl]

@mamonu I do still have it. I will try to make it available to you in the next few days

[pckroon]

@rsokl if you're willing to share it further I can also have a look at including your strategy in hypothesis-networkx. You're also welcome to open a PR yourself of course ;)

[rsokl]

@mamonu @pckroon sorry for the delay!

https://github.com/rsokl/graph_strat

Please let me know if you have any questions or see any issues. @pckroon feel free to incorporate this into hypothesis-networkx, I do not have the bandwidth to open a PR currently.

[rsokl]

@mamonu fyi I just pushed a somewhat minor change to improve the caching used by the partition generator