Opened 13 years ago
Closed 13 years ago
#7533 closed enhancement (fixed)
Implement distance graphs
Reported by: | Rob Beezer | Owned by: | Robert Miller |
---|---|---|---|
Priority: | minor | Milestone: | sage-4.3 |
Component: | graph theory | Keywords: | distance graph |
Cc: | Merged in: | sage-4.3.alpha1 | |
Authors: | Rob Beezer | Reviewers: | Nathann Cohen |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
Create a new graph from an old graph by making vertices of the new graph adjacent exactly when they are a certain distance apart in the old graph. This construction is useful in algebraic graph theory.
Attachments (2)
Change History (8)
Changed 13 years ago by
Attachment: | trac_7533_distance_graphs.patch added |
---|
comment:1 Changed 13 years ago by
Status: | new → needs_review |
---|
comment:2 follow-up: 4 Changed 13 years ago by
Status: | needs_review → needs_work |
---|
comment:3 Changed 13 years ago by
Hi Nathann,
Thanks for the excellent suggestions. I'll get a list argument working and look at using the shortest path routine.
Someplace in the code I got the impression the iterator is faster (by about a factor of 2).
I've tested the code for digraphs, but really am only interested in undirected graphs at the moment. With some time, I could easily generalize it later.
Rob
Changed 13 years ago by
Attachment: | trac_7533_distance_graphs_2.patch added |
---|
comment:4 Changed 13 years ago by
Status: | needs_work → needs_review |
---|
New patch addresses two of Nathann's suggestions.
- A list of distances, or a single distance, are now possible. New doctests illustrate this and aslo show how to build the graph with all the distances *less than or equal* to a specified value.
- Using
shortest_path_all_pairs()
turns out, surprisingly, to be much slower. It added about 37 seconds to running the tests for the file (from 80 seconds to 117 seconds). For the odd graph with parameter 5 (on 126 vertices), the "all pair" version took about 20 seconds while the version in the current patch (which uses.distance()
) takes a bit over 2 seconds.
comment:5 Changed 13 years ago by
Status: | needs_review → positive_review |
---|
Positive review !!! You changed the definition to have d ( integer ) represent an unique distance, and not range(distance), which is not the best for my usage, but clearly the best for Sage and for comprehension. Good idea.
I created ticket #7540 about the difference in speed, which is an oddness we must fix ...
Positive review, excellent patch !
Nathann
comment:6 Changed 13 years ago by
Merged in: | → sage-4.3.alpha1 |
---|---|
Resolution: | → fixed |
Reviewers: | → Nathann Cohen |
Status: | positive_review → closed |
Hello !!!!
Several comments :
- 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]).Short of this, the documentation/tests are excellent and this patch will definitely be used !!!
Nathann