Opened 4 years ago
Closed 4 years ago
#26634 closed enhancement (fixed)
clean generic_graph.py (part 5)
Reported by: | dcoudert | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-8.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 4 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 4 years ago by
I do not understand why there should be a loops
for transitive_closure()
. It does not seem well-defined or useful.
comment:3 Changed 4 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 4 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 4 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 4 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 4 years ago by
Tested over 8.5.beta3.
comment:8 Changed 4 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 well-documented.
comment:9 Changed 4 years ago by
- Commit changed from 9544f15c037b791039d313e7e99302ef49c31981 to eaa7f6c58a37e5cab7ef81142ada00a46d840621
comment:10 Changed 4 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 4 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 4 years ago by
I have rebased this ticket on 8.5.beta6. The patchbot was complaining so it may help it...
comment:13 Changed 4 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 4 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