#17537: The geodetic closure of a graph
-------------------------------------+-------------------------------------
Reporter: azi | Owner:
Type: enhancement | Status: needs_info
Priority: minor | Milestone: sage-6.5
Component: graph theory | Resolution:
Keywords: | Merged in:
Authors: Jernej Azarija | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/azi/geodeticClosure | 04f03328e877d2c35ee52228ffde216ae8cb262e
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Changes (by ncohen):
* status: needs_review => needs_info
Comment:
Hmmm... Calling "distances_all_pairs" in a function like that is a
suicide. You cannot re-compute all distances every time you want to
compute a closure. Actually, the information that you need is precisely
the one that is stored in `convexity_properties`.
The "convexity properties" object associates to every pair of vertices
`u,v` the bitset of all z such that z is on a shortest uv path. Thus if
you need to find the closure of a set of points, all you have to do is
compute the union (with 'or' processor operations) of the bitsets
associated to all pairs of vertices.
My point is that the code is already there, but of course the name
'convexity properties' is very ill-chosen in this case. We will probably
have to change the terminology... What do you think about all this ?
By the way, is the terminology 'closure' used anywhere ? Because formally
it is not a closure function. One of the property of closure functions is
that `f(f(X))` should be equal to `f(x)`.
Nathann
--
Ticket URL: <http://trac.sagemath.org/ticket/17537#comment:5>
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.
