PartialOrderOfDClasses inconsistent output
The documentation says that the partial order of Dclasses can be obtained by the transitive closure of the output relations. However, it seems that the reflexive closure is also need. For manual example
gap> S:=Semigroup( Transformation( [ 2, 4, 1, 2 ] ), > Transformation( [ 3, 3, 4, 1 ] ) );; gap> PartialOrderOfDClasses(S); [ [ 3 ], [ 2, 3 ], [ 3, 4 ], [ 4 ] ]
(1,1) is missing, while the (3,3) explicitly appears in the output. This also contradicts the documentation saying that only the immediately below relations are returned, hinting that basically the Hasse diagram of the partial order is meant to be returned. From random examples it seems that PartialOrderOfDClasses misses some maximal elements.
So it is not clear what is returned exactly.
Comments (11)


I see, and the documentation fix would solve the issue.
However, I was trying to use PartialOrderOfDClasses as a possible invariant for deciding isomorphism (e.g. the number of arrows in the Hassediagram), and the fact that "There might be other indices there too, and this may or may not include i." makes it unusable for that purpose. So I wonder whether it would be possible to get the Hassediagram cheaply (i.e. without constructing the closures and then calculating the cover relations). Maybe this is feature request.

You'd still have to check that two Hasse diagrams were isomorphic. This is related to Issue
#96. 
 marked as minor
 marked as enhancement
I'm updating the issue to change it to a feature request.

Oh, yes, I was not precise. I would like to use the invariant for excluding the possibility of isomorphism. If the number of edges in the Hasse diagrams are different, then the semigroups are not isomorphic so we don't need to run the expensive backtrack search on their multiplication tables (in SubSemi).

Just the code that I use for getting some complexity measure of the partial order by counting the edges in the Hasse diagram  as a temporary solution.
NrEdgesInHasseDiagramOfDClasses := function(sgp) local hd; #producing the Hasse diagram of DClasses (in a roundabout way) hd := HasseDiagramBinaryRelation( ReflexiveClosureBinaryRelation( TransitiveClosureBinaryRelation( BinaryRelationByListOfImages( PartialOrderOfDClasses(sgp))))); #calculating the number of edges (summing the sizes of the image sets) return Sum(List(Source(hd), x> Size(Images(hd,x))));; end;

In changeset de5d3efdc5b5, I introduced some functions for digraphs in the Semigroups package. In there you can find the function,
DigraphTransitiveClosure
which has complexityO(n+m+nm)
wheren
is the number of vertices andm
is the number of edges in the digraph. I think this is best possible. So, you can do:gap> S:=Semigroup( Transformation( [ 2, 4, 1, 2 ] ), > Transformation( [ 3, 3, 4, 1 ] ) );; gap> PartialOrderOfDClasses(S); [ [ 3 ], [ 2, 3 ], [ 3, 4 ], [ 4 ] ] gap> DigraphTransitiveClosure(last); [ [ 3, 4 ], [ 2, 3, 4 ], [ 3, 4 ], [ 4 ] ]
Feedback welcome as always!

Just for reference, I implemented the suggestion here.

 changed status to resolved
fixing the documentation for PartialOrderOfDClasses, which resolves Issue
#99.→ <<cset d783dde7a56c>>

 removed milestone
Removing milestone: 2.1 (automated comment)

Just a quick remark: it is called
DirectedGraphTransitiveClosure
.  Log in to comment
This is a bug in the documentation, not in the code. If
l
is the returned list, then it is guaranteed that inl[i]
are all the indices ofD
classes which are immediately below thei
thD
class. There might be other indices there too, and this may or may not includei
.So, you are correct, the documentation is wrong, I will amend it as described above, and add that it is the reflexive transitive closure which is the partial order of the
D
classes.