Ask Your Question

Algorithm implementation in Sage

asked 2013-03-14 06:22:04 +0200

Mohab gravatar image

updated 2015-07-31 17:55:42 +0200

FrédéricC gravatar image

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 ?

edit retag flag offensive close merge delete

1 Answer

Sort by » oldest newest most voted

answered 2013-03-14 12:08:21 +0200

fidbc gravatar image

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)

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.

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools


Asked: 2013-03-14 06:22:04 +0200

Seen: 296 times

Last updated: Mar 14 '13