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: sage-9.8
Component: graph theory Keywords: gsoc, diameter,
Cc: Merged in:
Authors: Madhav Wagle Reviewers:
Report Upstream: N/A Work issues:
Branch: u/gh-ArchitWagle/real_directed_diameter (Commits, GitHub, GitLab) Commit: b1bb1ac1046a85a4dc0280288c3e29d426f5619f
Dependencies: Stopgaps:

Status badges

Description (last modified by Madhav Wagle)

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: 56-67 https://doi.org/10.1007/978-3-319-20086-6_5

It is designed for directed real sparse graphs.

Change History (14)

comment:1 Changed 3 years ago by Madhav Wagle

Branch: u/gh-ArchitWagle/real_directed_diameter

comment:2 Changed 3 years ago by Madhav Wagle

Authors: Madhav Wagle
Commit: aceb725547c28de9969fe7684c192e1951760f1b
Component: PLEASE CHANGEgraph theory
Description: modified (diff)
Keywords: gsoc diameter added
Status: newneeds_review
Summary: real directed diameterImplemented the directed diameter algorithm for real graphs in https://doi.org/10.1007/978-3-319-20086-6_5
Type: PLEASE CHANGEenhancement

comment:3 Changed 3 years ago by Madhav Wagle

Summary: Implemented the directed diameter algorithm for real graphs in https://doi.org/10.1007/978-3-319-20086-6_5diameter for large directed real graphs

comment:4 Changed 3 years ago by David Coudert

Status: needs_reviewneeds_info

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

comment:5 in reply to:  4 Changed 3 years ago by Madhav Wagle

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/978-3-319-20086-6_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 1-2 lines of code to my current implementation to do that.

Last edited 3 years ago by Madhav Wagle (previous) (diff)

comment:6 Changed 3 years ago by Madhav Wagle

Status: needs_infoneeds_work

Few changes to be made

comment:7 Changed 3 years ago by git

Commit: aceb725547c28de9969fe7684c192e1951760f1bb1bb1ac1046a85a4dc0280288c3e29d426f5619f

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

b1bb1accorrected memset calls

comment:8 Changed 3 years ago by Matthias Köppe

Milestone: sage-9.1sage-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:9 Changed 2 years ago by Matthias Köppe

Milestone: sage-9.2sage-9.3

comment:10 Changed 22 months ago by Matthias Köppe

Milestone: sage-9.3sage-9.4

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

comment:11 Changed 17 months ago by Matthias Köppe

Milestone: sage-9.4sage-9.5

Setting a new milestone for this ticket based on a cursory review.

comment:12 Changed 12 months ago by Matthias Köppe

Milestone: sage-9.5sage-9.6

comment:13 Changed 8 months ago by Matthias Köppe

Milestone: sage-9.6sage-9.7

comment:14 Changed 3 months ago by Matthias Köppe

Milestone: sage-9.7sage-9.8
Note: See TracTickets for help on using tickets.