Opened 6 years ago

Closed 6 years ago

Last modified 6 years ago

#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:

Status badges

Description (last modified by jaanos)

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 jaanos

  • Branch set to u/jaanos/more_trouble_with_immutable_graphs

comment:2 Changed 6 years ago by jaanos

  • Authors set to Janoš Vidali
  • 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 ncohen

Wondering about the default: why shouldn't we use immutable = self.is_immutable()?

comment:4 Changed 6 years ago by jaanos

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 ncohen

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 jaanos

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 git

  • Commit changed from 7cf72ddf94e1ff2693fa158a5fb9be490e776cb3 to 97ab2e1ef6de89e60b7088188fe81ae29f2a908b

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

97ab2e1Return an immutable cycle from traveling_salesman_problem if the input graph is immutable

comment:8 Changed 6 years ago by jaanos

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 ncohen

  • 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 ncohen

  • Component changed from PLEASE CHANGE to graph theory

comment:11 Changed 6 years ago by vbraun

  • 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 jaanos

  • Commit 97ab2e1ef6de89e60b7088188fe81ae29f2a908b deleted

Thanks again!

Note: See TracTickets for help on using tickets.