#19197: LatticePoset: add breadth()
-------------------------------------+-------------------------------------
Reporter: jmantysalo | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.9
Component: combinatorics | Resolution:
Keywords: | Merged in:
Authors: Jori Mäntysalo | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/jmantysalo/latticeposet__add_breadth__|
33610ad2c4327679b8dfc1d3af445fe4d9080e4a
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by jmantysalo):
More comments later (getting late here), but for this one:
Replying to [comment:17 ncohen]:
> Plus there may be vertices at distance 2 from your start vertex that
*never* get explored because you set distance=3. Do we also agree there?
This is due to the fact that a vertex is at 'distance' k from the source
vertex in a DFS if "there exists a path of length k from the source vertex
to it" (possibly a *very long* path) and that if this vertex is once
discovered at 'distance' 10 000 it may not be 'rediscovered' again at
distance 2.
No. The vertex was not discovered at distance 10 000, because search in
that path was stopped at distance 3.
I can see nothing complicated here, except maybe on terms to use. Just "Go
back when there is no more unseen vertices as neighbours." is changed to
"Go back when there is no more unseen vertices as neighbours or if the
maximum distance has already been reached."
--
Ticket URL: <http://trac.sagemath.org/ticket/19197#comment:19>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
