Advanced Search

Question: How do I use IsIsomorphic on large amount of small graphs?

Question:How do I use IsIsomorphic on large amount of small graphs?

tomasmedici 15 Maple 18
graph matrix isomorphism
April 04 2017
3

Hello,

I am trying to write a procedure to see, which (di)-graphs are isomorphic (here represented by there 3*3 adjecency-matrices). When I try the procedure for all 3*3-matrices with entries in {0,1} (there are 512 of them), I get the following error:
"Error, (in GraphTheory:-IsIsomorphic) invalid subscript selector"

Can you possibly say, what I am doing wrong? My code is the following:

getIso3 := proc(liste)
  local i,k,M1,c,d:
  c := 0:
  M1 := [[liste[1]]]:
  for i from 2 to numelems(liste) do
    for k from 1 to numelems(M1) do
        if IsIsomorphic(Digraph([a,b,c], liste[i]),Digraph([a,b,c],M1[k][1])) then
          M1[k] := [op(M1[k]), liste[i]]:
          c := 1:
        end if:
    end do:
    if c=0 then
      M1 := [op(M1), [liste[i]]]:
    else
      c := 0:
    end if:   end do: 
  return(M1):
end proc:

 

My input is a list (JJ) of 512 3*3 matrices constructed the following way :

all9Perm := proc(list)
  local P,i,m,n,A:
  P := list:
  for i from 0 to 9 do
    m:= i:  n:= 9-i:
    A := combinat:-permute([1$n, 0$m]):
    P := [op(P), op(1..numelems(A),A)]:
  od:
  return(P):
end proc:
K := []:
L := all9Perm(K):
listoflistsToListofmatrices := proc(liste)
  local M,i:
  M := []:
  for i from 1 to numelems(liste) do
      M := [op(M), Matrix([
          [ liste[i][1] , liste[i][2] , liste[i][3] ],
          [ liste[i][4] , liste[i][5] , liste[i][6] ],
          [ liste[i][7] , liste[i][8] , liste[i][9] ]])
          ]:
  end do:
  return(M):
end proc:
JJ := listoflistsToListofmatrices(L):

 

When I run this procedure on some of the 512 matrices it does work, but it crashes somewhere around matrix 350. I have try so split the list of the 512 matrices, and I am able to run the procedure on these splits, but this is very inconvenient :-)

I hope you can help me. Also if this can be done in an easier way - I am new to programming and recieve help with a smile.

Yours, Tomas.
Please Wait...