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:
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.
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!
On Thu, Nov 8, 2012 at 3:29 AM, Tamás Nepusz <nta...@gmail.com> wrote:
> > 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:
> 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.
> 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:
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!
On Thu, Nov 8, 2012 at 7:20 AM, Tamás Nepusz <nta...@gmail.com> wrote:
> > 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:
