Opened 2 years ago
Closed 2 years ago
#26634 closed enhancement (fixed)
clean generic_graph.py (part 5)
Reported by:  dcoudert  Owned by:  

Priority:  major  Milestone:  sage8.5 
Component:  graph theory  Keywords:  py3, graph 
Cc:  tscrim  Merged in:  
Authors:  David Coudert  Reviewers:  Travis Scrimshaw, Frédéric Chapoton 
Report Upstream:  N/A  Work issues:  
Branch:  5c2c2f6 (Commits, GitHub, GitLab)  Commit:  5c2c2f65cfab29add7333e55ba8ea0132a2a7f54 
Dependencies:  Stopgaps: 
Description
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).
Change History (14)
comment:1 Changed 2 years ago by
 Branch set to public/26634_generic_graph_part_5
 Cc tscrim added
 Commit set to 3a7686aabf265b5d55080eb0e6f50fca83d5bd68
 Status changed from new to needs_review
comment:2 Changed 2 years ago by
I do not understand why there should be a loops
for transitive_closure()
. It does not seem welldefined or useful.
comment:3 Changed 2 years ago by
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 ?
comment:4 Changed 2 years ago by
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.
comment:5 Changed 2 years ago by
 Commit changed from 3a7686aabf265b5d55080eb0e6f50fca83d5bd68 to 9544f15c037b791039d313e7e99302ef49c31981
Branch pushed to git repo; I updated commit sha1. New commits:
9544f15  trac #26634: update the behavior of transitive_closure

comment:6 Changed 2 years ago by
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.
comment:7 Changed 2 years ago by
Tested over 8.5.beta3.
comment:8 Changed 2 years ago by
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 welldocumented.
comment:9 Changed 2 years ago by
 Commit changed from 9544f15c037b791039d313e7e99302ef49c31981 to eaa7f6c58a37e5cab7ef81142ada00a46d840621
comment:10 Changed 2 years ago by
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 :(
comment:11 Changed 2 years ago by
 Commit changed from eaa7f6c58a37e5cab7ef81142ada00a46d840621 to 5c2c2f65cfab29add7333e55ba8ea0132a2a7f54
Branch pushed to git repo; I updated commit sha1. New commits:
5c2c2f6  trac #26634: Merged with 8.5.beta6

comment:12 Changed 2 years ago by
I have rebased this ticket on 8.5.beta6. The patchbot was complaining so it may help it...
comment:13 Changed 2 years ago by
 Reviewers set to Travis Scrimshaw, Frédéric Chapoton
 Status changed from needs_review to positive_review
ok, let it be
comment:14 Changed 2 years ago by
 Branch changed from public/26634_generic_graph_part_5 to 5c2c2f65cfab29add7333e55ba8ea0132a2a7f54
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
trac #26634: part 5