Opened 3 years ago
Closed 3 years ago
#26675 closed enhancement (fixed)
clean generic_graph.py (part 11)  substructures
Reported by:  dcoudert  Owned by:  

Priority:  major  Milestone:  sage8.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, GitHub, GitLab)  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 ifself.allows_multiple_edges()
but ifself.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 3 years ago by
 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
comment:2 Changed 3 years ago by
 Commit changed from b3cb0551969cfa4cc5d137a50a824bee6f7d91f6 to 020daadfc3d29da7649fb4edc53d7bf88dbd1c0c
Branch pushed to git repo; I updated commit sha1. New commits:
020daad  trac #26675: update table of methods

comment:3 Changed 3 years ago by
 Commit changed from 020daadfc3d29da7649fb4edc53d7bf88dbd1c0c to 6591aab3f6b69ff890bdf921e2e18203ff1cf8a6
Branch pushed to git repo; I updated commit sha1. New commits:
6591aab  trac #26675: Merged with 8.5.beta6

comment:4 Changed 3 years ago by
rebase on 8.5.beta6 to help the patchbot.
comment:5 Changed 3 years ago by
LGTM overall. Do you have a test that shows this bug in is_hamiltonian
is fixed?
comment:6 Changed 3 years ago by
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/sitepackages/sage/doctest/forker.py", line 671, in _run self.compile_and_execute(example, compiler, test.globs) File "/Users/dcoudert/sage/local/lib/python2.7/sitepackages/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/sitepackages/sage/graphs/generic_graph.py", line 21734, in is_hamiltonian verbose=verbose, verbose_constraints=verbose_constraints) File "/Users/dcoudert/sage/local/lib/python2.7/sitepackages/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/sitepackages/sage/graphs/generic_graph.py", line 11932, in subgraph immutable=immutable) File "/Users/dcoudert/sage/local/lib/python2.7/sitepackages/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 3 years ago by
 Reviewers set to Travis Scrimshaw
 Status changed from needs_review to positive_review
Okay, thanks.
comment:8 Changed 3 years ago by
 Branch changed from public/26675_generic_graph_part_11_substructures to 6591aab3f6b69ff890bdf921e2e18203ff1cf8a6
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
trac #26675: generic_graph (part 11)  substructures