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.

[ncohen]

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

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

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

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

[git]

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]

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

[ncohen]

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

[jaanos]

Thanks again!