Indexability of vertices and neighbors

[gdalle]

In the PRs done by @simonschoelly to test on generic graphs, he frequently ran into trouble because collections like vertices(g) or neighbors(g, v) were not indexable. This explains the appearance of the function collect_if_not_vector throughout the code.

@etiennedeg what will this behavior look like in GraphsBase?

[gdalle]

See #270

[etiennedeg]

Very good question, for the moment, the collect_if_not_vector sounds like the best workaround but feels a bit clunky, maybe it can be refined by checking outneighbors implement indexing methods ?

[simonschoelly]

The collect_if_not_vector also has the downside, that we might unnecessary allocate some things. What we maybe want, is that these methods return something that implements the Indexing operators. So we could require that all these methods return something that is an AbstractVector. Can we think of some cases were that would be a to strict of a requirement?

One downside I already see is the neighbors function for directed graph, Where we have to take the union of the in and out neighbors. On the other hand, this is such a rare case, maybe we can just create some weird wrapper type that has a non-constant indexing time. We already allocate a whole vector at the moment for SimpleDiGraph, so we also pay a cost there.

[simonschoelly]

Very good question, for the moment, the collect_if_not_vector sounds like the best workaround but feels a bit clunky, maybe it can be refined by checking outneighbors implement indexing methods ?

This might be possible with something like Base.hasmethod - I am just always a bit careful with such reflection based methods, as I think I run into some world age issues when I had much less experience with Julia. But the julia standard library also seems to use it, so maybe it is indeed possible.

[simonschoelly]

Something like

function collect_if_not_indexable(vs)
    if Base.hasmethod(getindex, (typeof(vs), Integer))
        return vs
    else
        return collect(vs)
     end
 end

[gdalle]

Either that or we wrap it inside a struct that does indexing by enumeration, and we pay non-constant indexing cost