clean generic_graph.py (part 11) - substructures

[dcoudert]

We clean methods subgraph, _subgraph_by_adding, _subgraph_by_deleting, subgraph_search, subgraph_search_count, subgraph_search_iterator, random_subgraph, is_chordal, is_circulant, is_interval, is_gallai_tree, is_clique, is_cycle, is_independent_set, is_subgraph.

• PEP8 cleaning

• avoid sortings in methods _subgraph_by_adding and _subgraph_by_deleting and slightly speed up the methods by using sets instead of lists for checking membership.

• fix bug in is_hamiltonian for graphs on 2 vertices with multiple edges that is raised by the changes done in _subgraph_by_deleting. Roughly, we were not testing if self.allows_multiple_edges() but if self.has_multiple_edges(). Consequently, in some situation we were returning edge (u, v, [l]) instead of (u, v, l), but (u, v, [l]) is not hashable! The changes done here are not conflicting with the changes done in clean generic_graph.py (part 8) - connectivity #26663.

• avoid comparison of vertex labels in is_clique using a mapping to integers

• small improvement in is_independent_set to avoid a copy

CC: @tscrim @fchapoton

Component: graph theory

Author: David Coudert

Branch/Commit: 6591aab

Reviewer: Travis Scrimshaw

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

[dcoudert]

Commit: b3cb055

[dcoudert]

Branch: public/26675_generic_graph_part_11_substructures

[dcoudert]

New commits:

b3cb055

trac #26675: generic_graph (part 11) - substructures

[sagetrac-git]

Changed commit from b3cb055 to 020daad

[sagetrac-git]

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

020daad

trac #26675: update table of methods

[sagetrac-git]

Changed commit from 020daad to 6591aab

[sagetrac-git]

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

6591aab

trac #26675: Merged with 8.5.beta6

[dcoudert]

comment:4

rebase on 8.5.beta6 to help the patchbot.

[tscrim]

comment:5

LGTM overall. Do you have a test that shows this bug in is_hamiltonian is fixed?

[dcoudert]

comment:6

If I don't do this change in traveling_salesman_problem:

-                    if self.has_multiple_edges():
+                    if self.allows_multiple_edges():

then I get:

Failed example:
    DiGraph([(0,1),(1,0)],multiedges=True).is_hamiltonian()
Exception raised:
    Traceback (most recent call last):
      File "/Users/dcoudert/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 671, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/Users/dcoudert/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 1086, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.graphs.generic_graph.GenericGraph.?[46]>", line 1, in <module>
        DiGraph([(Integer(0),Integer(1)),(Integer(1),Integer(0))],multiedges=True).is_hamiltonian()
      File "/Users/dcoudert/sage/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py", line 21734, in is_hamiltonian
        verbose=verbose, verbose_constraints=verbose_constraints)
      File "/Users/dcoudert/sage/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py", line 7555, in traveling_salesman_problem
        answer = self.subgraph(edges=edges, immutable=self.is_immutable())
      File "/Users/dcoudert/sage/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py", line 11932, in subgraph
        immutable=immutable)
      File "/Users/dcoudert/sage/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py", line 12214, in _subgraph_by_deleting
        edges_to_keep_labeled = frozenset(e for e in edges if len(e) == 3)
    TypeError: unhashable type: 'list'

Indeed, when the graph allows multiple edges, G.edge_label(u, v) returns a list, even if there is only one edge from u to v.

So the doctest is already here.

[tscrim]

comment:7

Okay, thanks.

[tscrim]

Reviewer: Travis Scrimshaw

[vbraun]

Changed branch from public/26675_generic_graph_part_11_substructures to 6591aab