Opened 3 years ago
Last modified 3 months ago
#29346 needs_work enhancement
diameter for large directed real graphs
Reported by:  Madhav Wagle  Owned by:  

Priority:  major  Milestone:  sage9.8 
Component:  graph theory  Keywords:  gsoc, diameter, 
Cc:  Merged in:  
Authors:  Madhav Wagle  Reviewers:  
Report Upstream:  N/A  Work issues:  
Branch:  u/ghArchitWagle/real_directed_diameter (Commits, GitHub, GitLab)  Commit:  b1bb1ac1046a85a4dc0280288c3e29d426f5619f 
Dependencies:  Stopgaps: 
Description (last modified by )
This method implements the [d2] algorithm for computing the diameter of real directed graphs.
[d2] Takuya Akiba, Yoichi Iwata, Yuki Kawata: An Exact Algorithm for Diameters of Large Real Directed Graphs. SEA 2015: 5667 https://doi.org/10.1007/9783319200866_5
It is designed for directed real sparse graphs.
Change History (14)
comment:1 Changed 3 years ago by
Branch:  → u/ghArchitWagle/real_directed_diameter 

comment:2 Changed 3 years ago by
Authors:  → Madhav Wagle 

Commit:  → aceb725547c28de9969fe7684c192e1951760f1b 
Component:  PLEASE CHANGE → graph theory 
Description:  modified (diff) 
Keywords:  gsoc diameter added 
Status:  new → needs_review 
Summary:  real directed diameter → Implemented the directed diameter algorithm for real graphs in https://doi.org/10.1007/9783319200866_5 
Type:  PLEASE CHANGE → enhancement 
comment:3 Changed 3 years ago by
Summary:  Implemented the directed diameter algorithm for real graphs in https://doi.org/10.1007/9783319200866_5 → diameter for large directed real graphs 

comment:4 followup: 5 Changed 3 years ago by
Status:  needs_review → needs_info 

comment:5 Changed 3 years ago by
Replying to dcoudert:
#29309 also implements the same algorithm. Shouldn't you join forces to obtain a stronger implementation ?
Hi, The definitions of diameter used by me and #29309 are different. He has made simplifications to his code based on the standard definition of diameter (like making direct calls to
simple_BFS()
which returns diameter infinity for non strongly connected graphs.
My implementation considers the max finite eccentricty, as specified in https://doi.org/10.1007/9783319200866_5
Which returns a finite diameter for both connected and unconnected graphs
His implementation would be a much better choice if we want to keep the definition of diameter the same for all algorithms.
On the other hand, I can also modify my implementation to allow the user to set a parameter to make a choice on which definition of diameter they want to use. I would only need to add 12 lines of code to my current implementation to do that.
comment:7 Changed 3 years ago by
Commit:  aceb725547c28de9969fe7684c192e1951760f1b → b1bb1ac1046a85a4dc0280288c3e29d426f5619f 

Branch pushed to git repo; I updated commit sha1. New commits:
b1bb1ac  corrected memset calls

comment:8 Changed 3 years ago by
Milestone:  sage9.1 → sage9.2 

Batch modifying tickets that will likely not be ready for 9.1, based on a review of the ticket title, branch/review status, and last modification date.
comment:9 Changed 2 years ago by
Milestone:  sage9.2 → sage9.3 

comment:10 Changed 22 months ago by
Milestone:  sage9.3 → sage9.4 

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.
comment:11 Changed 17 months ago by
Milestone:  sage9.4 → sage9.5 

Setting a new milestone for this ticket based on a cursory review.
comment:12 Changed 12 months ago by
Milestone:  sage9.5 → sage9.6 

comment:13 Changed 8 months ago by
Milestone:  sage9.6 → sage9.7 

comment:14 Changed 3 months ago by
Milestone:  sage9.7 → sage9.8 

#29309 also implements the same algorithm. Shouldn't you join forces to obtain a stronger implementation ?