lcz

1004 Reputation

11 Badges

5 years, 152 days
changsha, China

MaplePrimes Activity


These are questions asked by lcz

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.

AllGraphs is a new function in Maple 2024. Good things!

However, it seems that most of its functionalities are already provided by NonIsomorphicGraphs, and its speed even lags behind that of NonIsomorphicGraphs 

 

I'm curious about what truly sets this function apart from existing ones. It generates isomorphic graphs if nonisomorphic=falseBut I donot know what its application is. Supporting directed graphs is a new thing, but its speed is not well.

iterator := GraphTheory[AllGraphs](vertices = 6, edges =6..7, connected, nonisomorphic)
s:=[seq(p, p = iterator)]:
nops(s)

Note that this function is suitable for generating non-isomorphic connected graphs with 6 vertices and either 6 or 7 edges. It doesn't hold an advantage in terms of speed, andNonIsomorphicGraphs also provides an iteration option.

The (Induced) Subgraph Isomorphism computational problem is, given H and G, determine whether there is a (induced) subgraph isomorphism from H to G. See https://en.wikipedia.org/wiki/Induced_subgraph_isomorphism_problem

In Maple, IsSubgraphIsomorphic(G1,G2)  returns true if G1 is isomorphic to some subgraph of G2. However, it does not provide options for induced subgraphs. For example, 

with(GraphTheory):
claw:=CompleteGraph(1,3);
g:=CompleteGraph(2,2,2,2):
DrawGraph(g);
IsSubgraphIsomorphic(claw,g) #true

So the graph g contains a claw as a subgraph. But every claw in graph g  is non-induced. So g does not contain any induced claw. Maple does not appear to have this feature to determine if a graph contains a induced subgraph isomorphic to another graph. It is unclear whether we can modify some code in IsSubgraphIsomorphic  to achieve this goal.

The following code effectively converts the image to the JPG format.
with(GraphTheory):
s:=DrawGraph(CompleteGraph(5),size=[250,250])
Export("D:\\s1.jpg",s)

But I would like to export it using PDF format. However, the modified code below seems to be quite unsuccessful. I am aware that Maple has export options in the front end, but I still prefer to use code for this purpose.

Export("D:\\s1.pdf",s)

Error, (in Export) invalid input: member received _ImportExport:-InfoTable["PDF"][4], which is not valid for its 2nd argument, s

There are two reasons for this.

with(GraphTheory):
Graphs:=[NonIsomorphicGraphs(6,8,output=graphs,outputform = graph)]:
num_g:=nops(Graphs):
num:=ceil((num_g)/5.):
Matrix (num,5,(i,j)->`if`((i-1)*5+j<=num_g, DrawGraph(Graphs[(i-1)*5+j],size=[250,250] ,overrideoptions ,showlabels=false,style=planar, stylesheet =  [
 vertexcolor     = orange
,vertexfontcolor = black
,vertexborder    = false
,edgethickness   = 0.6
,edgecolor       = MidnightBlue
,vertexshape     =  "circle"
,vertexfont      = [Arial, 4],
vertexthickness=5], caption = cat(H__,5*(i-1)+j),captionfont=["ROMAN",7]),plot(x = 0 .. 1, axes = none))):
DocumentTools:-Tabulate (M1[1..5,.. ],widthmode=percentage ,width=80 , exterior =all):

There are various variants of graph coloring, such as when I want to compute the star chromatic number of a graph, Maple (or Mathematica) seems not to provide relevant functions.

Fortunately, the software ColPack   offers this functionality (Note: I just noticed that this software also uses greedy coloring instead of accuracy). However, it supports the MTX format. So, the question is: 

  •  How can I write a graph in MTX format?

And 

  •  how can the MTX format be converted into a graph format?

Of course, I would like to perform these operations in Maple.  (SageMath may have something)


The following is an example (bcsstk01.mtx) in the directory `ColPack-master/Graphs directory` of the source code of ColPack.

bcsstk01.mtx.txt

./ColPack -f ../../Graphs/bcsstk01.mtx -m STAR
 Out: 11

But I do not know what the graph in the example is. On the contrary, I would like to compute the star chromatic number of the Petersen graph, and I also don't know how to convert it into the MTX format like the above.

with(GraphTheory):
with(SpecialGraphs):
P:=PetersenGraph()

I don't understand what the very long decimal numbers (like 2.8322685185200e+06) in the third column in the MTX-file. Will it affect the  imformation of the entire graph?

 

For MTX format, see https://math.nist.gov/MatrixMarket/formats.html.  For graphs, the numbers in the third column can all be considered as 1 (with the first two columns representing vertices, and their adjacency). Of course, this is my interpretation and may not necessarily be correct.

1 2 3 4 5 6 7 Last Page 1 of 25