Opened 13 years ago

Closed 13 years ago

# Implement distance graphs

Reported by: Owned by: Rob Beezer Robert Miller minor sage-4.3 graph theory distance graph sage-4.3.alpha1 Rob Beezer Nathann Cohen N/A

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

### comment:1 Changed 13 years ago by Rob Beezer

Status: new → needs_review

### comment:2 follow-up:  4 Changed 13 years ago by Nathann Cohen

Status: needs_review → needs_work

Hello !!!!

• 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

### comment:3 Changed 13 years ago by Rob Beezer

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

### comment:4 in reply to:  2 Changed 13 years ago by Rob Beezer

Status: needs_work → needs_review

New patch addresses two of Nathann's suggestions.

1. 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.
1. 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 Nathann Cohen

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 Mike Hansen

Merged in: → sage-4.3.alpha1 → fixed → Nathann Cohen positive_review → closed
Note: See TracTickets for help on using tickets.