Opened 13 years ago

Closed 13 years ago

#7533 closed enhancement (fixed)

Implement distance graphs

Reported by: rbeezer Owned by: rlm
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:

Status badges

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)

trac_7533_distance_graphs.patch (4.2 KB) - added by rbeezer 13 years ago.
trac_7533_distance_graphs_2.patch (6.7 KB) - added by rbeezer 13 years ago.

Download all attachments as: .zip

Change History (8)

Changed 13 years ago by rbeezer

comment:1 Changed 13 years ago by rbeezer

  • Status changed from new to needs_review

comment:2 follow-up: Changed 13 years ago by ncohen

  • Status changed from needs_review to needs_work

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

comment:3 Changed 13 years ago by rbeezer

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 rbeezer

comment:4 in reply to: ↑ 2 Changed 13 years ago by rbeezer

  • Status changed from needs_work to 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 ncohen

  • Status changed from needs_review to 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 mhansen

  • Merged in set to sage-4.3.alpha1
  • Resolution set to fixed
  • Reviewers set to Nathann Cohen
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.