This has the same snag as subset betweenness: partially overlapping vertex selections for the undirected case need special care.
(see #2352 (comment))

Does it? I believe this is a simple matrix subsetting operation. I.e. the result should be the same as taking only some rows and only some columns in the adjacency matrix.

The fact that in the undirected partially overlapping case some connections will appear twice (below and above diagonal) and some once should not be a problem here.

Let me know if I misunderstood something.

Doesn't that take an unnecessary amount of time? igraph_get_adjacency() loops through all edges to take their to and froms.

For the submatrix variant I think going through all edges and then check if their to and froms are in the vertex selectors is not the most efficient way of handling this. I want to go through the vertex selectors and get the edges between them. Then you hit this problem.

Doesn't that take an unnecessary amount of time?

I didn't mean that it should be implemented by subsetting the complete matrix. That makes no sense, as there would be no performance gain in using this function. I simply meant to describe the expected result.

I want to go through the vertex selectors and get the edges between them. Then you hit this problem.

I see what you mean.

How about this?

• Create a bool array is_target where is_target[v] is true is v is a to vertex
• For each from vertex s:
  • Get the neighbour list, and for each neighbour t:
    • If is_target[t] then matrix[s, t] += 1.

I think this gives the correct result both for directed and undirected graphs. However, its performance characteristics are not invariant to the exchange of to and from. I'm not sure if this is an issue in practice. If we wanted to try to squeeze more performance, we have two version, one where the outer loop is on from and one where it is on to. Then choose the version where the outer loop is shorter.

An alternative implementation will not construct is_target. Instead, it creates a sorted list of to vertex IDs. Then it takes the intersection of this sorted list with the neighbour list. Note that the neighbour list is guaranteed to be sorted.

We already have such sorted intersection functions,

• igraph_i_neisets_intersect in cocitation.c
• In the cycle basis calculation I computed a symmetric difference in a similar way

Maybe we should have helper functions for union, intersection, difference, symmetric difference for sorted integer lists.

I suspect that one of these two approaches should be faster than starting with a source and target vertex ID, then getting the edges inbetween.

But this is difficult to predict ...

What do you think @GroteGnoom ?

These are the two common ways to intersect vertex sets, and I'm never sure which is faster, or under what conditions each is faster. E.g. igraph_ecc() uses the sort method and igraph_i_local_relative_density() uses the Boolean mask method.

How about this?

• Create a bool array is_target where is_target[v] is true is v is a to vertex
• For each from vertex s:
  • Get the neighbour list, and for each neighbour t:
    • If is_target[t] then matrix[s, t] += 1.

Lets use an example to clear things up. I think the simplest case where we have problems is a 3-vertex full graph with no loops, from = [0,1,2], to = [0,1].

The full GET_ADJACECNY_BOTH adjacency matrix for the whole graph would look like this:

we have 3 selected edges:
0-1
0-2
1-2

First, GET_ADJACENCY_LOWER and GET_ADJACENCY_UPPER don't always make sense. The 'from 0 to 2' and 'from 1 to 2' elements don't exist in the submatrix, so GET_ADJACENCY_UPPER will miss edges.

GET_ADJACENCY_LOWER would look like this:

GET_ADJACENCY_UPPER would look like this:

And this is GET_ADJACENCY_BOTH

... I'll have to think a bit.

For this application, there should be no igraph_get_adjacency_t type parameter. As you point out, it makes no sense.

I think that just solves everything 🙂
There could be performance improvements, including your suggestion.

I think this also shows the betweenness_subset problem in matrix form: neither the upper triangle or lower triangle necessarily has all the selected edges, and the whole matrix sometimes has an edge twice, sometimes once.