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 False
anyone have any idea how to implement this in Sage ?
You can test if $G_1\cong G_2$ 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)
True
If 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: 2013-03-14 06:22:04 +0200
Seen: 322 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.