Opened 4 years ago
Closed 8 months ago
#22613 closed enhancement (duplicate)
Rewrite kruskal() to use yield
Reported by: | epilys | Owned by: | |
---|---|---|---|
Priority: | trivial | Milestone: | sage-duplicate/invalid/wontfix |
Component: | graph theory | Keywords: | |
Cc: | Merged in: | ||
Authors: | Reviewers: | David Coudert | |
Report Upstream: | N/A | Work issues: | |
Branch: | u/epilys/rewrite_kruskal___to_use_yield (Commits, GitHub, GitLab) | Commit: | ddbe075bc8e8b3daed0b6edaf150a48c6e7a2315 |
Dependencies: | Stopgaps: |
Description
Convert kruskal() into a generator, eg:
sage: from sage.graphs.spanning_tree import kruskal sage: G = Graph([[0,1,1],[1,2,1],[2,0,10]], weighted=True) sage: k = kruskal(G, check=True) sage: k <generator object at 0x7f5ba76dfe60> sage: k.next() (0, 1, 1) sage: k.next() (1, 2, 1) sage: k.next() --------------------------------------------------------------------------- StopIteration Traceback (most recent call last) <ipython-input-16-3790cf7939d1> in <module>() ----> 1 k.next() StopIteration: sage: list(kruskal(G, check=True)) [(0, 1, 1), (1, 2, 1)]
Change History (6)
comment:1 Changed 4 years ago by
- Branch set to u/epilys/rewrite_kruskal___to_use_yield
comment:2 Changed 4 years ago by
- Commit set to ddbe075bc8e8b3daed0b6edaf150a48c6e7a2315
- Status changed from new to needs_review
comment:3 Changed 4 years ago by
- Reviewers set to David Coudert
- Status changed from needs_review to needs_work
I have changed my comments since I was not on the correct version.
Something goes wrong. This should not be the expected behavior since
sage: from sage.graphs.spanning_tree import kruskal sage: G = graphs.PetersenGraph() sage: kruskal(G) <generator object at 0x1d2ff2950> sage: list(kruskal(G)) [(0, 1, None), (0, 4, None), (0, 5, None), (1, 2, None), (1, 6, None), (2, 3, None), (2, 7, None), (3, 8, None), (4, 9, None)] sage: G = 2*G sage: list(kruskal(G)) [(0, 1, None), (0, 4, None), (0, 5, None), (1, 2, None), (1, 6, None), (2, 3, None), (2, 7, None), (3, 8, None), (4, 9, None), (10, 11, None), (10, 14, None), (10, 15, None), (11, 12, None), (11, 16, None), (12, 13, None), (12, 17, None), (13, 18, None), (14, 19, None)] sage: G.is_connected() False sage: G.spanning_trees() [] sage: list(kruskal(Graph())) []
Also, the text A generator of the edges of a minimum spanning tree of
G
`, if one exists,
otherwise returns the empty list.` is not appropriate since a generator might return StopIteration? but not an empty list.
Don't forget to put your name as author.
comment:4 Changed 2 years ago by
- Milestone set to sage-duplicate/invalid/wontfix
This has been done in #26614, so I change the milestone to sage-duplicate/invalid/wontfix
.
comment:5 Changed 8 months ago by
- Status changed from needs_work to positive_review
This ticket can be closed.
comment:6 Changed 8 months ago by
- Resolution set to duplicate
- Status changed from positive_review to closed
Note: See
TracTickets for help on using
tickets.
New commits:
Rewrite kruskal() to use yield