More trouble with immutable graphs

[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.

CC: @nathanncohen

Component: graph theory

Keywords: graphs digraphs immutable

Author: Janoš Vidali

Branch: 97ab2e1

Reviewer: Nathann Cohen

Issue created by migration from https://trac.sagemath.org/ticket/19973

[jaanos]

Branch: u/jaanos/more_trouble_with_immutable_graphs

[jaanos]

Description changed:

--- 
+++ 
@@ -1 +1,3 @@
+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.

[jaanos]

Changed keywords from none to graphs digraphs immutable

[jaanos]

Commit: 7cf72dd

[jaanos]

Author: Janoš Vidali

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:3

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

[jaanos]

comment:4

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š

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:5

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?

[jaanos]

comment:6

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).

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 7cf72dd to 97ab2e1

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

[jaanos]

comment:8

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

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

Reviewer: Nathann Cohen

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:9

OKayyy.. Thanks for this ticket, good to go!

[vbraun]

Changed branch from u/jaanos/more_trouble_with_immutable_graphs to 97ab2e1

[jaanos]

comment:12

Thanks again!

[jaanos]

Changed commit from 97ab2e1 to none