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: sage-9.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:

Status badges

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 vipul73921

Branch: u/gh-vipul79321/ticket29660
Status: newneeds_review

comment:2 Changed 2 years ago by git

Commit: bf852a412f4f730b2b4e2eadd6e3d4c5f1f2b24c

Branch pushed to git repo; I updated commit sha1. New commits:

bf852a4radius, diameter, eccentricity, center, periphery moved to graph and digraph separately

comment:3 Changed 2 years ago by vipul73921

Authors: Vipul Gupta

comment:4 Changed 2 years ago by David Coudert

  • 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 ['Floyd-Warshall-Python', 'Floyd-Warshall-Cython', '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 git

Commit: bf852a412f4f730b2b4e2eadd6e3d4c5f1f2b24c9e2dcc8af873970454449639cb7ee253289447c9

Branch pushed to git repo; I updated commit sha1. New commits:

9e2dcc8unneccessary comments removed

comment:6 in reply to:  4 Changed 2 years ago by vipul73921

Replying to dcoudert:

  • There is no need to add before the methods
    +    # Eccentricity
    +    # Radius
    

Done

comment:7 Changed 2 years ago by David Coudert

Reviewers: David Coudert
Status: needs_reviewpositive_review

LGTM.

comment:8 Changed 2 years ago by David Coudert

Keywords: gsoc20 added; gsoc removed

just update the keyword to gsoc20

comment:9 Changed 2 years ago by Volker Braun

Branch: u/gh-vipul79321/ticket296609e2dcc8af873970454449639cb7ee253289447c9
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.