Input: Two undirected simple graphs G1 and G2, each having n vertices.
Output: True if G1 ? = G2; False otherwise.
for i ? 1,2 do
Ai ? adjacency matrix of Gi
pi ? permutation equivalence class of Ai
A0 i ? lexicographically maximal element of pi
if A0 1 = A0 2 then
return True
return Falseanyone have any idea how to implement this in Sage ?
You can test if G1≅G2 using the following function f.
sage: f = lambda g,h: g.is_isomorphic(h)
sage: G = graphs.CubeGraph(3)
sage: H = graphs.HexahedralGraph()
sage: f(G,H)
TrueIf you really want to use the canonical label then, given a Graph g, you can obtain it by using g.canonical_label() and then just compare the adjacency matrices.
Asked: 12 years ago
Seen: 467 times
Last updated: Mar 14 '13
Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.