Opened 6 years ago

Closed 4 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)

faster-isgraded.txt (602 bytes) - added by jmantysalo 4 years ago.

Download all attachments as: .zip

Change History (24)

comment:1 Changed 6 years ago by gmoose05

Thomas McConville? will be implementing this

comment:2 Changed 6 years ago by gmoose05

  • Cc mcco0489@… added

comment:3 Changed 5 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:4 Changed 5 years ago by darij

I've improved the situation in #13240; the algorithm is now polynomial time. Wouldn't hurt to improve it nevertheless.

comment:5 Changed 4 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:6 Changed 4 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:7 Changed 4 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

Changed 4 years ago by jmantysalo

comment:8 Changed 4 years ago by jmantysalo

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 4 years ago by jmantysalo

  • Branch set to u/jmantysalo/implement_poset_is_graded_using_a_polynomial_time__linear___algorithm_

comment:10 Changed 4 years ago by jmantysalo

  • Authors set to Jori Mäntysalo
  • Cc ncohen added
  • Commit set to a9896c7e9f9e8e6c6f52a25a3370c2d595e2fecf
  • Status changed from new to needs_review

I should now be O(n). (Where n if number of cover relations, not number of elements.


New commits:

32a7eb7New algorithm.
a9896c7.

comment:11 Changed 4 years ago by jmantysalo

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 4 years ago by ncohen

  • 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 4 years ago by jmantysalo

  • 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 4 years ago by jmantysalo

A side note about #17002: It makes minimal_elements slightly slower. Must modify functions sinks() and sources() on digraph.py.

comment:15 Changed 4 years ago by ncohen

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 4 years ago by jmantysalo

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: Changed 4 years ago by ncohen

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: Changed 4 years ago by jmantysalo

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 and is_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 4 years ago by ncohen

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 be O(n^2) and my implementation O(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 4 years ago by jmantysalo

  • 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 4 years ago by darij

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 4 years ago by ncohen

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 4 years ago by vbraun

  • Resolution set to wontfix
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.