lcz

929 Reputation

11 Badges

4 years, 104 days
changsha, China

MaplePrimes Activity


These are replies submitted by lcz

@Carl Love Indeed, the previous title was too cumbersome. I have simplified it.

@Carl Love Your code is very cool!  Although I can't understand right away why it can find a minimum dominating set (the underlying principles behind it), one method I know of for finding a minimum dominating set (or the domination number) is to convert it into an integer programming problem. 

See page 450 of the  book "Computational Mathematics with SageMath" ( http://dl.lateralis.org/public/sagebook/sagebook-ba6596d.pdf)

 
 

@dharr That's great. I didn't notice there was a similar question before. I still accept the length. However, it would be best to return a shortest closed  spanning walk for checking.  The length you give is exaclty Hamiltonian number.

@vs140580 To be honest, I didn't understand the requirements of your original post, especially, the second one:

  •  ii) An edge in  the list H will occur exactly twice only in the entire list of graphs

I think it's best to ask a question with a small example.

See this link and tomleslie gave a maple solution.

Or use is_subgraph in sagemath (maybe more efficient).

G = graphs.PetersenGraph()
H = Graph({1: [2, 3, 4]})
L = list(G.subgraph_search_iterator(H, induced=False)) 
len(L)

60

@Carl Love @nm We need Load the package pict2e . I asked this question on the LaTeX Stack Exchange, and it was answered by user egreg.

@Carl Love 

The LaTeX codes in Soccer.txt  are generated by Maple. I found that only horizontal or vertical edges are good; all others have this issue.

For example, the following edge is ok

\color[rgb]{0.000,0.000,0.000}\qbezier(130.66,240.67)(150.02,240.69)(169.38,240.70)

 

@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.

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 Kt-free graphs and variantsarXiv 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

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