Compatibility with igraph 2.0.0

[krlmlr]

@jefferis @jdmanton @mmc46 @dmurdoch: This package fails its checks for the release candidate for igraph 2.0.0. See https://github.com/igraph/rigraph/blob/igraph-0.10/revdep/problems.md for details.

Is this a problem in your package? Should we be doing things differently?

Install the 2.0.0 release candidate using pak::pak("igraph/[email protected]") .

We're planning to release igraph 2.0.0 just before CRAN's closing on Christmas. This should give us at least until mid-January to resolve this and keep CRAN happy at the same time. Thank you for your help!

Tracker: igraph/rigraph#989.

[dmurdoch]

@krlmlr: This is not related to nat, but I failed to install the new igraph, with this error:

clang -arch x86_64 -I"/Library/Frameworks/R.framework/Resources/include" -DNDEBUG -I/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include -DUSING_R -I. -Ivendor -Ivendor/cigraph/src -Ivendor/cigraph/include -Ivendor/cigraph/vendor -DNDEBUG -DNTIMER -DNPRINT -DINTERNAL_ARPACK -DIGRAPH_THREAD_LOCAL= -DPRPACK_IGRAPH_SUPPORT -D_GNU_SOURCE=1 -I'/Library/Frameworks/R.framework/Versions/4.3-x86_64/Resources/library/cpp11/include' -I/opt/R/x86_64/include    -fPIC  -falign-functions=64 -Wall -g -O2  -Wall -pedantic -fdiagnostics-color=always -c vendor/cigraph/src/misc/feedback_arc_set.c -o vendor/cigraph/src/misc/feedback_arc_set.o
In file included from vendor/cigraph/src/misc/feedback_arc_set.c:35:
vendor/cigraph/src/internal/glpk_support.h:39:10: fatal error: 'glpk.h' file not found
#include <glpk.h>
         ^~~~~~~~
1 error generated.
make: *** [vendor/cigraph/src/misc/feedback_arc_set.o] Error 1
ERROR: compilation failed for package ‘igraph’
* removing ‘/private/var/folders/d6/s97fjjxd3_9353x_lwb692100000gn/T/RtmptDH0YG/pkg-lib3d9954f69d2e/igraph’

glpk is listed as an optional system requirement, and I apparently don't have it available (on a Mac). If it's optional, maybe the configuration should have detected that it's missing and avoided requiring it?

[dmurdoch]

After installing glpk, I got the same error as shown in the "problems" link. Here's a bit more context:

── Error (test-neuron.R:278:3): we can subset a neuron with a vertex sequence ──
Error in `igraph::delete.vertices(g, verticestoprune)`: At vendor/cigraph/src/graph/iterators.c:828 : Cannot create iterator, invalid vertex ID. Invalid vertex ID
Backtrace:
    ▆
 1. ├─testthat::expect_is(...) at test-neuron.R:278:3
 2. │ └─testthat::quasi_label(enquo(object), label, arg = "object")
 3. │   └─rlang::eval_bare(expr, quo_get_env(quo))
 4. ├─base::subset(n, n_graph_dfs$order, invert = T)
 5. └─nat:::subset.neuron(n, n_graph_dfs$order, invert = T)
 6.   └─nat::prune_vertices(x, r, invert = !invert, ...) at nat/R/neuron.R:839:3
 7.     └─igraph::delete.vertices(g, verticestoprune) at nat/R/ngraph.R:543:3
[ FAIL 2 | WARN 0 | SKIP 0 | PASS 101 ]

I don't know either nat or igraph well enough to be able to guess where the problem lies, but it doesn't look like it's related to rgl, so I'll leave it to others.

[krlmlr]

Thanks, good catch! I'll make a note to fix our configuration code here.

[jefferis]

Thanks both.

@krlmlr any immediate clues based on this as to what I should be looking for based on known igraph changes?

Error in `igraph::delete.vertices(g, verticestoprune)`: At vendor/cigraph/src/graph/iterators.c:828 : Cannot create iterator, invalid vertex ID. Invalid vertex ID

[krlmlr]

Not sure, but a minimal reproducible example would already help.

[jefferis]

OK so @krlmlr this is because of a change in the behaviour of igraph::graph.dfs(,unreachable=F)
Is this change intended?

> n_graph_dfs.old$order
  [1]  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63
 [17]  64  65  66  67  68  69  70  71  72  73  74  75  76  77  78  79
 [33]  80  81  82  83  84  85  86  87  88  89  90  91  92  93  94  95
 [49]  96  97  98  99 100 101 102 103 104 105 106 107 108 109 110 111
 [65] 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127
 [81] 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143
 [97] 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159
[113] 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175
[129] 176 177 178 179 180 NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN
[145] NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN
[161] NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN
[177] NaN NaN NaN NaN

vs

> n_graph_dfs.new$order
  [1]  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63
 [17]  64  65  66  67  68  69  70  71  72  73  74  75  76  77  78  79
 [33]  80  81  82  83  84  85  86  87  88  89  90  91  92  93  94  95
 [49]  96  97  98  99 100 101 102 103 104 105 106 107 108 109 110 111
 [65] 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127
 [81] 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143
 [97] 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159
[113] 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175
[129] 176 177 178 179 180   0   0   0   0   0   0   0   0   0   0   0
[145]   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0
[161]   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0
[177]   0   0   0   0

[krlmlr]

@szhorvat: Can you please comment?

We did change some of the bfs() outputs preemptively in igraph 1.6.0, seems I missed this component (and perhaps others).

[krlmlr]

@jefferis: Thanks for tracking this down!

[szhorvat]

@krlmlr It's best to ask @ntamas as I was not the last one to touch this function. In fact I am not deeply familiar with it because I did not expose it in the Mathematica interface. Mathematica's built-in version is much more powerful than what's in igraph, and in fact I was hoping to get a much improved version in before 1.0 ...

But for now, what I can see in the docs is that this is an intentional change. The order vector will have the same length as the vertex count, and will be padded with -1, which are transformed to 0 in R. This does not mean that the R interface has to follow the same. Actually, I cannot reproduce this:

> g<-make_graph(c(1,2, 3,4))
> dfs(g, root=1, unreachable = F)$order
+ 2/4 vertices, from 277be4a:
[1] 1 2

Is the truncation to 2 elements intentional in R, or some side effect of converting to a vertex sequence?

Personally, I do think that truncation makes more sense than padding ... but again, ask @ntamas.

I am sick at the moment and my mind is not very clear.

[szhorvat]

One more note: in 0.9, indices were represented as double, so using NaN to fill in "missing" values was an option. In 0.10 we use an integer type, so no more NaN. Usually, the solution is a negative number. This is what we do specifically with "parent vectors" that represent a rooted tree. But this order vector is specific to DFS/BFS.

[ntamas]

The order component of the DFS and BFS result objects is indeed weird. It is supposed to store the order in which the vertices were visited in DFS or BFS order. The C core resizes this vector to the number of nodes and then fills it with a default value. The default value was NaN in 0.9 where we used an igraph_vector_t type (which consists of doubles) due to igraph's R heritage and the fact that R vectors are floating-point vectors by default. In igraph 0.10 we started to prune these historical artifacts and replaces the order member with an igraph_vector_int_t on the C side. As a consequence, we needed to change the default value from NaN to -1 on the C side. Since R uses 1-based indexing, the vector on the C side is offset by 1, so -1 becomes 0 and this becomes the padding on the R side.

I don't know what the reason for the padding is; this comes from the early days of igraph before my time. We did not bother to change it for fears of breaking backward compatibility with R. The only advantage I see right now is that we don't need to dynamically reallocate the vector as new items are appended to it during the traversal.

@krlmlr What's the plan with dealing this on the R side? If you plan to add a custom function that restores NaN instead of 0 to remain backward compatible with earlier releases, maybe it would be time to drop the padding on the C side and design the conversion function on the R side in a way that restores the padding in pure R?

[krlmlr]

New anticipated release data: January 12.

We propagated the new values for the other components of bfs() . We could change 0 to NaN to keep consistency, but I wonder if we should use -1 or any other value.

[ntamas]

Whichever makes more sense in the R context, I'm not that familiar with existing conventions in R. I think that the two most promising options are: 1) restore the original behaviour with NaN for sake of backward compatibility, or 2) if we decide to let go of backward compatibility, then let's fix the root of the issue and truncate the vector properly.

[krlmlr]

I think the new behavior of dfs() is more useful, but I'll restore the original behavior of padding with NA . Running revdepchecks now.

library(igraph)
#> 
#> Attaching package: 'igraph'
#> The following objects are masked from 'package:stats':
#> 
#>     decompose, spectrum
#> The following object is masked from 'package:base':
#> 
#>     union
g <- make_graph(c(1, 2, 3, 4))
g
#> IGRAPH 8bd2d6e D--- 4 2 -- 
#> + edges from 8bd2d6e:
#> [1] 1->2 3->4
dfs(g, root = 3, order.out = TRUE, unreachable = FALSE, dist = TRUE)
#> $root
#> [1] 3
#> 
#> $mode
#> [1] "out"
#> 
#> $order
#> + 4/4 vertices, from 8bd2d6e:
#> [1]  3  4 NA NA
#> 
#> $order.out
#> + 4/4 vertices, from 8bd2d6e:
#> [1]  4  3 NA NA
#> 
#> $father
#> NULL
#> 
#> $dist
#> [1] -1 -1  0  1
#> 
#> $neimode
#> [1] "out"
bfs(g, root = 3, unreachable = FALSE, dist = TRUE)
#> $root
#> [1] 3
#> 
#> $mode
#> [1] "out"
#> 
#> $order
#> + 4/4 vertices, from 8bd2d6e:
#> [1]  3  4 NA NA
#> 
#> $rank
#> NULL
#> 
#> $father
#> NULL
#> 
#> $pred
#> NULL
#> 
#> $succ
#> NULL
#> 
#> $dist
#> [1] -1 -1  0  1
#> 
#> $neimode
#> [1] "out"

^{Created on 2023-12-31 with reprex v2.0.2}

[krlmlr]

Unfortunately, the problem with nat persists even with the change.

[jefferis]

@krlmlr can you tell me which branch I should test against?

pak::pak("igraph/[email protected]")

is no longer an option and so I tried:

pak::pak("igraph/rigraph@f-nat-dfs")

This does indeed fail for the same example, but the dfs output has changed for unreachable vertices (NaN vs 0 below). I can update my code to be resistant to this variation, but it would be good to know your final position on the dfs return structure first. With many thanks, Greg.

old igraph 1.5.1

> n_graph_dfs
$root
[1] 48

$mode
[1] "out"

$order
  [1]  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66
 [20]  67  68  69  70  71  72  73  74  75  76  77  78  79  80  81  82  83  84  85
 [39]  86  87  88  89  90  91  92  93  94  95  96  97  98  99 100 101 102 103 104
 [58] 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123
 [77] 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142
 [96] 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161
[115] 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180
[134] NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN
[153] NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN
[172] NaN NaN NaN NaN NaN NaN NaN NaN NaN

$order.out
NULL

$father
NULL

$dist
NULL

$neimode
[1] "out"

vs pak::pak("igraph/rigraph@f-nat-dfs")

$root
[1] 48

$mode
[1] "out"

$order
  [1]  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66
 [20]  67  68  69  70  71  72  73  74  75  76  77  78  79  80  81  82  83  84  85
 [39]  86  87  88  89  90  91  92  93  94  95  96  97  98  99 100 101 102 103 104
 [58] 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123
 [77] 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142
 [96] 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161
[115] 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180
[134]   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0
[153]   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0
[172]   0   0   0   0   0   0   0   0   0

$order.out
NULL

$father
NULL

$dist
NULL

$neimode
[1] "out"

[jefferis]

@krlmlr a note for me the full suite of nat tests passes against f-nat-dfs so long as I handle the difference between the dfs signalling unreachable nodes with 0 vs NaN. Further details about the failures you see would be helpful. See #518 for changes I have made.

[krlmlr]

Thanks. Development has now moved to the mainline, pak::pak("igraph/rigraph") is best. I reviewed the PR quickly, looks good if it passes checks against dev igraph.

[jefferis]

Thanks @krlmlr. This is still unresolved because igraph/rigraph#1062 doesn't quite behave as I would expect. Reprex:

> g <- make_ring(10) %du% make_ring(10)
> as.vector(igraph::bfs(g, 1, unreachable = FALSE)$order)
 [1]  1  2 10  3  9  4  8  5  7  6
> igraph::igraph_options(return.vs.es = FALSE)
> as.vector(igraph::bfs(g, 1, unreachable = FALSE)$order)
 [1]  1  2 10  3  9  4  8  5  7  6  0  0  0  0  0  0  0  0  0  0
> igraph::igraph_options(return.vs.es = T)
> as.vector(igraph::bfs(g, 1, unreachable = FALSE)$order)
 [1]  1  2 10  3  9  4  8  5  7  6

[krlmlr]

Thanks for the heads-up, fixed the vs-es = FALSE case in igraph.

We're planning to send igraph to CRAN on January 23.