lcz

994 Reputation

11 Badges

5 years, 91 days
changsha, China

MaplePrimes Activity


These are questions asked by lcz

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.

The following  question I asked a long time ago.

The user Carl Love provided a nice answer regarding the counting of cycles. Back then, I was only interested in the number of cycles, but now I am also interested in finding out these cycles.

 

I noticed sand15's answer where he (or she) attempted to use the cycle basis to find all cycles. This approach is theoretically viable. However, it seems that his (her) implementation had some instances of missing cycles.  (mmcdara‘s answer is also missing some cycles)

So I brought up this question again to draw attention to it. The only distinction is that I may have specifically mentioned the use of a cycle basis method. Additionally, I may give another question:

  • How do we generate all cycles with a specific length (by cycle basis)?

 However, I remain open-minded about alternatives that do not involve a cycle basis. 

The SageMath approach for that can be referred to the link, which is actually why I remembered this question. It feels like the function in linear algebra that generates all elements through a basis would be effective.

g=graphs.OctahedralGraph()
def gen_simple_cycles(G):
    C = [frozenset(tuple(sorted(e[:2])) for e in c) for c in G.cycle_basis(output='edge')]
    for S in Subsets(C):
        T = set()
        for c in S:
            T = T.symmetric_difference(c)
        H = Graph(T, format='list_of_edges')
        if H.is_eulerian() and max(H.degree(),default=0)==2:
            yield H.eulerian_circuit(return_vertices=True)[1]
list(gen_simple_cycles(g))

[[0, 4, 2, 0],
 [0, 4, 3, 0],
 [0, 4, 5, 1, 0],
 [2, 5, 4, 2],
 [3, 5, 4, 3],
 [0, 3, 1, 0],
 [0, 2, 1, 0],
 [0, 3, 4, 2, 0],
 [0, 2, 4, 5, 1, 0],
 [0, 4, 5, 2, 0],
 [0, 4, 2, 1, 0],
 [0, 3, 4, 5, 1, 0],
 [0, 4, 5, 3, 0],
 [0, 4, 3, 1, 0],
 [0, 4, 2, 5, 1, 0],
 [0, 4, 3, 5, 1, 0],
 [0, 4, 5, 1, 3, 0],
 [0, 4, 5, 1, 2, 0],
 [2, 5, 3, 4, 2],
 [0, 3, 1, 2, 0],
 [0, 3, 4, 5, 2, 0],
 [0, 3, 5, 4, 2, 0],
 [0, 2, 4, 3, 1, 0],
 [0, 3, 4, 2, 1, 0],
 [0, 2, 5, 1, 0],
 [0, 2, 4, 3, 5, 1, 0],
 [0, 3, 1, 5, 4, 2, 0],
 [1, 5, 4, 2, 1],
 [0, 4, 3, 5, 2, 0],
 [0, 4, 5, 2, 1, 0],
 [0, 4, 2, 1, 3, 0],
 [0, 3, 4, 2, 5, 1, 0],
 [0, 3, 5, 1, 0],
 [1, 5, 4, 3, 1],
 [0, 3, 4, 5, 1, 2, 0],
 [0, 4, 2, 5, 3, 0],
 [0, 4, 5, 3, 1, 0],
 [0, 4, 3, 1, 2, 0],
 [0, 4, 2, 5, 1, 3, 0],
 [0, 4, 3, 5, 1, 2, 0],
 [0, 3, 5, 2, 0],
 [0, 2, 5, 4, 3, 1, 0],
 [0, 3, 4, 5, 2, 1, 0],
 [0, 2, 4, 5, 3, 1, 0],
 [0, 3, 5, 4, 2, 1, 0],
 [1, 3, 4, 2, 1],
 [0, 3, 1, 5, 2, 0],
 [1, 5, 2, 1],
 [1, 5, 3, 4, 2, 1],
 [0, 4, 3, 5, 2, 1, 0],
 [0, 4, 5, 2, 1, 3, 0],
 [1, 5, 2, 4, 3, 1],
 [1, 5, 3, 1],
 [0, 3, 5, 1, 2, 0],
 [0, 4, 2, 5, 3, 1, 0],
 [0, 4, 5, 3, 1, 2, 0],
 [0, 4, 3, 1, 5, 2, 0],
 [0, 4, 2, 1, 5, 3, 0],
 [0, 2, 5, 3, 1, 0],
 [0, 3, 5, 2, 1, 0],
 [1, 3, 4, 5, 2, 1],
 [1, 3, 5, 4, 2, 1],
 [1, 3, 5, 2, 1]]

Total: 63 cycles.

 

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