I think there may be a bug in igraph’s R interface here, but not in the underlying C function.
The C function returns two vectors: alpha and alpham1.
alpha is simply a number, or “rank”, assigned to each vertex. It has the property that visiting vertices in order of decreasing alpha (i.e. highest rank first) corresponds to the maximum cardinality search order, i.e. always visiting the vertex with the most already visited neighbours. Crucially, alpha is not a vertex index. It is just a way to define an ordering.
alpham1 on the other hand is a vertex index. This vector contains the indices of vertices, in reverse maximum cardinality order.
What may be confusing with the example you give here is that in your graph, vertex indices and vertex names are not the same. These are the vertex names:
> V(testGraph8)
+ 7/7 vertices, named, from d14e217:
[1] 1 3 4 7 2 5 6
The 1st vertex has name 1, the 2nd vertex has name 3, and so on.
The bug in the R interface
This is the definition of the function:
function (graph)
{
if (!is_igraph(graph)) {
stop("Not a graph object")
}
on.exit(.Call(C_R_igraph_finalizer))
res <- .Call(C_R_igraph_maximum_cardinality_search, graph)
if (igraph_opt("return.vs.es")) {
res$alpha <- create_vs(graph, res$alpha)
}
res
}
Note that the function treats the alpha returned from the C function as vertex indices and converts them to vertex names. Again, the problem is that alpha are not vertex indices, so this gives a wrong result.
To get the vertex names in maximum cardinality order, we could use:
> V(testGraph8)[rev(am1$alpham1)]
+ 7/7 vertices, named, from d14e217:
[1] 1 7 4 3 5 6 2
Here’s the search order we get, as animated with the Mathematica interface of igraph (IGraph/M). I’m sorry, I’m not experienced with R.
I am glad that you brought this up, as the Mathematica interface had the same bug. I must have used the R implementation as a guide, and I was not familiar with the concept of maximum cardinality search.
When the vertex names happened to be equal to the vertex indices, the alpha result was “correct”, i.e. it corresponded to the \alpha described in the referenced paper (which again are not vertex indices, just numbers, or “ranks”).
Pinging @Gabor and @vtraag to verify my assessment above.
We need to decide how to fix this:
- Do we want the result from the function to be a list of vertex names, ordered according to maximum cardinality search? This could be obtained with
V(testGraph8)[rev(am1$alpham1)]
- Or do we want them to be \alpha values? In this case
alpha would be the inverse permutation of alpham1.
