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`

.