#26675 closed enhancement (fixed)

clean generic_graph.py (part 11) - substructures

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

Description

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 13 months ago by dcoudert

  • Branch set to public/26675_generic_graph_part_11_substructures
  • Cc tscrim chapoton added
  • Commit set to b3cb0551969cfa4cc5d137a50a824bee6f7d91f6
  • Status changed from new to needs_review
  • Summary changed from clean generic_graph.py (part 11) - to clean generic_graph.py (part 11) - substructures

New commits:

b3cb055trac #26675: generic_graph (part 11) - substructures

comment:2 Changed 13 months ago by git

  • Commit changed from b3cb0551969cfa4cc5d137a50a824bee6f7d91f6 to 020daadfc3d29da7649fb4edc53d7bf88dbd1c0c

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

020daadtrac #26675: update table of methods

comment:3 Changed 12 months ago by git

  • Commit changed from 020daadfc3d29da7649fb4edc53d7bf88dbd1c0c to 6591aab3f6b69ff890bdf921e2e18203ff1cf8a6

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

6591aabtrac #26675: Merged with 8.5.beta6

comment:4 Changed 12 months ago by dcoudert

rebase on 8.5.beta6 to help the patchbot.

comment:5 Changed 12 months ago by tscrim

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

comment:6 Changed 12 months ago by dcoudert

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.

comment:7 Changed 12 months ago by tscrim

  • Reviewers set to Travis Scrimshaw
  • Status changed from needs_review to positive_review

Okay, thanks.

comment:8 Changed 12 months ago by vbraun

  • Branch changed from public/26675_generic_graph_part_11_substructures to 6591aab3f6b69ff890bdf921e2e18203ff1cf8a6
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.