Opened 4 years ago

Closed 4 years ago

#27009 closed enhancement (fixed)

py3: avoid sorting vertices and edges in method treewidth

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

Status badges


We avoid sorting vertices, edges and connected components. The code is better this way, and this fixes a doctest error with py3.

Change History (7)

comment:1 Changed 4 years ago by dcoudert

  • Branch set to public/27009_treewidth
  • Cc tscrim chapoton added
  • Commit set to f830eb94a953905c3b6e6540e46e2319fb8a3e41
  • Status changed from new to needs_review

New commits:

f830eb9trac #27009: avoid sorting in method treewidth

comment:2 Changed 4 years ago by tscrim

Why do you use for v in G.vertices(sort=False): instead of one of the iterators?

Other than that LGTM.

comment:3 Changed 4 years ago by dcoudert

The graph is modified inside the loop over all vertices, so I cannot use an iterator here (at least it's safer this way). So we can use either G.vertices(sort=False) or list(G).

comment:4 Changed 4 years ago by tscrim

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

Okay, thanks for the explanation. LGTM.

comment:5 Changed 4 years ago by dcoudert

Thank you for the reviews and happy new year !

comment:6 Changed 4 years ago by embray

  • Milestone changed from sage-8.6 to sage-8.7

Retarging tickets optimistically to the next milestone. If you are responsible for this ticket (either its reporter or owner) and don't believe you are likely to complete this ticket before the next release (8.7) please retarget this ticket's milestone to sage-pending or sage-wishlist.

comment:7 Changed 4 years ago by vbraun

  • Branch changed from public/27009_treewidth to f830eb94a953905c3b6e6540e46e2319fb8a3e41
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.