Opened 2 years ago
Closed 2 years ago
#29660 closed enhancement (fixed)
Move radius, diameter and eccentricity methods from generic_graph.py to graph.py and digraph.py
Reported by:  vipul73921  Owned by:  

Priority:  major  Milestone:  sage9.2 
Component:  graph theory  Keywords:  gsoc20 
Cc:  David Coudert  Merged in:  
Authors:  Vipul Gupta  Reviewers:  David Coudert 
Report Upstream:  N/A  Work issues:  
Branch:  9e2dcc8 (Commits, GitHub, GitLab)  Commit:  9e2dcc8af873970454449639cb7ee253289447c9 
Dependencies:  Stopgaps: 
Description
Currently radius, diameter and eccentricity computation methods are in generic_graph.py file. Since graph and digraph both have different algorithms for their computation. So it would be nice to have these method separately for graph and digraph in respective files.
Change History (9)
comment:1 Changed 2 years ago by
Branch:  → u/ghvipul79321/ticket29660 

Status:  new → needs_review 
comment:2 Changed 2 years ago by
Commit:  → bf852a412f4f730b2b4e2eadd6e3d4c5f1f2b24c 

comment:3 Changed 2 years ago by
Authors:  → Vipul Gupta 

comment:4 followup: 6 Changed 2 years ago by
 There is no need to add before the methods
+ # Eccentricity + # Radius
 This part is a perfect example of why we must add an eccentricity method in boost backend. It makes no sense to use boost to compute APSP, then return a dictionary of dictionaries with the distances (taking very long time to build and consuming a lot of memory) and finally get the largest value. We could directly return the eccentricities from boost.
+ if algorithm in ['FloydWarshallPython', 'FloydWarshallCython', 'Johnson_Boost']: + dist_dict = self.shortest_path_all_pairs(by_weight, algorithm, + weight_function, + check_weight)[0] + algorithm = 'From_Dictionary'
Overall, I think this change ease the identification of missing methods and bad implementation choices. We must avoid as much as possible the use of dist_dict
.
comment:5 Changed 2 years ago by
Commit:  bf852a412f4f730b2b4e2eadd6e3d4c5f1f2b24c → 9e2dcc8af873970454449639cb7ee253289447c9 

Branch pushed to git repo; I updated commit sha1. New commits:
9e2dcc8  unneccessary comments removed

comment:6 Changed 2 years ago by
comment:7 Changed 2 years ago by
Reviewers:  → David Coudert 

Status:  needs_review → positive_review 
LGTM.
comment:8 Changed 2 years ago by
Keywords:  gsoc20 added; gsoc removed 

just update the keyword to gsoc20
comment:9 Changed 2 years ago by
Branch:  u/ghvipul79321/ticket29660 → 9e2dcc8af873970454449639cb7ee253289447c9 

Resolution:  → fixed 
Status:  positive_review → closed 
Note: See
TracTickets for help on using
tickets.
Branch pushed to git repo; I updated commit sha1. New commits:
radius, diameter, eccentricity, center, periphery moved to graph and digraph separately