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

Priority:  major  Milestone:  sage8.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: 
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 4 years ago by
Branch:  → public/26675_generic_graph_part_11_substructures 

Cc:  Travis Scrimshaw Frédéric Chapoton added 
Commit:  → b3cb0551969cfa4cc5d137a50a824bee6f7d91f6 
Status:  new → needs_review 
Summary:  clean generic_graph.py (part 11)  → clean generic_graph.py (part 11)  substructures 
comment:2 Changed 4 years ago by
Commit:  b3cb0551969cfa4cc5d137a50a824bee6f7d91f6 → 020daadfc3d29da7649fb4edc53d7bf88dbd1c0c 

Branch pushed to git repo; I updated commit sha1. New commits:
020daad  trac #26675: update table of methods

comment:3 Changed 4 years ago by
Commit:  020daadfc3d29da7649fb4edc53d7bf88dbd1c0c → 6591aab3f6b69ff890bdf921e2e18203ff1cf8a6 

Branch pushed to git repo; I updated commit sha1. New commits:
6591aab  trac #26675: Merged with 8.5.beta6

comment:5 Changed 4 years ago by
LGTM overall. Do you have a test that shows this bug in is_hamiltonian
is fixed?
comment:6 Changed 4 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 4 years ago by
Reviewers:  → Travis Scrimshaw 

Status:  needs_review → positive_review 
Okay, thanks.
comment:8 Changed 4 years ago by
Branch:  public/26675_generic_graph_part_11_substructures → 6591aab3f6b69ff890bdf921e2e18203ff1cf8a6 

Resolution:  → fixed 
Status:  positive_review → closed 
New commits:
trac #26675: generic_graph (part 11)  substructures