Implement Poset.is_graded using a polynomial time (linear?) algorithm.

[nthiery]

Title says it all. See also #13222.

[gmoose05]

Thomas McConville? will be implementing this

[darij]

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

[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.

[jmantysalo]

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

---

New commits:

​32a7eb7	New algorithm.
​a9896c7	.

[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.

[ncohen]

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

[jmantysalo]

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.

[jmantysalo]

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

[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

[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.

[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

[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.

[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

[jmantysalo]

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.

[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(?).

[ncohen]

Okay. Well, for sure I do not know any algorithmic way to compute that which would be better than the current one.

Nathann