question about function max_cardinality

I’m using the “max_cardinality” function in the R package “igraph” and I meet a problem in explainning the meaning of the ordering from this function. Here is the example,

testGraph8 <- graph_from_literal(1-3, 1-4, 1-7,
                                 2-4, 2-5,
                                 3-4, 3-7,
                                 4-5, 4-7,
                                 5-6, 5-7,


The result is

+ 7/7 vertices, named, from 287e480:
[1] 6 7 2 5 1 4 3

[1] 5 7 6 2 3 4 1

According to the manual, “alpha” is the ordering from maximum cardinality search (MCS). However, if we choose 6 in Step-1 in MCS and 7 in Step-2, in Step-3 we should choose 5 rather than 2.

I’m thinking maybe it means the perfect elimination ordering hence I reverse the order of “alpha” to check if (3,4,1,5,2,7,6) is the order from MCS. Then I met a problem where in Step-4, 7 should be chosen rathen than 5.

May I ask the meaning of the output of this function and whether I made any mistakes?

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")
    res <- .Call(C_R_igraph_maximum_cardinality_search, graph)
    if (igraph_opt("")) {
        res$alpha <- create_vs(graph, res$alpha)

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.
1 Like

My suggestion is to return the ranks in alpha, i.e. be consistent with the C interface and the referenced paper’s notation.

We could add another, differently named component to the result list which has the vertices in maximum cardinality order.