Opened 9 years ago
Closed 6 years ago
#13223 closed enhancement (wontfix)
Implement Poset.is_graded using a polynomial time (linear?) algorithm.
Reported by: | nthiery | Owned by: | sage-combinat |
---|---|---|---|
Priority: | minor | Milestone: | sage-duplicate/invalid/wontfix |
Component: | combinatorics | Keywords: | sd40 |
Cc: | sage-combinat, mcco0489@…, ncohen | Merged in: | |
Authors: | Jori Mäntysalo | Reviewers: | |
Report Upstream: | N/A | Work issues: | |
Branch: | u/jmantysalo/implement_poset_is_graded_using_a_polynomial_time__linear___algorithm_ (Commits) | Commit: | a9896c7e9f9e8e6c6f52a25a3370c2d595e2fecf |
Dependencies: | #13222 | Stopgaps: |
Description
Title says it all. See also #13222.
Attachments (1)
Change History (24)
comment:1 Changed 8 years ago by
comment:2 Changed 8 years ago by
- Cc mcco0489@… added
comment:3 Changed 7 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:4 Changed 7 years ago by
I've improved the situation in #13240; the algorithm is now polynomial time. Wouldn't hurt to improve it nevertheless.
comment:5 Changed 7 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:6 Changed 7 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:7 Changed 6 years ago by
- Milestone changed from sage-6.3 to sage-6.4
Changed 6 years ago by
comment:8 Changed 6 years ago by
I attached an example code. Before integrating to Sage it must be changed so that rank list is saved, or should it? For now is_graded()
starts with is_ranked()
, and it saves rank of every element to internal variable.
comment:9 Changed 6 years ago by
- Branch set to u/jmantysalo/implement_poset_is_graded_using_a_polynomial_time__linear___algorithm_
comment:10 Changed 6 years ago by
- Cc ncohen added
- Commit set to a9896c7e9f9e8e6c6f52a25a3370c2d595e2fecf
- Status changed from new to needs_review
comment:11 Changed 6 years ago by
Duh, must to do more timings. This is somewhat faster when going throught Posets(8), but much slower with bigger random posets. Algorithm should probably be selected by number of elements and cover relations.
comment:12 Changed 6 years ago by
- Status changed from needs_review to needs_info
I do not understand. According to Wikipedia, isn't this poset graded by the function which associates to every element the length of its label ?
http://en.wikipedia.org/wiki/Graded_poset
sage: d=DiGraph(); d.add_path(["aaaa","aaa","aa","a"]); d.add_path(["bbb","aa"]) sage: Poset(d).is_graded() False
(same result with or without your branch applied)
Nathann
comment:13 Changed 6 years ago by
- Priority changed from major to minor
- Status changed from needs_info to needs_work
Some sources define graded poset like what Sage define ranked. For that see #16998 and doc for is_graded
on posets.py
.
My code lacked one set()
function. But after that also minimal_elements()
takes more time that I thinked, hence this code is still slower than original in many (most?) cases.
Also, original code is O(n). Hence I dropped this to minor priority.
comment:14 Changed 6 years ago by
A side note about #17002: It makes minimal_elements
slightly slower. Must modify functions sinks()
and sources()
on digraph.py
.
comment:15 Changed 6 years ago by
Oh. I thought that it would go unnoticed.
Well, try replacing the code of sinks/source from
return [x for x in self if self.out_degree(x)==0]
to
return [x for x,d in self.out_degree(labels=True).iteritems() if d==0]
It means less calls to out_degree
. Perhaps that's what you detected ?
Nathann
comment:16 Changed 6 years ago by
I'll try that.
Whole question is irrelevant, but interesting. It should be clear that checking if a poset is graded is faster when doing it "directly" and not throught rank function. Rank should need both in- ja out-edges of underlying graph, direct method just out-edges; and out-edges are just picked up from memory, not searched in any way.
However, many timinigs say against this.
comment:17 follow-up: ↓ 18 Changed 6 years ago by
Hello !
Just looked at the code again, but I do not see what possible improvement you expect. Algorithmically, things are done correctly. Now, if you really need to save some time on this function you can change a couple of lines to avoid creating lists unnecessarily, turn the Python list into a C arrays, things like that. But I think that the Poset code still needs other improvements before this kind of things begin to be the critical costs.
About definitions, though: what is implemented is not equivalent to return all(rf(i) == rank for i in maxes)
, for you need to do the same with mins. This Poset
is not graded according to the definition involving "all maximal chains":
Poset(DiGraph({1:[2],3:[2],4:[3]})).show()
It would be interesting to compare the speed of rank_dict
and is_graded
though, as their code is very similar.
Nathann
comment:18 in reply to: ↑ 17 ; follow-up: ↓ 19 Changed 6 years ago by
Replying to ncohen:
Now, if you really need to save some time on this function you can change a couple of lines to avoid creating lists unnecessarily, turn the Python list into a C arrays, things like that. But I think that the Poset code still needs other improvements before this kind of things begin to be the critical costs.
Yep. Should this one be marked as positive_review and moved to wontfix-milestone?
About definitions, though: what is implemented is not equivalent to
return all(rf(i) == rank for i in maxes)
, for you need to do the same with mins.
True.
It would be interesting to compare the speed of
rank_dict
andis_graded
though, as their code is very similar.
I made a code that was slightly faster when calculating how many of Posets(8)
are graded (assuming that ranks were not already computed). IF "going up" is cheaper than going down, i.e. poset is internally saved as digraph of upper covers, then in principle current implementation would be O(n^2)
and my implementation O(n)
. But in reality this sppedup is not happening.
comment:19 in reply to: ↑ 18 Changed 6 years ago by
Yooooooo !
Yep. Should this one be marked as positive_review and moved to wontfix-milestone?
+1 to that
I made a code that was slightly faster when calculating how many of
Posets(8)
are graded (assuming that ranks were not already computed). IF "going up" is cheaper than going down, i.e. poset is internally saved as digraph of upper covers, then in principle current implementation would beO(n^2)
and my implementationO(n)
. But in reality this sppedup is not happening.
Well, going up or down should be the same cost. The edges are stored twice (in each direction) in digraphs.
Nathann
comment:20 Changed 6 years ago by
- Milestone changed from sage-6.4 to sage-duplicate/invalid/wontfix
- Status changed from needs_work to positive_review
As current algorithm already is O(n)
with small constant factor, and Nathann also suggest closing this, I mark this ticket as dontfix-positive_review.
Todo-note from posets.py
must also be removed. However, I can do that on #16998.
comment:21 Changed 6 years ago by
Sorry for the confusion that came from me. When I said that "Wouldn't hurt to improve it nevertheless", I didn't have any particular improvements in mind, just an impression that I wasn't being very thorough. And I think it wasn't exactly my algorithm that got implemented in Sage, but rather an improved version by Anne(?) and Nicolas(?).
comment:22 Changed 6 years ago by
Okay. Well, for sure I do not know any algorithmic way to compute that which would be better than the current one.
Nathann
comment:23 Changed 6 years ago by
- Resolution set to wontfix
- Status changed from positive_review to closed
Thomas McConville? will be implementing this