#19973 closed defect (fixed)
More trouble with immutable graphs
Reported by: | jaanos | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-7.1 |
Component: | graph theory | Keywords: | graphs digraphs immutable |
Cc: | ncohen | Merged in: | |
Authors: | Janoš Vidali | Reviewers: | Nathann Cohen |
Report Upstream: | N/A | Work issues: | |
Branch: | 97ab2e1 (Commits, GitHub, GitLab) | Commit: | |
Dependencies: | Stopgaps: |
Description (last modified by )
Here is a fix to a few cases where things fail with immutable graphs due to subgraph
preserving the mutability of the graph. The affected methods are traveling_salesman_problem
(and then also is_hamiltonian
and hamiltonian_cycle
) and is_clique
with the parameter directed_clique=True
.
These problems have either been missed, or, more likely, introduced in #19526.
Change History (12)
comment:1 Changed 6 years ago by
- Branch set to u/jaanos/more_trouble_with_immutable_graphs
comment:2 Changed 6 years ago by
- Cc ncohen added
- Commit set to 7cf72ddf94e1ff2693fa158a5fb9be490e776cb3
- Description modified (diff)
- Keywords graphs digraphs immutable added
- Status changed from new to needs_review
- Type changed from PLEASE CHANGE to defect
comment:3 Changed 6 years ago by
comment:4 Changed 6 years ago by
Hi!
This is the default for subgraph
since #19526 (if that's what you meant). But in these cases the algorithms change these subgraphs (in fairly trivial ways, but still), so we need them to be mutable.
Janoš
comment:5 Changed 6 years ago by
Oh. My mistake: what I meant is that the functions will now return a mutable graph (e.g. the tsp) even when called on an immutable graph. Should we change the mutability status of those graphs we are about to return to match the status of self
?
comment:6 Changed 6 years ago by
Yes, we could do that. Also, when calling is_hamiltonian
, we don't really need to construct this subgraph at all (unless it's cached somewhere, but I don't see it in the current code).
comment:7 Changed 6 years ago by
- Commit changed from 7cf72ddf94e1ff2693fa158a5fb9be490e776cb3 to 97ab2e1ef6de89e60b7088188fe81ae29f2a908b
Branch pushed to git repo; I updated commit sha1. New commits:
97ab2e1 | Return an immutable cycle from traveling_salesman_problem if the input graph is immutable
|
comment:8 Changed 6 years ago by
OK, traveling_salesman_problem
now preserves mutability. It still constructs the subgraph, even if called from is_hamiltonian
- this is, after all, the easy part of the algorithm:)
comment:9 Changed 6 years ago by
- Reviewers set to Nathann Cohen
- Status changed from needs_review to positive_review
OKayyy.. Thanks for this ticket, good to go!
comment:10 Changed 6 years ago by
- Component changed from PLEASE CHANGE to graph theory
comment:11 Changed 6 years ago by
- Branch changed from u/jaanos/more_trouble_with_immutable_graphs to 97ab2e1ef6de89e60b7088188fe81ae29f2a908b
- Resolution set to fixed
- Status changed from positive_review to closed
comment:12 Changed 6 years ago by
- Commit 97ab2e1ef6de89e60b7088188fe81ae29f2a908b deleted
Thanks again!
Wondering about the default: why shouldn't we use
immutable = self.is_immutable()
?