Opened 9 years ago

Closed 9 years ago

#15769 closed defect (fixed)

SetSystem._isomorphism fails on an empty Setsystem

Reported by: Rudi Pendavingh Owned by:
Priority: major Milestone: sage-6.2
Component: matroid theory Keywords:
Cc: Stefan, Michael Welsh Merged in:
Authors: Rudi Pendavingh Reviewers: Nathann Cohen
Report Upstream: N/A Work issues:
Branch: public/15769 (Commits, GitHub, GitLab) Commit: 1bc84e87328477994b0d26afe77cddb20f4dc5ab
Dependencies: Stopgaps:

Status badges

Description

The following produces an error:

from sage.matroids.set_system import SetSystem
S=SetSystem([],[])
S._isomorphism(S)

_equivalence() has a similar problem.

Change History (9)

comment:1 Changed 9 years ago by Nathann Cohen

SetSystem? ?... Guys, there is a Hypergraph class in Sage. Perhaps we should do something ?

comment:2 in reply to:  1 ; Changed 9 years ago by Rudi Pendavingh

Replying to ncohen:

SetSystem? ?... Guys, there is a Hypergraph class in Sage. Perhaps we should do something ?

Hi Nathan, the SetSystem? is just an internal datastucture. The end user only has access to them as an iterator over a set of sets, and we reserve the right to replace them with something that does the same job better or faster. But while we have them, they better not fail when they are empty :) Internally, we do use them to test for matroid isomorphism.

Of course it's easy enough to turn these SetSystems? into Hypergraphs, since they behave as iterators.

M=matroids.named_matroids.NonFano()
H=Hypergraph(M.bases())

BTW there seems to be no way to get vertices that are not in some hyperedge into a Hypergraph.

comment:3 in reply to:  2 ; Changed 9 years ago by Nathann Cohen

Yooooo !!!

Hi Nathan, the SetSystem? is just an internal datastucture. The end user only has access to them as an iterator over a set of sets, and we reserve the right to replace them with something that does the same job better or faster. But while we have them, they better not fail when they are empty :) Internally, we do use them to test for matroid isomorphism.

Makes sense !

Of course it's easy enough to turn these SetSystems? into Hypergraphs, since they behave as iterators.

M=matroids.named_matroids.NonFano()
H=Hypergraph(M.bases())

BTW there seems to be no way to get vertices that are not in some hyperedge into a Hypergraph.

Well right now hypergraphs do absokutely nothing smart. Some coloring, and some plot with view(). But if some of us want to work on them it would be better to do the job only once ! I only wrote this because I needed it, but some isomorphism check would be nice indeed. Plus basic things like enumerating the vertices, as you say. I am working on some design patches as the same time, which do not return hypergraphs but list of lists... I am not very set on what this class should do, to be honest :-)

Nathann

comment:4 in reply to:  3 Changed 9 years ago by Rudi Pendavingh

Well right now hypergraphs do absokutely nothing smart. Some coloring, and some plot with view(). But if some of us want to work on them it would be better to do the job only once ! I only wrote this because I needed it, but some isomorphism check would be nice indeed. Plus basic things like enumerating the vertices, as you say. I am working on some design patches as the same time, which do not return hypergraphs but list of lists... I am not very set on what this class should do, to be honest :-)

You could use SetSystem? as a back-end to Hypergraph. SetSystem? is hardly more than an array of bitsets, so it is good at storing many subsets of a relatively small set (internally the subsets are represented as bitsets). It would not be memory-efficient as a way to store small subsets of a big groundset --- in that case, class Hypergraph better choose another way to store its stuff.

Currently, the isomorphism test of SetSystem? is my own partial implementation of the partition-refinement algorithm of McKay?, just some 300 lines of code. Until I complete that implementation, my code will not be able to compute the automorphism group. Nauty and other complete implementations can do that. I am not sure whether I should finish my implementation or learn my code to call other parts of Sage for this. It depends on how directly I can call such code from my own. I care a lot about efficiency, so I want to avoid unnecessary translation steps where possible. Another ticket, I guess.

comment:5 Changed 9 years ago by Rudi Pendavingh

Branch: u/Rudi/ticket/15769
Created: Jan 30, 2014, 10:22:03 PMJan 30, 2014, 10:22:03 PM
Modified: Feb 1, 2014, 10:12:42 AMFeb 1, 2014, 10:12:42 AM

comment:6 Changed 9 years ago by Rudi Pendavingh

Commit: 769e4533706b305b24ad23a52080e4599ed8b2e5
Status: newneeds_review

This should do it.


New commits:

769e453Fixed SetSystem._isomorphism(S,T) where S is an empty isopmorphism.

comment:7 Changed 9 years ago by Nathann Cohen

Authors: Rudi Pendavingh
Branch: u/Rudi/ticket/15769public/15769
Commit: 769e4533706b305b24ad23a52080e4599ed8b2e51bc84e87328477994b0d26afe77cddb20f4dc5ab
Reviewers: Nathann Cohen

If you agree with this small modification (and merge) you can set the ticket to positive_review.

Nathann


New commits:

10dee0etrac #15769: Rebase on 6.2.beta0
1bc84e8trac #15769: replace "if len(L) > 0:" with "if L:"

comment:8 Changed 9 years ago by Rudi Pendavingh

Status: needs_reviewpositive_review

Looks fine, thanks Nathann!

comment:9 Changed 9 years ago by Volker Braun

Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.