id summary reporter owner description type status priority milestone component resolution keywords cc merged author reviewer upstream work_issues branch commit dependencies stopgaps
26675 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 #26663.
- avoid comparison of vertex labels in `is_clique` using a mapping to integers
- small improvement in `is_independent_set` to avoid a copy" enhancement closed major sage-8.5 graph theory fixed py3, graph tscrim chapoton David Coudert Travis Scrimshaw N/A 6591aab3f6b69ff890bdf921e2e18203ff1cf8a6 6591aab3f6b69ff890bdf921e2e18203ff1cf8a6