Opened 7 years ago

Closed 7 years ago

#18608 closed enhancement (fixed)

Arc method in BalancedIncompleteBlockDesign class

Reported by: q.honore Owned by:
Priority: major Milestone: sage-6.9
Component: combinatorial designs Keywords:
Cc: vdelecroix, ncohen Merged in:
Authors: Quentin Honoré, Vincent Delecroix Reviewers: Nathann Cohen
Report Upstream: N/A Work issues:
Branch: cbc952e (Commits, GitHub, GitLab) Commit: cbc952eed400d1785aa9530351b7db06b3232e29
Dependencies: Stopgaps:

Status badges

Change History (25)

comment:1 Changed 7 years ago by q.honore

  • Branch changed from u/q.honore/bibd to public/18608

comment:2 Changed 7 years ago by git

  • Commit set to 8e29523f838e964a3ba618d3644bc74a1cb7db80

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

b358e2bAdd methods arc and blocking_set in BIBD class
8e29523Corrected small errors in documentation

comment:3 Changed 7 years ago by q.honore

  • Status changed from new to needs_review

comment:4 Changed 7 years ago by ncohen

Helloooooo ! Isn't 'blocking set' equivalent to 2-coloring of hypergraphs (see #17542)?

Nathann

comment:5 Changed 7 years ago by q.honore

Yes, you're right, it's exactly the same. Arc may be useful though Quentin

comment:6 Changed 7 years ago by vdelecroix

Hello,

For arcs, there is a more general notion that will not cost a lot to implement:

A (s,n)-arc is a set of n points so that in each block there are at most s of them. The case of s=1 corresponds to independent set in graph. The case of s=2 corresponds to the current definition you used.

Given a (v,b,r,k)-bibd (with lambda=1) it is easy to show that the cardinality n of an (s,n)-arc satisfies

n <= 1 + (r-1)(s-1)

The arcs for which the above is an equality are called maximal arcs.

Vincent

comment:7 Changed 7 years ago by git

  • Commit changed from 8e29523f838e964a3ba618d3644bc74a1cb7db80 to 98ed48986340835ee616dbe7c30ee191bee41a35

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

6f95063Deleted blocking set method, arc method is now for (s,n)-arc
bf69936Merge branch 'public/18608' of trac.sagemath.org:sage into develop
98ed489Merge branch 'develop' into HEAD

comment:8 Changed 7 years ago by git

  • Commit changed from 98ed48986340835ee616dbe7c30ee191bee41a35 to a76436a4bb79e315938816cce5798f0c8099cc03

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

a76436aDescription changed

comment:9 Changed 7 years ago by q.honore

  • Description modified (diff)
  • Summary changed from Arc and blocking_set methods in BalancedIncompleteBlockDesign class to Arc method in BalancedIncompleteBlockDesign class

comment:10 Changed 7 years ago by vdelecroix

  • Reviewers set to Vincent Delecroix
  • Status changed from needs_review to needs_work

Hello,

Sometimes you use one back quote as `(s,n)` and sometimes two as ``s``. As you can see, the rendering is quite different in the documentation. The single backquote is used for LaTeX code while the double is used to mention the parameters of the algorithm. Try to not mix them in the same line.

It is dangerous to return self._points directly as it might be modified by the users. Return rather a copy of it using return self._points[:].

The rest looks good.

Vincent

comment:11 Changed 7 years ago by ncohen

Would it be possible to replace 'highest cardinality' with 'maximum cardinality'? Also, would it be possible to replace 'number' with 'maximum number' in the definition of 's'?

Thanks,

Nathann

comment:12 Changed 7 years ago by git

  • Commit changed from a76436a4bb79e315938816cce5798f0c8099cc03 to 831f346f13f8bd439850cec8ddcf912147a75d19

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

831f346Work on description

comment:13 Changed 7 years ago by q.honore

  • Status changed from needs_work to needs_review

comment:14 Changed 7 years ago by git

  • Commit changed from 831f346f13f8bd439850cec8ddcf912147a75d19 to a6d38932e82777967163fb725f58a0255c077c59

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

03a7295Add methods arc and blocking_set in BIBD class
9c198b2Corrected small errors in documentation
73cc907Deleted blocking set method, arc method is now for (s,n)-arc
31eeaedDescription changed
b38469fWork on description
a6d3893Trac #18608: more doc

comment:15 Changed 7 years ago by vdelecroix

  • Milestone changed from sage-6.8 to sage-6.9

Hello,

I rebased above the latest beta and updated the doc. Nathann could you have a look?

Vincent

comment:16 Changed 7 years ago by ncohen

sage: b=designs.balanced_incomplete_block_design(7,3)
sage: len(b.arc())
4
sage: b.relabel(list("abcdefg"))
sage: len(b.arc())
7

comment:17 Changed 7 years ago by git

  • Commit changed from a6d38932e82777967163fb725f58a0255c077c59 to 25ab24491d3cbbab10cb8dbbb95ed3a58d97f171

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

25ab244Trac #18608: fix labelings

comment:18 Changed 7 years ago by git

  • Commit changed from 25ab24491d3cbbab10cb8dbbb95ed3a58d97f171 to e570d949c8e428ec6cb7c099600bf43f66cf7fe9

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

e570d94Trac #18608: add a doctest

comment:19 Changed 7 years ago by vdelecroix

Sorry for that...

comment:20 Changed 7 years ago by ncohen

sage: b = designs.balanced_incomplete_block_design(7,3)
sage: b.relabel(list("abcdefg"))
sage: b.ground_set()
['a', 'b', 'c', 'd', 'e', 'f', 'g']
sage: b.arc()
[0, 1, 2, 5]

comment:21 Changed 7 years ago by git

  • Commit changed from e570d949c8e428ec6cb7c099600bf43f66cf7fe9 to 9ed9d8e2f624e3b642fb19d02ce527f0250c13c2

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

9ed9d8eTrac #18608: fix labelings again

comment:22 Changed 7 years ago by ncohen

Four doctests broke on my machine, since I use a different LP solver. I flagged the dangerous ones with "random" and turned the final test into a boolean one.

I added the commit to that branch since you made it public, and you can change the ticket's status if you agree with it.

Nathann

comment:23 Changed 7 years ago by git

  • Commit changed from 9ed9d8e2f624e3b642fb19d02ce527f0250c13c2 to cbc952eed400d1785aa9530351b7db06b3232e29

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

cbc952etrac #18608: Reviewer's commit

comment:24 Changed 7 years ago by vdelecroix

  • Authors changed from Quentin Honoré to Quentin Honoré, Vincent Delecroix
  • Reviewers changed from Vincent Delecroix to Nathann Cohen
  • Status changed from needs_review to positive_review

Thanks Nathann!

comment:25 Changed 7 years ago by vbraun

  • Branch changed from public/18608 to cbc952eed400d1785aa9530351b7db06b3232e29
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.