Revision history [back]
 | 1 | initial version |
You could list all of the neighborhoods and see if there are any duplicates:
sage: g = graphs.DiamondGraph()
sage: [g.neighbors(v) for v in g.vertex_iterator()]
[[1, 2], [0, 2, 3], [0, 1, 3], [1, 2]]
g[v] is equivalent to g.neighbors(v), so we could do this instead:
sage: g = graphs.DiamondGraph()
sage: [g[v] for v in g.vertex_iterator()]
[[1, 2], [0, 2, 3], [0, 1, 3], [1, 2]]
There are indeed duplicates; how to detect them? You can search the internet for "Python does list contain duplicates" to find lots of options, but one choice is to convert this list to a set, since sets do not contain duplicates. Sets cannot contain lists as elements, though, so convert each neighborhood to a tuple first:
sage: nbhds = [tuple(g[v]) for v in g.vertex_iterator()]
sage: nbhds
[(1, 2), (0, 2, 3), (0, 1, 3), (1, 2)]
sage: set(nbhds)
{(0, 1, 3), (0, 2, 3), (1, 2)}
sage: len(nbhds)
4
sage: len(set(nbhds))
3
So you can test whether len(nbhds) == len(set(nbhds)).
Alternatively, the adjacency matrix records the neighbors of each vertex: there is a 1 in the (i,j) entry of the matrix if there is an edge between vertices i and j, or equivalently, row i of the matrix has 1's in the columns where its neighbors are. So if two rows of the matrix are the same, then two vertices have the same neighborhoods. You can write a similar test to detect this.
