Fast filtering needs based on reachability

[vpoughonEZ]

I'd like to filter needs based on reachability, i.e. keep all needs that are related to the current one through either requires, links_back, tests_back, etc. recursively, to produce an extract of only relevant elements in a needflow.

Right now I'm using this custom filter function but it's very slow because it's called for every single need, and we have hundreds of them. Any recommendation on how to optimize it? I've thought about pre-computing a reachability matrix once, so that the filtering can be much faster by just looking up indexes. But where would I put this pre-computing code?

def needflow_filter(needs, results, **kwargs):
    "Custom filter function for the needflow directive"

    # Get id of the current need from the template
    this_id = kwargs["arg1"]

    needs_dict = {x['id_complete']: x for x in needs}
    needs_links = {
        x['id_complete']: x['links_back'] + x['tests_back'] + x['implements_back'] +
        x['iscomposedof_back'] + x['requires']
        for x in needs
    }

    candidates = set([this_id])
    results.append(needs_dict[this_id])
    result_id = set(candidates)

    while len(candidates) != 0:
        c = candidates.pop()
        links = needs_links[c]
        for link in links:
            if link not in result_id:
                result_id.add(link)
                candidates.add(link)
                n = needs_dict[link]
                results.append(n)
                results.append(needs_dict[n['id_parent']])

[danwos]

Hi,
first of all, excellent approach. I like it 👍

Unfortunately, I see no way to add a pre-calculated reachability matrix somewhere and reuse it easily. Not with the current features Sphinx and Sphinx-Needs are providing via config.

But I think such a reachability matrix would be helpful for everybody and speed up things.
So a solution could be directly implemented into Sphinx-Needs itself and make it available inside filter-functions via a simple parameter or it is part of the need object itself. It could also make filtering based on links much easier.

I think developing a solution directly in Sphinx-Needs is much faster than optimizing your approach with the currently available feature set.

What do you think?
Maybe we can use this discussion to define together a new feature, which is based on your use case, but implemented in a more, maybe configurable way.

First idea: We could create a common graph for all needs. Based on networkX?
We should try to include as less link/graph specific code is needed into Sphinx-Needs, as I think there are already great, powerful libs out there.

[vpoughonEZ]

Thanks, yes I agree with your points. Ideally this could be accomplished with a simple filter string like id in reachable_from(current_id) or something (not sure about the syntax). But of course what type of links count as "reachable" should be configurable. And most importantly it should be fast. So the first step is that sphinx needs, as soon as the list of all defined needs is available, should pre-compute reachability data. The second step is to make it available to users, either via a string, or maybe simpler via an object that we can use in a filter function. If my function above had access to the precomputed reachability data it would be easy to compute the result.

[vpoughonEZ]

But of course pre-computing the reachability matrix might be expensive if it's not ever needed, so there's some tradeoff or configuration to consider.

[adegroote]

What I try to do, but I don't test if it really works in term of "performance" improvement is the following :

def get_dict(needs):
    if not hasattr(get_dict, 'd'):
        get_dict.d = {x['id']: x for x in needs}
    return get_dict.d


def get_links(needs):
    if not hasattr(get_links, 'd'):
        get_links.d = {x['id']:  x['links_back'] + x['tests_back'] + x['implements_back']
                       for x in needs}
    return get_links.d

to cache the dictionaries.

Still, I don't test if it really improves the performance. Anyway, a full graph representation would be very nice :D

[danieleades]

the 'needs' should form a directed acyclic graph. Once constructed, it should be fairly cheap to traverse