Opened 4 years ago

Closed 4 years ago

#26675 closed enhancement (fixed)

clean (part 11) - substructures

Reported by: David Coudert Owned by:
Priority: major Milestone: sage-8.5
Component: graph theory Keywords: py3, graph
Cc: Travis Scrimshaw, Frédéric Chapoton Merged in:
Authors: David Coudert Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 6591aab (Commits, GitHub, GitLab) Commit: 6591aab3f6b69ff890bdf921e2e18203ff1cf8a6
Dependencies: Stopgaps:

Status badges


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 #26663.
  • avoid comparison of vertex labels in is_clique using a mapping to integers
  • small improvement in is_independent_set to avoid a copy

Change History (8)

comment:1 Changed 4 years ago by David Coudert

Branch: public/26675_generic_graph_part_11_substructures
Cc: Travis Scrimshaw Frédéric Chapoton added
Commit: b3cb0551969cfa4cc5d137a50a824bee6f7d91f6
Status: newneeds_review
Summary: clean (part 11) -clean (part 11) - substructures

New commits:

b3cb055trac #26675: generic_graph (part 11) - substructures

comment:2 Changed 4 years ago by git

Commit: b3cb0551969cfa4cc5d137a50a824bee6f7d91f6020daadfc3d29da7649fb4edc53d7bf88dbd1c0c

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

020daadtrac #26675: update table of methods

comment:3 Changed 4 years ago by git

Commit: 020daadfc3d29da7649fb4edc53d7bf88dbd1c0c6591aab3f6b69ff890bdf921e2e18203ff1cf8a6

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

6591aabtrac #26675: Merged with 8.5.beta6

comment:4 Changed 4 years ago by David Coudert

rebase on 8.5.beta6 to help the patchbot.

comment:5 Changed 4 years ago by Travis Scrimshaw

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

comment:6 Changed 4 years ago by David Coudert

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:
Exception raised:
    Traceback (most recent call last):
      File "/Users/dcoudert/sage/local/lib/python2.7/site-packages/sage/doctest/", line 671, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/Users/dcoudert/sage/local/lib/python2.7/site-packages/sage/doctest/", line 1086, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.graphs.generic_graph.GenericGraph.?[46]>", line 1, in <module>
      File "/Users/dcoudert/sage/local/lib/python2.7/site-packages/sage/graphs/", line 21734, in is_hamiltonian
        verbose=verbose, verbose_constraints=verbose_constraints)
      File "/Users/dcoudert/sage/local/lib/python2.7/site-packages/sage/graphs/", 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/", line 11932, in subgraph
      File "/Users/dcoudert/sage/local/lib/python2.7/site-packages/sage/graphs/", 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.

comment:7 Changed 4 years ago by Travis Scrimshaw

Reviewers: Travis Scrimshaw
Status: needs_reviewpositive_review

Okay, thanks.

comment:8 Changed 4 years ago by Volker Braun

Branch: public/26675_generic_graph_part_11_substructures6591aab3f6b69ff890bdf921e2e18203ff1cf8a6
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.