Opened 6 years ago

Closed 6 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)

trac_14536.patch (10.0 KB) - added by ncohen 6 years ago.
trac_14536_review1.patch (2.7 KB) - added by chapoton 6 years ago.

Download all attachments as: .zip

Change History (14)

comment:1 Changed 6 years ago by ncohen

  • Dependencies set to #14475
  • Status changed from new to needs_review

I also implemented an iterator over all tournaments with Nauty.

Nathann

comment:2 follow-up: Changed 6 years ago by nthiery

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: Changed 6 years ago by ncohen

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: Changed 6 years ago by nthiery

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: Changed 6 years ago by ncohen

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

Last edited 6 years ago by ncohen (previous) (diff)

comment:6 in reply to: ↑ 5 Changed 6 years ago by nthiery

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

Last edited 6 years ago by ncohen (previous) (diff)

comment:7 Changed 6 years ago by chapoton

  • 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 6 years ago by ncohen

  • Status changed from needs_work to needs_review

Glooooooops. Sorry. I just fixed them :-/

Nathann

Changed 6 years ago by ncohen

Changed 6 years ago by chapoton

comment:9 Changed 6 years ago by chapoton

hello,

here is a review patch. If you are happy with it, you can set a positive review on my behalf.

comment:10 Changed 6 years ago by ncohen

  • 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 6 years ago by jdemeyer

  • Work issues doctest deleted

comment:12 Changed 6 years ago by jdemeyer

  • Merged in set to sage-5.10.rc0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.