#7533: Implement distance graphs
----------------------------+-----------------------------------------------
Reporter: rbeezer | Owner: rlm
Type: enhancement | Status: needs_work
Priority: minor | Milestone: sage-4.3
Component: graph theory | Keywords: distance graph
Work_issues: | Author: Rob Beezer
Upstream: N/A | Reviewer:
Merged: |
----------------------------+-----------------------------------------------
Changes (by ncohen):
* status: needs_review => needs_work
Comment:
Hello !!!!
Several comments :
* I very often meet people interested in the graph which contains an
edge fo any pair of vertices at distance _at most_ d ( and not _exactly_ d
as you do ). Well, the only fact that you need it means that it should be
possible in Sage, but could you include in your patch something about
distance "at most" d ? Actually, I was thinking of an argument d being:
* An integer, in which case all the vertices at distance "at most"
d are linked
* A list of integers, in which case all the vertices whose
distance belongs to the list are linked
In this situation, to obtain the result you want you would need to
write distance_graph([8]).
* You are computing the distances between any pair of vertices, and
computing distance(x,y) is not the best way to do so. The Floyd-Marshall
algorithms does it way faster : see Graph.shortest_path_all_pairs ( you
will obtain the distances between any pair of vertices, plus some
information on how to build the shortest path. You are not interested in
this, but it costs nothing more to compute it ! )
* If the complexity is the same, could you replace
self.vertex_iterator by just "self" ?
* This function could also be useful in the case of DiGraphs
Short of this, the documentation/tests are excellent and this patch will
definitely be used !!!
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/7533#comment:2>
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 post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
