Opened 5 years ago
Closed 4 years ago
#17540 closed enhancement (fixed)
Poset.dimension
Reported by: | ncohen | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-6.7 |
Component: | combinatorics | Keywords: | |
Cc: | mmarco, dimpase, vdelecroix, tmonteil, jmantysalo | Merged in: | |
Authors: | Nathann Cohen | Reviewers: | Dima Pasechnik |
Report Upstream: | N/A | Work issues: | |
Branch: | ffe181b (Commits) | Commit: | ffe181b536ce832a68620f1c7063807315d370a6 |
Dependencies: | Stopgaps: |
Description (last modified by )
With this code, Sage at last can compute the dimension of a Poset.
http://en.wikipedia.org/wiki/Order_dimension
Nathann
See https://groups.google.com/d/topic/sage-devel/qEE9YUAPA4g/discussion
Change History (42)
comment:1 Changed 5 years ago by
- Branch set to u/ncohen/17540
- Status changed from new to needs_review
comment:2 Changed 5 years ago by
- Commit set to 216d59efca2e03ebce6e9fd76f150abb32e369d5
comment:3 Changed 5 years ago by
- Description modified (diff)
comment:4 follow-up: ↓ 5 Changed 5 years ago by
Is the ticket description wrong? I can't review code that is not supposed to work :-)
comment:5 in reply to: ↑ 4 ; follow-up: ↓ 6 Changed 5 years ago by
Is the ticket description wrong? I can't review code that is not supposed to work :-)
Don't get it. You talk about the missing () to dimension ?
comment:6 in reply to: ↑ 5 Changed 5 years ago by
Replying to ncohen:
Is the ticket description wrong? I can't review code that is not supposed to work :-)
Don't get it. You talk about the missing () to dimension ?
With this code, Sage can compute the dimension of a Poset. http://en.wikipedia.org/wiki/Order_dimension Turns out that we were not able to.
we are not able to
comment:7 Changed 5 years ago by
- Description modified (diff)
I am glad to see this very confusing typo corrected. Thank you for bringing it to my attention.
comment:8 follow-up: ↓ 9 Changed 5 years ago by
- Description modified (diff)
IMHO there should be a separate function to compute the chromatic number of a hypergraph.
comment:9 in reply to: ↑ 8 ; follow-ups: ↓ 10 ↓ 11 Changed 5 years ago by
IMHO there should be a separate function to compute the chromatic number of a hypergraph.
It is true, but we could not call it from here. The reason why this code is so long is that we avoid building the LP from the start every time we need to add a constraint. It is only re-built when we notice that the new hypergraph is not k-colorable anymore.
Nathann
P.S. : Actually I will write a LP for that. I will surely need it some day.
comment:10 in reply to: ↑ 9 Changed 5 years ago by
comment:11 in reply to: ↑ 9 ; follow-up: ↓ 12 Changed 5 years ago by
Replying to ncohen:
IMHO there should be a separate function to compute the chromatic number of a hypergraph.
It is true, but we could not call it from here. The reason why this code is so long is that we avoid building the LP from the start every time we need to add a constraint. It is only re-built when we notice that the new hypergraph is not k-colorable anymore.
Hmm, why do you need to rebuild the hypergraph? The latter is fixed. What is not fixed is the number of colours you need, and you don't want to rebuild the ILP from scratch for this. Why is this poset-specific?
comment:12 in reply to: ↑ 11 Changed 5 years ago by
Hmm, why do you need to rebuild the hypergraph? The latter is fixed. What is not fixed is the number of colours you need, and you don't want to rebuild the ILP from scratch for this. Why is this poset-specific?
On the paper, the hypergraph is very well defined and you have to compute its chromatic number. In practice, you cannot build the hypergraph because the list of its edges is too huge (I would not know how to do that anyway). So what we do is start with *some* of the edges in the hypergraph, and find a coloring.
When we have a coloring, we can check that it is valid by building the corresponding graphs --> if all are acyclic that's fine and we are done.
If one is not acyclic, however, we have found a cycle --> a new set to add to our hypergraph. And so we re-color this thing again.
This being said, when you find a new set in your hypergraph, you only have to add one constraint and then you can call .solve
again. If we called .coloring()
each time, we would in fact be building a new LP and solve it from scratch every time we add a constraint, and that's a waste of computations that this branch avoids.
Nathann
comment:13 follow-up: ↓ 15 Changed 5 years ago by
according to [FT00], instead of the hypergraph on inc(P)
, it suffices to restrict to the induced subhypergraph of the critical incomparable pairs (see Lemma 3.3 in [loc.cit.]), and then do the same chromatic number computation.
comment:14 follow-up: ↓ 16 Changed 5 years ago by
Concerning the certificate
, it looks like a half-certificate ; is the algorithm able to provide an evidence that no smaller set of linear ordering can generate the poset by intersection ?
Also, the "just to be sure" section at the end of the code should be run only if some check
option is set to True
since the algorithm is supposed to work without this ?
By the way, in the INPUT
section, it seems more common to write ``certificate`` - boolean (default: ``False``)
than to write the default at the end of the description (i first thought the information was missing).
comment:15 in reply to: ↑ 13 ; follow-up: ↓ 19 Changed 5 years ago by
according to [FT00], instead of the hypergraph on
inc(P)
, it suffices to restrict to the induced subhypergraph of the critical incomparable pairs (see Lemma 3.3 in [loc.cit.]), and then do the same chromatic number computation.
I do not see how that would change anything. You are just telling me that only a subset of points of the hypergraph matters, but that does not give me the set of edges that only involve critical pairs.
Nathann
comment:16 in reply to: ↑ 14 ; follow-up: ↓ 17 Changed 5 years ago by
Concerning the
certificate
, it looks like a half-certificate ; is the algorithm able to provide an evidence that no smaller set of linear ordering can generate the poset by intersection ?
No it cannot. The problem is NP, so there is a certificate for a 'yes' answer, but it is not co-NP so there is no certificate for the other side. (Insert 'polynomial' wherever it fits in the sentence, and assume P!=NP)
Also, the "just to be sure" section at the end of the code should be run only if some
check
option is set toTrue
since the algorithm is supposed to work without this ?
I do not think that it should, considering the running time of the algorithm. That's almost for free comparatively, so I don't see the need to make it optional.
By the way, in the
INPUT
section, it seems more common to write``certificate`` - boolean (default: ``False``)
than to write the default at the end of the description (i first thought the information was missing).
Well I usually write it the way it is written. If you want to change it you are welcome to add a commit, but if it is just about enforcing the coding style you like I will not code it for you :-P
Nathann
comment:17 in reply to: ↑ 16 ; follow-up: ↓ 20 Changed 5 years ago by
Replying to ncohen:
By the way, in the
INPUT
section, it seems more common to write``certificate`` - boolean (default: ``False``)
than to write the default at the end of the description (i first thought the information was missing).Well I usually write it the way it is written. If you want to change it you are welcome to add a commit, but if it is just about enforcing the coding style you like I will not code it for you
:-P
This is not the coding style i like, it is about coding conventions, a feature that allow various people to collectively work on some source code, see http://sagemath.org/doc/developer/coding_basics.html#documentation-strings
comment:18 follow-up: ↓ 21 Changed 5 years ago by
There seems to be no check for argument, i.e. certificate='cat-says-meow'
does not raise an error. Should it?
One-line explanation on TOC should end with dot.
Does this work with empty poset? Checking just now, but compiling is slooow with this machine.
comment:19 in reply to: ↑ 15 ; follow-up: ↓ 23 Changed 5 years ago by
Replying to ncohen:
according to [FT00], instead of the hypergraph on
inc(P)
, it suffices to restrict to the induced subhypergraph of the critical incomparable pairs (see Lemma 3.3 in [loc.cit.]), and then do the same chromatic number computation.I do not see how that would change anything. You are just telling me that only a subset of points of the hypergraph matters, but that does not give me the set of edges that only involve critical pairs.
It seems that you get a smaller ILP; you run your acyclicity test and compute cycles just as you do, but only leave critical pairs there (i.e. you take the subhypergraph induced on the critical pairs --- the edges get intersected with the subset of critical pairs).
comment:20 in reply to: ↑ 17 Changed 5 years ago by
This is not the coding style i like, it is about coding conventions, a feature that allow various people to collectively work on some source code, see http://sagemath.org/doc/developer/coding_basics.html#documentation-strings
If the fact that I wrote the defaut value at the end of the sentence instead of the beginning is a problem for you, add a commit. You will find many other such instances in the same document.
Nathann
comment:21 in reply to: ↑ 18 Changed 5 years ago by
There seems to be no check for argument, i.e.
certificate='cat-says-meow'
does not raise an error. Should it?
I do not think that there should, especially when the argument is boolean (not even a string) and when it does not produce any bug whatever happens. Chekking this kind of stuff is useful when a string is expected, but really if we begin to check every single arguments of every function like that, then half of the python code we have in Sage will be checking the type of input because Python does not do it instead.
One-line explanation on TOC should end with dot.
Done
Does this work with empty poset? Checking just now, but compiling is slooow with this machine.
Done (Jori: we have a 4h30 difference in our timezones)
Nathann
comment:22 Changed 5 years ago by
- Commit changed from 216d59efca2e03ebce6e9fd76f150abb32e369d5 to 59f0435008dccc2f06d46c2b1293258c694487fa
comment:23 in reply to: ↑ 19 Changed 5 years ago by
It seems that you get a smaller ILP; you run your acyclicity test and compute cycles just as you do, but only leave critical pairs there (i.e. you take the subhypergraph induced on the critical pairs --- the edges get intersected with the subset of critical pairs).
I see. Well, I am not very eager to dig into that in order to see how I could list all those critical pairs, then add this to this already non-trivial code, given that I am not very convinced that it will make any difference in the runtimes :-P
Nathann
comment:24 Changed 4 years ago by
Ping ?...
comment:25 Changed 4 years ago by
Piiiiing ?...
comment:26 Changed 4 years ago by
Piiiiiiiiiiiiiiiiiing ?...
comment:27 Changed 4 years ago by
OK, OK, just a bit of patience...
comment:28 Changed 4 years ago by
what is your default LP solver (on which that was tested)? For me
sage: G = graphs.CompleteBipartiteGraph(3,3) sage: P = Poset(DiGraph({(u,v):[u,v] for u,v,_ in G.edges()})) sage: P.dimension()
runs, and runs, and runs (that's with GLPK).
comment:29 Changed 4 years ago by
sigh... That's CPLEX :-/
comment:30 Changed 4 years ago by
With GLPK for G=K_{2,3}
it returns 3 in 2.5s
sage: %time P.dimension() CPU times: user 2.58 s, sys: 4 ms, total: 2.59 s Wall time: 2.58 s 3
With CPLEX it takes 252ms. And for G=K_{3,3}
it returns 4 in 6s.
Nathann
comment:31 follow-up: ↓ 32 Changed 4 years ago by
for G=K33 and with GLPK your code seems to be looping forever. In the code you call init_LP
in the loop, rather than doing a warm restart. This seems to defeat the purpose of constraint generation.
PS. OK, I see, you increase k every time it goes up. Anyhow, one gets stuck on some LP at k=3 here...
comment:32 in reply to: ↑ 31 Changed 4 years ago by
PS. OK, I see, you increase k every time it goes up.
Indeed.
Anyhow, one gets stuck on some LP at k=3 here...
Well, it depends on the graph. And of course it depends on the solver :-P
comment:33 Changed 4 years ago by
OK, tried this with GUROBI, it did work for K33. Trying for Petersen graph now :-)
typo:
+ # We check that all color class induce an acyclic graph, and add a + # constraint otherwise.
do you mean classes
?
comment:34 Changed 4 years ago by
Yes. Tell me when you are done with the review and I will fix everything at once.
comment:35 Changed 4 years ago by
I also notice that there is no objective function in LP. Sometimes specifying some more or less random non-symmetric function helps to speed things up.
comment:36 Changed 4 years ago by
OK, fix that typo, and I'll set it to positive review, even though the code is very slow...
comment:37 Changed 4 years ago by
The Wikipedia article you refer says that this is sometimes also called "Dushnik–Miller dimension". Is this common name for dimension? If so, it should be mentioned somewhere, so that user googling "Dushnik–Miller sagemath" will found this.
comment:38 Changed 4 years ago by
- Commit changed from 59f0435008dccc2f06d46c2b1293258c694487fa to ffe181b536ce832a68620f1c7063807315d370a6
comment:39 Changed 4 years ago by
Here it is!
Nathann
comment:40 Changed 4 years ago by
- Milestone changed from sage-6.5 to sage-6.7
- Reviewers set to Dima Pasechnik
- Status changed from needs_review to positive_review
comment:41 Changed 4 years ago by
Thaaaaaaaaaaaaaanks ! ;-)
Nathann
comment:42 Changed 4 years ago by
- Branch changed from u/ncohen/17540 to ffe181b536ce832a68620f1c7063807315d370a6
- Resolution set to fixed
- Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
trac #17540: Poset.dimension()