[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[igraph] using colors when counting isomorphisms (also indexing)
From: |
Jason Cory Brunson |
Subject: |
[igraph] using colors when counting isomorphisms (also indexing) |
Date: |
Thu, 07 Mar 2013 14:41:02 -0500 |
User-agent: |
Mozilla/5.0 (Macintosh; Intel Mac OS X 10.6; rv:17.0) Gecko/20130216 Thunderbird/17.0.3 |
The use of colors with the graph-isomorphism functions seems inconsistent and
problematic. I am sorry if this is old news; i do not see this topic in the
help archives.
My understanding is that when both graphs have specified vertex colors (for
instance), the isomorphisms tallied are restricted only by having each vertex
map to a vertex of the same color. Hence, this makes sense:
g1 <- graph.ring(4)
g2 <- graph.ring(4)
V(g1)$color <- rep(1, length = vcount(g1))
V(g2)$color <- rep(2, length = vcount(g2))
graph.count.isomorphisms.vf2(g1, g2)
[1] 0
graph.count.isomorphisms.vf2(g1, g2, vertex.color1 = NULL, vertex.color2 = NULL)
[2] 8
However, this example (simplified from those in the documentation) is
problematic:
V(g1)$color <- rep(1:2, length = vcount(g1))
V(g2)$color <- rep(1:2, length = vcount(g2))
graph.count.isomorphisms.vf2(g1, g2)
[1] 2
It seems to me that there should be four isomorphisms: two mapping node 1 to
node 1 and two mapping node 1 to node 3.
Any help reconciling this issue would be greatly appreciated!
Also, the indices of the vertices returned by graph.get.isomorphisms are 1 less
than they should be (possibly a relic of previous versions when graphs begin
with vertex 0?):
graph.get.isomorphisms.vf2(g1, g2)
[[1]]
[1] 0 1 2 3
[[2]]
[1] 2 1 0 3
Cory Brunson
- [igraph] using colors when counting isomorphisms (also indexing),
Jason Cory Brunson <=