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:

Status badges

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 epilys

  • Branch set to u/epilys/rewrite_kruskal___to_use_yield

comment:2 Changed 4 years ago by epilys

  • Commit set to ddbe075bc8e8b3daed0b6edaf150a48c6e7a2315
  • Status changed from new to needs_review

New commits:

ddbe075Rewrite kruskal() to use yield

comment:3 Changed 4 years ago by dcoudert

  • 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.

Last edited 4 years ago by dcoudert (previous) (diff)

comment:4 Changed 2 years ago by dcoudert

  • 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 dcoudert

  • Status changed from needs_work to positive_review

This ticket can be closed.

comment:6 Changed 8 months ago by chapoton

  • Resolution set to duplicate
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.