IncidenceStructure.packing

[nathanncohen]

A Good Old ILP for a NP-Hard problem. Reminds me of the early days of Graphs in Sage :-P

Nathann

Depends on #16701

CC: @videlec @KPanComputes @dimpase @brettpim

Component: combinatorial designs

Author: Nathann Cohen

Branch/Commit: 6edd826

Reviewer: Dima Pasechnik

Issue created by migration from https://trac.sagemath.org/ticket/16709

[nathanncohen]

Branch: u/ncohen/16709

[nathanncohen]

Dependencies: #16701

[sagetrac-git]

Commit: 8b05ae8

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

9c7d82e	trac #16701: IncidenceStructure.degree
5a11312	trac #16701: A fix for a blasphemy
ec241b8	trac #16701: Tribute to pep8 fascism
8b05ae8	trac #16709: IncidenceStructure.packing

[sagetrac-git]

Changed commit from 8b05ae8 to 3a6f43d

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

3a6f43d

trac #16709: IncidenceStructure.packing

[dimpase]

comment:4

LGTM.

By the way, I noticed weirdness in designs.steiner_quadruple_system -- these guys aren't Incidence system, they are just dumps of tuples...

[dimpase]

Reviewer: Dima Pasechnik

[dimpase]

comment:5

PS. one ought to have .covering() too, not only .packing().

[nathanncohen]

comment:6

Yo !

Thanks for the review !

By the way, I noticed weirdness in designs.steiner_quadruple_system -- these guys aren't Incidence system, they are just dumps of tuples...

Well, write a ticket if you care (I will review it), otherwise I'll do it someday. I was against it some time ago, but that was before Vincent's patch to renovate the incidence structure code. It used to be buggy and unmaintained, but now it is on a better road. Let's use it.

Nathann

[nathanncohen]

comment:7

PS. one ought to have .covering() too, not only .packing().

Same here, write a patch if you care (like for packing it only takes 10 lines of LP) otherwise it will be done someday. Though I hit packing problems much more often than covering ones, so it may not be tomorrow :-P

Nathann

[vbraun]

Changed branch from u/ncohen/16709 to 3a6f43d

[vbraun]

comment:9

PDF Docs:

LaTeX Warning: Hyper reference `sage/combinat/designs/incidence_structures:sage
.combinat.designs.incidence_structures.IncidenceStructure.is_t_design' on page 
244 undefined on input line 20504.

[244] [245] [246]
! Double subscript.
l.20746 ...tion, see the ;wikipedia:$Packing_in_a_
                                                  hypergraph$.

[vbraun]

Changed commit from 3a6f43d to none

[nathanncohen]

comment:10

:-/

[nathanncohen]

Commit: 6edd826

[nathanncohen]

New commits:

3a6f43d	trac #16709: IncidenceStructure.packing
354c830	trac #16709: Merged with 6.3.beta8
6edd826	trac #16709: Broken doc

[nathanncohen]

Changed branch from 3a6f43d to u/ncohen/16709

[dimpase]

comment:13

right, ; -> :

[vbraun]

Changed branch from u/ncohen/16709 to 6edd826