#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) 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 11 months ago by dcoudert

  • Branch set to public/26634_generic_graph_part_5
  • Cc tscrim added
  • Commit set to 3a7686aabf265b5d55080eb0e6f50fca83d5bd68
  • Status changed from new to needs_review

New commits:

3a7686atrac #26634: part 5

comment:2 Changed 11 months ago by tscrim

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

comment:3 Changed 11 months ago by 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 ?

comment:4 Changed 11 months ago by 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.

comment:5 Changed 11 months ago by git

  • Commit changed from 3a7686aabf265b5d55080eb0e6f50fca83d5bd68 to 9544f15c037b791039d313e7e99302ef49c31981

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

9544f15trac #26634: update the behavior of transitive_closure

comment:6 Changed 11 months ago by 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.

comment:7 Changed 10 months ago by dcoudert

Tested over 8.5.beta3.

comment:8 Changed 10 months ago by 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.

comment:9 Changed 10 months ago by git

  • Commit changed from 9544f15c037b791039d313e7e99302ef49c31981 to eaa7f6c58a37e5cab7ef81142ada00a46d840621

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

1ba9a09trac #26634: Merged with 8.5.beta3
eaa7f6ctrac #26634: revert behavior of transitive_closure

comment:10 Changed 10 months ago by 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 :(

comment:11 Changed 10 months ago by git

  • Commit changed from eaa7f6c58a37e5cab7ef81142ada00a46d840621 to 5c2c2f65cfab29add7333e55ba8ea0132a2a7f54

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

5c2c2f6trac #26634: Merged with 8.5.beta6

comment:12 Changed 10 months ago by dcoudert

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

comment:13 Changed 10 months ago by chapoton

  • Reviewers set to Travis Scrimshaw, Frédéric Chapoton
  • Status changed from needs_review to positive_review

ok, let it be

comment:14 Changed 10 months ago by vbraun

  • Branch changed from public/26634_generic_graph_part_5 to 5c2c2f65cfab29add7333e55ba8ea0132a2a7f54
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.