[igraph] Contracting two vertices into one in Igraph - error

[Priyanka Kadiyala]

Hello All,

I'm trying to implement the Nagamochi-Ibaraki algorithm and have the following problem:

I have picked two vertices, say "x" and "y" that need to be contracted into a single vertex. I have tried to understand the contract.vertices function but the mapping parameter is confusing me. The total vertices in my graph are 26, and they will be contracted recursively until I have only 2 nodes left. Can you please help me with this? I'm not sure what I'm doing wrong.

My graph is this: g1 <- barabasi.game(26, m=4, directed=FALSE, algorithm="bag")

And after I pick two nodes, say 25, 26, which have multiple edges between them, I'm trying to merge them into a single vertex:

> g2 <- contract.vertices(g1,(25:26),vertex.attr.comb=toString)
Error in contract.vertices(g1, (25:26), vertex.attr.comb = toString) :
  At structural_properties.c:6922 : Invalid mapping vector length, Invalid value

Thank you,
Krishna.

[Tamás Nepusz]

> And after I pick two nodes, say 25, 26, which have multiple edges between them, I'm trying to merge them into a single vertex:

The right contraction vector in this case is:

c(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,25)

The reason is as follows. In the contraction vector, the i-th element must contain the _new_ ID of vertex i of the _old_ graph (making sure that the new IDs are in a continuous range from 1 to the desired number of vertices in the new graph). This is to allow making several contractions and permutations in a single step. Since the _new_ ID of every vertex except your vertex 26 must stay the same, the first 25 elements of the vector are 1:25. The 26th element must be 25 because you want the new ID of vertex 26 to become 25 (since you merged that into vertex 25).

In general, if you want to merge vertex v into vertex u (assuming that v > u), you will need a contraction vector as follows:

vec <- c(1:(v-1), u, v:(vcount(g)-1))

If v < u, just swap u and v and do the same thing.

Best,
Tamas


_______________________________________________
igraph-help mailing list
igrap...@nongnu.org
https://lists.nongnu.org/mailman/listinfo/igraph-help

[Priyanka Kadiyala]

Hi Tamas,

Thank you for your help. I understand this function better, but here's the other problem:

Of the vertices 1:26, I can also choose two nodes that are not consecutive, as in, I can choose to merge (1,5) or (7,18) into a single vertex. Can this be done?

Thank you for getting back to me! I really appreciate it!

Best,
Krishna.

[Tamás Nepusz]

> Of the vertices 1:26, I can also choose two nodes that are not consecutive, as in, I can choose to merge (1,5) or (7,18) into a single vertex. Can this be done?

Quoting myself:

> In general, if you want to merge vertex v into vertex u (assuming that v > u), you will need a contraction vector as follows:
>
> vec <- c(1:(v-1), u, v:(vcount(g)-1))
>
> If v < u, just swap u and v and do the same thing.

In your case, u=1 and v=5 (since you are merging node 5 into node 1), so the contraction vector is:

c(1:4, 1, 5:(vcount(g)-1))

[Priyanka Kadiyala]

Thank you! I had read that part, I just implemented it wrong and was getting an error, the example clarified it further and I successfully tried contracting a few more nodes.

I really appreciate your help and patience! Thank you!