bfs()/dfs() adds NA into 'father' vector, which then causes trouble later

[szhorvat]

Describe the bug

The bfs() and dfs() functions produce a 'father' vector that contains NA for the root. This is in fact not a vector, but an igraph.vs, where it is reasonable to expect that all values are proper vertex IDs and not NA. As a result, there will be problems when trying to use this result.

This is closely related to #186. Perhaps the same fix should be applied as there. While this will be a breaking change, the father results appears to be unusable at the moment, as the NAs are basically guaranteed to trigger an error (unless I'm missing something about how to work with NA).

To reproduce

g <- sample_gnm(10,20)
res <- bfs(g,1,father=T)$father

> str(res)
Error in simple_vs_index(x, ii, na_ok) : Unknown vertex selected
> res[1]
Error in simple_vs_index(x, args[[1]]$expr) : Unknown vertex selected

I am not sure how to even test whether a certain element or NA, which is what originally prevented me from being able to come up with a nice solution for the Strahler number computation here.

Version information

1.3.0, but also earlier.

[szhorvat]

Ultimately, the question is how to represent trees through parent vectors, see igraph/igraph#1880 Also, what to call parent vectors? parent? father? predecessor?

[ntamas]

I'm going to keep father for the 1.x series in order not to break the API; we can reconsider for 2.0 where we will need to break all sorts of things anyway.

As for NA, res[1, na_ok=T] works now after d88657c. I'll look into enabling NA values for str(res).

[ntamas]

Okay, so supporting str(res) is not easy. In the end, it boils down to a call to [.igraph.vs from an internal part of the R code that I have no control over. So, either we make it possible for igraph.vs to remember whether it was constructed with na_ok in the first place so sub-slices created from it can "inherit" this property, or we make na_ok=T the default, which is a breaking change.

[ntamas]

Postponing the rest of this issue to 2.x; indexing now works with the na_ok=... trick outlined above, and supporting str(res) would require deeper changes that we are not prepared to do now.

[krlmlr]

str() is a generic, can we implement a method for it?

We could mention na_ok in the error message.

[krlmlr]

As for the presence of NA values, I don't see it as a big problem. This is idiomatic R.

[ntamas]

I didn't know that str is a generic at the time I wrote it. If we can work around the issue with that, that's great, but I don't think it's a priority. Also, if NA values in a result vector like this is idiomatic R and people know who to do with it, that's OK and we can essentially close this issue.

[szhorvat]

As for the presence of NA values, I don't see it as a big problem. This is idiomatic R.

Also, if NA values in a result vector like this

Note that this result is not a vector, but a vertex sequence, i.e. igraph.vs.

I think this is problematic:

• I am not currently comfortable with igraph.vs having NAs. On the C side, an igraph_vs_t, which an igraph.vs would typically map to, cannot have missing values. To make things worse, R arbitrarily designates a particular integer as the "NA value", but on the C side, this will appears as a normal integer. We don't want to have to know about R's NA weirdness in the C library. Starting with igraph 0.10, vertex indices are proper integers.
• Semantically, the result here is not a vertex sequence, so it shouldn't be represented as an igraph.vs at all. What we have instead is a vertex -> vertex mapping. And yes, some vertices do not map to anything, we need to represent that somehow (with an NA or otherwise). To allow that, isn't it better to use a different result type than igraph.vs instead of trying to tolerate NAs in vertex sequences?

@krlmlr Before making up your mind on this, I strongly suggest you implement a Strahler index computation using bfs() to experience the issues first-hand.

---

As I said above, the first issue is whether the result should be an igraph.vs at all, give that there is a need for representing missing values. There is a second issue as well. The result here is what we now call a "parent vector" in the C core. We standardized the parent vector representations in C, igraph/igraph#1880, and decided to also represent the reason why a parent is missing. Typically: -1 indicates a root and -2 indicates an unprocessed/unreachable vertex. While in R it is perfectly idiomatic to use NA for missing values, how do we represent why a value is missing? The distinction could be dropped in the R interface, but then we'd be discarding useful information that is not recoverable otherwise.