Opened 4 years ago

Closed 4 years ago

#18830 closed enhancement (fixed)

implement Lovasz theta-function for graphs

Reported by: dimpase Owned by:
Priority: major Milestone: sage-6.8
Component: graph theory Keywords:
Cc: ncohen Merged in:
Authors: Dima Pasechnik Reviewers: Nathann Cohen
Report Upstream: N/A Work issues:
Branch: f635efb (Commits) Commit: f635efb9956bed4fa8cab78138f433a9063da637
Dependencies: #18827 Stopgaps:

Description

Use a dedicated SDP solver from csdp for this problem to compute the well-known Lovasz theta-function for graphs.

Change History (13)

comment:1 Changed 4 years ago by dimpase

  • Branch set to u/dimpase/18830
  • Commit set to a26dd1e94811fd5801e3693d3dbb4e64f5ba164e

New commits:

83676aaimplementation using csdp's dedicated theta solver
77257e3remaning, docs, etc
a26dd1eadd to docs, and a bit of cleaning

comment:2 Changed 4 years ago by dimpase

  • Cc ncohen added
  • Dependencies set to #18827
  • Status changed from new to needs_review

comment:3 Changed 4 years ago by ncohen

  • Reviewers set to Nathann Cohen
  • Status changed from needs_review to needs_work

Helloooooo Dima,

There is a LovaZS at the head of your new module. Also, could you check that csdp is installed with a 'is_package_installed("csdp")' and raise a meaningful exception otherwise?

Could you also provide a couple of sentences to explain, in the documentation of lovasz_theta, what exactly this function is? This will become a method of Graph and well, we usually give those kind of explanations there. Depending on how verbose you feel, it can be just a link toward the relevant wikipedia page :wikipedia:`Lovász_number`.

Thaaaaaanks,

Nathann

comment:4 Changed 4 years ago by git

  • Commit changed from a26dd1e94811fd5801e3693d3dbb4e64f5ba164e to 68e6fc8ceb2187d3f642cbdbaa34a4766b4af18a

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

68e6fc8typos fixed

comment:5 Changed 4 years ago by git

  • Commit changed from 68e6fc8ceb2187d3f642cbdbaa34a4766b4af18a to 621f3426a4b5e828484ffabb0e780a08262e0ed0

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

b341213added more info on theta and a check that csdp is installed
621f342more typos fixed

comment:6 Changed 4 years ago by dimpase

  • Status changed from needs_work to needs_review

all done!

comment:7 follow-up: Changed 4 years ago by ncohen

Hellooooo Dima!

I added a small commit at #18830, that mostly does text reformatting. Some accents, a shorter name for the module, a different import, making the first sentence of a docstring a one-line one, things like that.

If you agree with this, you can set this ticket to positive_review. Meanwhile, I'll be walking toward the lab :-D

Nathann

comment:8 in reply to: ↑ 7 Changed 4 years ago by dimpase

Replying to ncohen:

Hellooooo Dima!

I added a small commit at #18830, that mostly does text reformatting. Some accents, a shorter name for the module, a different import, making the first sentence of a docstring a one-line one, things like that.

sure, but where is your commit? See you soon, Dima

If you agree with this, you can set this ticket to positive_review. Meanwhile, I'll be walking toward the lab :-D

Nathann

comment:9 Changed 4 years ago by ncohen

Argggggg... I meant at public/18830. Sorry.

comment:10 Changed 4 years ago by dimpase

  • Branch changed from u/dimpase/18830 to public/18830
  • Commit changed from 621f3426a4b5e828484ffabb0e780a08262e0ed0 to f635efb9956bed4fa8cab78138f433a9063da637
  • Status changed from needs_review to positive_review

comment:11 Changed 4 years ago by vbraun

  • Status changed from positive_review to needs_work

Author name

comment:12 Changed 4 years ago by dimpase

  • Authors set to Dima Pasechnik
  • Status changed from needs_work to positive_review

comment:13 Changed 4 years ago by vbraun

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