Question: Filter out non-isomorphic graphs by canonical labeling

I would like to remove isomorphs from some graphs. That is to filter out non-isomorphic graphs.

graph_list := [GraphTheory:-CompleteGraph(3), GraphTheory:-PathGraph(3),Graph({{a,b},{b,c},{c,a}})]:

# Create a table to store non-isomorphic graphs
non_isomorphic_graphs := table():

# Counter for indexing the table
counter := 1:

# Iterate over each graph and check if it is isomorphic to any of the stored graphs
for g in graph_list do
    is_isomorphic := false:
    for key in indices(non_isomorphic_graphs,'nolist') do
        if GraphTheory:-IsIsomorphic(g, non_isomorphic_graphs[key]) then
            is_isomorphic := true:
            break:
        end if:
    end do:
    if not is_isomorphic then
        non_isomorphic_graphs[counter] := g:
        counter := counter + 1:
    end if:
end do:
op(non_isomorphic_graphs)
DrawGraph~(non_isomorphic_graphs,  layoutoptions = [neutral_color = "pink", initial = spring])

 

A canonical form is a labeled graph Canon(G) that is isomorphic to G, such that every graph that is isomorphic to G has the same canonical form as G. I noticed that Maple has a function called CanonicalGraph. Can this function achieve the effect I want? I can easily achieve this by combining the  canonical form and property of sets  in  Sage.

graph_list = [Graph([(0, "a"), ("a", 2), (2, 0)]),graphs.PathGraph(3), graphs.CompleteGraph(3)]
non_isomorphic_graphs_labels = {g.canonical_label().copy(immutable=True) for g in graph_list}

 

 

An underlying motivation:My collaborators and I designed generation rules (algorithms) for 1-planar 4-trees;see https://arxiv.org/abs/2404.15663. Since the generating process is based on 1-planar embeddings, it will ultimately require filtering non-isomorphic graphs among a list of embeddings. I would be especially delighted to see that someone implement our algorithm in the future. Currently, I am stuck on handling some labeling details. It is somewhat similar to generating Apollonian networks (planar 3-trees). However, since its simplicial vertices are only two, the growth rate will not be too fast as the number of vertices increases.

Please Wait...