Opened 8 years ago
Closed 8 years ago
#14536 closed enhancement (fixed)
Random tournaments, a misnamed method and a segfault
Reported by: | ncohen | Owned by: | jason, ncohen, rlm |
---|---|---|---|
Priority: | major | Milestone: | sage-5.10 |
Component: | graph theory | Keywords: | digraph, tournament |
Cc: | Merged in: | sage-5.10.rc0 | |
Authors: | Nathann Cohen | Reviewers: | Frédéric Chapoton |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #14475 | Stopgaps: |
Description
digraphs.Tournament
use to return a transitive tournament. I have no idea why I named it "tournament", as there is a wealth of tournaments on n
vertices. Hence I rename it in this patch. I think that it does not need to be deprecated first, because the former name really is ill-adapted, and because the patch that added it was merged three months ago only. Let's not keep this bad name for another year.
The segfault is rather shameful... :-P
sage: Graph(-1) ------------------------------------------------------------------------ /home/ncohen/.Sage/sage: line 135: 5163 Segmentation fault "$SAGE_ROOT/spkg/bin/sage" "$@"
Attachments (2)
Change History (14)
comment:1 Changed 8 years ago by
- Dependencies set to #14475
- Status changed from new to needs_review
comment:2 follow-up: ↓ 3 Changed 8 years ago by
Yo,
I just had a look, and it sounds very reasonnable.
Three details:
- Why not displaying anymore the number of vertices in the name method of TransitiveTournament?? Since other graphs do the same that would be consistent.
- A potential alternative name would be "chain"
- In the tournament generator using Nauty, once the nauty command is constructed, it seems that all the rest is generic (calling Nauty, parsing the output, building and yielding the graphs). What about extracting this into a generic function?
In the long run, it would be nice to have a uniform interface for generating graphs using either Sage's engine or nauty (say with an algo=nauty/Sage optional switch, which would default to Sage, unless nauty become a standard package some day.).
Cheers,
Nicolas
comment:3 in reply to: ↑ 2 ; follow-up: ↓ 4 Changed 8 years ago by
Hellooooooo !!
- Why not displaying anymore the number of vertices in the name method of TransitiveTournament?? Since other graphs do the same that would be consistent.
Well. This is the result with the patch as it is :
sage: digraphs.TransitiveTournament(5) Transitive Tournament: Digraph on 5 vertices
If the number of vertices is included in the name, you get "Transitive Tournament on 5 vertices: Digraph on 5 vertices".
- A potential alternative name would be "chain"
For what ? Transitive tournament ? O_o
Hey, it's not a Poset ! It's a digraph ! :-P
Plus it would really make people think of this :
sage: digraphs.Path(5) Path on 5 vertices: Digraph on 5 vertices
Oh, by the way the name contains the number of vertices in this case. What do you think ?
- In the tournament generator using Nauty, once the nauty command is constructed, it seems that all the rest is generic (calling Nauty, parsing the output, building and yielding the graphs). What about extracting this into a generic function?
HMmmmmm. Most of it is, yes. Building the string that Nauty received as input is not, and parsing the graph is not either.. Usually Nauty returns a sparse6_string but Sage does not understand sparse6 string for digraphs yet. And there was a small difference in #14474 too.
Well, you are right a large part of it could be made automatic. It would also be the occasion to create a Nauty module, and so a documentation page about the Nauty spkg (how it is to be installed, which Demigod first wrote it.
Let's say another patch ? We still do not have the interface from Sage to Nauty's digraph generation. It's not that bad because we have Robert Miller's version in Sage, but I will probably do it someday. So I'll do both then :-)
In the long run, it would be nice to have a uniform interface for generating graphs using either Sage's engine or nauty (say with an algo=nauty/Sage optional switch, which would default to Sage, unless nauty become a standard package some
Nauty is not a part of Sage because of license problems... And it knows how to enumerate things that are not implemented in Sage yet (like hypergraphs :-PPP
).
It goes in both directions, though. It is easy to enumerate through Sage the list of graphs satisfying some specific property, and the property is actually tested *during* the enumeration. No way to do this with Nauty, unless we *REALLY* rewrite the interface and call Nauty's C functions directly :-P
Nathann
comment:4 in reply to: ↑ 3 ; follow-up: ↓ 5 Changed 8 years ago by
Replying to ncohen:
If the number of vertices is included in the name, you get "Transitive Tournament on 5 vertices: Digraph on 5 vertices".
I see. It would be consistent to fix Circuit then:
sage: digraphs.Circuit(5) Circuit on 5 vertices: Digraph on 5 vertices
But that can be for later.
Hey, it's not a Poset ! It's a digraph !
Fair enough :-)
Well, you are right a large part of it could be made automatic. It would also be the occasion to create a Nauty module, and so a documentation page about the Nauty spkg (how it is to be installed, which Demigod first wrote it.
Let's say another patch ?
Yup.
Nauty is not a part of Sage because of license problems...
I know. Maybe we should chat to Brendan about this someday.
And it knows how to enumerate things that are not implemented in Sage yet (like hypergraphs
:-PPP
).It goes in both directions, though. It is easy to enumerate through Sage the list of graphs satisfying some specific property, and the property is actually tested *during* the enumeration. No way to do this with Nauty, unless we *REALLY* rewrite the interface and call Nauty's C functions directly
:-P
Yup. Still it would be nice if there was a single entry point for both generators, even if some features only work in one case.
Cheers,
Nicolas
comment:5 in reply to: ↑ 4 ; follow-up: ↓ 6 Changed 8 years ago by
Yoooooooooo !
I see. It would be consistent to fix Circuit then:
Done !
Nauty is not a part of Sage because of license problems...
I know. Maybe we should chat to Brendan about this someday.
Brendan McKay? is like MY own personnal Chuck Nurris. He is right. But perhaps he can decide that licensing his software under the GPL would be even greater. We would not convince him to do that, of course, but he could decide it by himself. And this would not be related in any way with our emails. Of course.
Yup. Still it would be nice if there was a single entry point for both generators, even if some features only work in one case.
Yepyep. Will do !
Nathann
comment:6 in reply to: ↑ 5 Changed 8 years ago by
Replying to ncohen:
Brendan McKay? is like MY own personnal Chuck Nurris. He is right.
+1
But perhaps he can decide that licensing his software under the GPL would be even greater. We would not convince him to do that, of course, but he could decide it by himself. And this would not be related in any way with our emails.
He chose the license for Nauty a while ago. In the mean time the world of software as evolved quite some. It can be useful to him to have feedback on what can be helpful to us and to the math open source community at large nowadays. And then he can take whatever informed decision he wants. He is the author anyway.
Cheers,
Nicolas
comment:7 Changed 8 years ago by
- Keywords digraph tournament added
- Status changed from needs_review to needs_work
- Work issues set to doctest
3 failing doctests need to be corrected
comment:8 Changed 8 years ago by
- Status changed from needs_work to needs_review
Glooooooops. Sorry. I just fixed them :-/
Nathann
Changed 8 years ago by
Changed 8 years ago by
comment:9 Changed 8 years ago by
hello,
here is a review patch. If you are happy with it, you can set a positive review on my behalf.
comment:10 Changed 8 years ago by
- Reviewers set to Frédéric Chapoton
- Status changed from needs_review to positive_review
Ahh..... Old PEP8 :-P
Thank you for this patch and the review :-)
Nathann
comment:11 Changed 8 years ago by
- Work issues doctest deleted
comment:12 Changed 8 years ago by
- Merged in set to sage-5.10.rc0
- Resolution set to fixed
- Status changed from positive_review to closed
I also implemented an iterator over all tournaments with Nauty.
Nathann