Opened 13 months ago

Closed 7 months ago

#29431 closed enhancement (duplicate)

certificate based radius for undirected unweighed graphs

Reported by: gh-ArchitWagle Owned by:
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: graph theory Keywords: graph, gsoc, radius
Cc: Merged in:
Authors: Reviewers: David Coudert
Report Upstream: N/A Work issues:
Branch: u/gh-ArchitWagle/certificate_based_radius_for_undirected_unweighed_graphs (Commits, GitHub, GitLab) Commit: 6dd478d063b40493ccc136831acfebfa1c92325c
Dependencies: Stopgaps:

Status badges

Description (last modified by gh-ArchitWagle)

This ticket implements the radius algorithm given in http://arxiv.org/abs/1803.04660

It performs very well

( >90% reduction in execution time on all graphs I tried)

: G = Graph(4)                           
....: while not G.is_connected():
....:     G = graphs.RandomGNP(10000,0.008)
....:     

sage: %time G.radius()
CPU times: user 23min 30s, sys: 4min 9s, total: 27min 39s
Wall time: 27min 39s
3

sage: %time G.radius(algorithm="radius-certificate")
CPU times: user 231 ms, sys: 4.38 ms, total: 236 ms
3

Change History (10)

comment:1 Changed 13 months ago by gh-ArchitWagle

  • Branch set to u/gh-ArchitWagle/certificate_based_radius_for_undirected_unweighed_graphs

comment:2 Changed 13 months ago by gh-ArchitWagle

  • Commit set to 590904a2561944a846218bb06aa0f551dbe261fd
  • Component changed from PLEASE CHANGE to graph theory
  • Description modified (diff)
  • Keywords graph gsoc radius added
  • Type changed from PLEASE CHANGE to enhancement

New commits:

c822d97added the new certificate based radius algorithm
590904aMerge branch 'radius_certificate' into t/29431/certificate_based_radius_for_undirected_unweighed_graphs

comment:3 Changed 13 months ago by git

  • Commit changed from 590904a2561944a846218bb06aa0f551dbe261fd to 6dd478d063b40493ccc136831acfebfa1c92325c

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

6dd478dAdded commments, docs and modifications to handle cases like unconnected graph

comment:4 Changed 13 months ago by gh-ArchitWagle

  • Description modified (diff)
  • Status changed from new to needs_review

comment:5 Changed 13 months ago by gh-ArchitWagle

  • Description modified (diff)

comment:6 Changed 12 months ago by mkoeppe

  • Milestone changed from sage-9.1 to sage-9.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:7 Changed 11 months ago by gh-DaveWitteMorris

What is the relation with #29715? It looks to me like they should be combined somehow, or one should be closed as a duplicate.

comment:8 Changed 10 months ago by dcoudert

  • Milestone changed from sage-9.2 to sage-duplicate/invalid/wontfix

The algorithm has been implemented for both weighted and unweighted undirected graphs in #29715.

comment:9 Changed 8 months ago by dcoudert

  • Reviewers set to David Coudert
  • Status changed from needs_review to positive_review

This ticket can be closed.

comment:10 Changed 7 months ago by chapoton

  • Resolution set to duplicate
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.