@nm @Carl Love Thank you very much for pointing out the reason. I hope that the Latex in Maple will be improved in the future.

Also, you can take a look at this link.

• https://stackoverflow.com/questions/57328273/algorithm-for-polygon-triangulation

I am interested in two aspects of this problem:

1. What is the time complexity of generating all possible triangulations? (I noticed that dharr's method is quite efficient.)

2. Can non-isomorphic triangulations of an n sided cyclic polygon  be generated? This is equivalent to generating all non-isomorphic maximal outerplanar graphs.

I just saw your addition, and   Export(..., B, format="delimited")can achieve this very well. That's great!

@acer It seems that I mixed up the rows and columns. Your code did achieve the effect I wanted. I noticed that the columns are separated by commas. It seems like these three columns are a bit too crowded.

Can we replace the commas between them with a space (or two, or more spaces) to improve readability? (Of course, if it would take up too much of your time, it's not necessary to make these changes.)

From a practical perspective, I recommend using SageMath (9.1+) for this problem because it has the function minimal_dominating_sets. It's not ruled out that Maple may implement it in the future.

It claims to use the algorithm described in Reference 1, but it's strange that the graphs mentioned in Reference 1 are all subject to some certain constraints. I'm not sure if the SageMath development team is aware of this issue.

1. Marthe Bonamy, Oscar Defrain, Marc Heinrich, Michał Pilipczuk, and Jean-Florent Raymond. Enumerating minimal dominating sets in K_t-free graphs and variants. arXiv 1810.00789

G = graphs.ButterflyGraph()
ll = list(G.minimal_dominating_sets())
G.show()
print(ll)

[{0, 1}, {1, 3}, {0, 2}, {2, 3}, {4}]

Then, we further determine whether the given vertex (for example,  vertex "1") is included in the whole minimal dominating sets.

result = [s for s in ll if 1 in s]

[{0, 1}, {1, 3}]

(This made me ponder whether it's necessary to find all the minimal dominating sets before filtering, or if there's a way to improve this algorithm to achieve OP's goal.)

@Carl Love I generated 572740300 directed graphs using nauty, and it takes up approximately 7G of space. Therefore, I split the file into 50 parts using some auxiliary tools  (like Split Byte in Windows). Each part is around 152 MB (11454806 graphs).

The main issue is still the inability to randomly access data from some files, as dharr  mentioned. We always have to start from the first line. Therefore, it's still very challenging for data sizes larger than 1 GB.

@dharr That's really unfortunate. It seems that a feasible solution is to split a file into multiple files.

@tomleslie  Both your codes are nice. But I cannot choose two answers as the best answer. Even your code involving regular expreeion is more in line with my expectations

@acer That's very helpful. I have another question: If I treat each single-digit number as a separate number, for example, in the previous string, 

[1,2,4,3,4,2,4,3,4,5,5,6,7,6,3,4,4,5,2,3,1,2,9,8,3,4,4,3]

How should I process it? One way I can think of is:

select(x-> type(parse(x),integer),  convert(S,list))

The purpose of raising these questions is to see how regular expressions are written in Maple. However, as you have shown, there are better and more concise built-in functions, which I also like very much.

@sursumCorda Is the transitive reduction of a directed graph unique? It is indeed very strange.

What I'm interested in is whether your graph can be reduced. I used the transitive_reduction function of the networkx package in Python to check, and It seems to indicate that this graph cannot be further reduced.

import networkx as nx
DG = nx.DiGraph([(3, 1), (9, 3), (4, 9), (14, 9), (10, 4), (5, 10), (15, 10), (11, 5), (19, 11), (12, 6),
                 (7, 12), (17, 12), (13, 7), (8, 13), (2, 8), (10, 14), (18, 14), (11, 15), (6, 19), (16, 19),
                 (23, 19), (13, 17), (15, 18), (21, 18), (12, 16),
                 (22, 16), (22, 23), (20, 22), (19, 21), (17, 20)])
TR = nx.transitive_reduction(DG)
print(TR)

DiGraph with 23 nodes and 30 edges

Because I am wondering whether the issue lies in non-reducible graphs or if the same problem also occurs for reducible graphs.

@mmcdara Yes, the code before the yellow part can run smoothly.

@mmcdara Thanks. I have uploaded the file with errors.

@mmcdara Great. The most important thing is that you told me the objects of DrawGraph can be modified by ourselves. However, in Maple 2023, many errors and warnings are reported. I am not sure if it is due to the version update.

Download Customization_1_2023.mw

@mmcdara I apologize for my negligence, but my concern still has merit. Because the function ShortestPath selects one of shortest paths between two vertices, we need to consider that the following choices may cause problems. I would say that the success of your function depends on luck from ShortestPath.

If  ShortestPath(G,1,10) first selects the shortest path 1-2-7-10, and then removes vertices  "2" and "7", subsequently, we can find at most two vertex-disjoint paths between "1" and "10" (1-4-8-10,1-5-9-10).

I'm not sure if I misunderstood your function, but this situation is indeed concerning.

PS: Interestingly, I haven't found a counterexample yet that makes your function always fail. This implies that any shortest path will break two or more vertex-disjoint paths.