clean generic_graph.py (part 5)

[dcoudert]

Here, we improve methods antisymmetric, transitive_closure, is_transitively_reduced and transitive_reduction. In particular, we add parameter loops to transitive_closure to control the addition of loops to the resulting graph (e.g., add a loop to u if u belongs to a directed cycle).

[dcoudert]

New commits:

​3a7686a

trac #26634: part 5

[tscrim]

I do not understand why there should be a loops for transitive_closure(). It does not seem well-defined or useful.

[dcoudert]

You are right and I should change that but I don't know what would be a good way to handle graphs with loops: remove loops ? put loops everywhere ? keep existing loops only ?

[tscrim]

I would either just keep existing loops or raise an error. One could make the case for removing loops too, but I would rather just keep what is there.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​9544f15

trac #26634: update the behavior of transitive_closure

[dcoudert]

Would that be better ? Roughly: if the graph has loops, either we let them in the transitive closure (loops=True) or we remove them from the transitive closure (loops=False).

Before this patch, a loop was added to each vertex of the the transitive closure of a graph without loops but allowing loops.

[dcoudert]

Tested over 8.5.beta3.

[tscrim]

Sorry, I have been really busy and can only do a few quick things with Sage right now. I am keeping track of the larger changes you are doing and plan to review them all.

Thinking a little bit more, I think adding a loop to every vertex might be the most reasonable definition of the transitive closure of a graph that allows loops. I do not think removing loops is a good way to do it as the transitive closure should always contain the original graph as an induced subgraph. So perhaps there is some fringe benefit to having a loops option, but I am more inclined to keep the current behavior. If you wanted a graph with loops, you would have already created a graph allowing loops. However, this behavior should be well-documented.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​1ba9a09	trac #26634: Merged with 8.5.beta3
​eaa7f6c	trac #26634: revert behavior of transitive_closure

[dcoudert]

I have reverted transitive_closure to it's initial behavior but added a clear note about loops, plus examples. I have also added an example in antisymmetric to show the that loops in directed graphs are ignored.

PS: I really understand time constraints, busy schedule and heavy load :(

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​5c2c2f6

trac #26634: Merged with 8.5.beta6

[dcoudert]

I have rebased this ticket on 8.5.beta6. The patchbot was complaining so it may help it...

[chapoton]

ok, let it be