Opened 4 years ago

Closed 4 years ago

#26547 closed enhancement (fixed)

clean spanning_tree.pyx

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: dce10d8 (Commits, GitHub, GitLab) Commit: dce10d89f35d9b6ff89791781ff75521e6f146eb
Dependencies: Stopgaps:

Status badges

Description

Done in this ticket:

  • rewrite/simply kruskal using proper DisjointSet
  • avoid comparison of vertex labels in boruvka using frozenset
  • PEP8 cleaning

Some sort operations remain in kruskal.

  • Edges must be visited by increasing weights. However, there is no reason for sorting by vertex labels as well
  • the output list of edges is sorted. There is no reason for this, especially since other methods don't do that, e.g., boruvka

So we can decide to change that as well in this ticket.

Change History (4)

comment:1 Changed 4 years ago by dcoudert

Branch: public/26547_spanning_tree
Cc: tscrim chapoton added
Commit: dce10d89f35d9b6ff89791781ff75521e6f146eb

New commits:

dce10d8trac #26547: clean spanning_tree.pyx

comment:2 Changed 4 years ago by dcoudert

Status: newneeds_review

comment:3 Changed 4 years ago by tscrim

Reviewers: Travis Scrimshaw
Status: needs_reviewpositive_review

LGTM.

comment:4 Changed 4 years ago by vbraun

Branch: public/26547_spanning_treedce10d89f35d9b6ff89791781ff75521e6f146eb
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.