Select performance

[xrn]

I have the exact same issue which is described in this topic on Stack Overflow https://stackoverflow.com/questions/56638240/igraph-select-performance

I have a direct graph created using igraph and the whole code is very very fast but select function is amazingly slow - any idea how to improve it?

Here is my function def get_value(tree, index): return tree.es.select(_to=index)["value"][0]

[ntamas]

I have just submitted an answer to the SO post - thanks for bringing it to my attention.

select() is basically almost always doing a linear scan on the vertex or edge set being filtered, and most likely there is no optimized path within the code of select() that would handle your case. (The order of the evaluation of arguments is not guaranteed either).

Ideally, select() should recognize that there is a faster way of doing what you wanted; more precisely, if select() is operating on g.es (and not some pre-filtered subset of g.es), there are no positional arguments, and _to is somewhere among the keyword arguments, it should realize that it can use find() to find the appropriate set of edges quicker than the default case. Unfortunately I haven't had time to develop igraph further so this particular issue has been lingering around for a while now.

The good news is that the development of igraph and python-igraph is gaining momentum again, so I'm hoping to get this fixed in the next few days and then make a proper release of python-igraph 0.8 after nearly five years.

Until then, you can use tree.vs[index].incident(mode="in") to find the inbound edges of vertex index, so your code could be rewritten as:

def get_value(tree, index):
    return tree.vs[index].incident(mode="in")[0]["value"]

[xrn]

Thanks for response @ntamas

Good to hear that development is one more time on track. I used your code but I am getting

AttributeError: 'igraph.Vertex' object has no attribute 'incident'

Sorry for asking but I can not reach right solution. Seems that

return tree.incident(index, mode="in")

Is executing but is returning totally different data than what I am getting from tree.es.select - any idea?

python-igraph==0.7.1.post6

[ntamas]

It could be the case that the incident() method of the Vertex object is not in the latest public release yet. In that case, use:

eid = tree.incident(index, mode="in")[0]
return g.es[eid]["value"]

Explanation: tree.incident(index, mode="in") returns the indices of the edges terminating at the given vertex. You then pick the first of these edges with g.es[eid] and retrieve its value attribute.

[xrn]

For my case reduction of time using a new code was significant - from 45m to 1.5m. One more time thanks for help :clap: :clap: - and I am looking for release 0.8 - gl

[ntamas]

I have added an optimized code path for the common case when g.es.is_all() is True and the selection is based on source or target vertex only.

For 0.9.0, we should attempt a more sophisticated scheme where filters based on source and/or target vertices are prioritized over other filters even if there are multiple filters in the call to select().

[stale[bot]]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed in 14 days if no further activity occurs. Thank you for your contributions.