Opened 2 years ago

Last modified 4 weeks ago

#29657 new task

Meta ticket: graphs: improve distances, radius, diameter, eccentricities

Reported by: David Coudert Owned by:
Priority: major Milestone: sage-9.8
Component: graph theory Keywords: gsoc2020
Cc: vipul73921 Merged in:
Authors: Vipul Gupta, David Coudert Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by David Coudert)

The goal of this ticket is to organize and follow the changes and improvements done on methods for computing distances, diameter, radius and eccentricities.

Tickets:

  • #29660: Move radius, diameter and eccentricity methods from generic_graph.py to graph.py and digraph.py
  • #29715: Implement a fast algorithm by Dragan, Habib and Viennot for computing the radius of undirected graphs.
  • #29734: fix an error in shortest_path_lengths method in generic_graph.py. The input graph should not be modified.
  • #29744: Implement diameter computation method for undirected graphs given by Dragan, Habib and Viennot.
  • #27934: Implement all eccentricity method for undirected graphs given by Dragan, Habib and viennot.
  • #29422: DiFUB algorithm for diameter of real (unweighed) directed graphs
  • #30039: Weighted version of difub algorithm and 2Dsweep.
  • #30081: Cleaning and improving consistency in distances methods in graph module
  • #30247: memory efficient implementation of Wiener index
  • #30269: memory efficient implementation of distances distribution
  • #30405: fast (and memory efficient) implementation of antipodal_graph

To do:

  • avoid the use of "dict of dict of distances" inside method eccentricity, and avoid repeated conversions from one graph format to the other
  • Make usage of weights, weight functions and checks consistent. See for instance issue reported with boost in #29781. This can be done by introducing following lines of code in all distances related methods such shortest_path(s) , shortest_path_length(s), shortest_path_all_pairs
    if by_weight and weight_function is None:
        def weight_function(e):
            return 1 if e[2] is None else e[2]
    
  • shortest_paths method in boost_graph.pyx doesnt properly detect negative cycle using Bellman-Ford as algorithm. To solve, we can try to traverse distance dictionary and check if any value is negative. If negative then raise error, since distances can't be negative.
  • In #29744 and #29715, we have raised an error, if graph contains negative edge weights. Reason for this was Bellman-Ford is not able to properly detect negative cycle in undirected graphs.

Opened and inactive tickets, to be finalized or ...

  • #29346: diameter for large directed real graphs - Algorithm by Takuya Akiba, Yoichi Iwata, Yuki Kawata
  • #29309: duplicate of #29346 with a different implementation
  • #29336: proposal for making a code of Yuki Kawata to compute the diameter of directed graphs an external package. Same algorithm than #29346 ?
  • #27564: methods for computing the diameter of trees. Note that 2 BFS / Dijkstra calls are sufficient for that.
  • #27540: approximate algorithm for the diameter of undirected graphs.
  • #4854: add parameter as_edge to return a path as a list of labeled edges instead of a list of vertices

Change History (24)

comment:1 Changed 2 years ago by David Coudert

Description: modified (diff)

comment:2 Changed 2 years ago by David Coudert

Description: modified (diff)

comment:3 Changed 2 years ago by Dave Morris

I am glad to see this, because there are several open tickets on these topics. Other tickets I noticed that seem to fit the description and I hope will be included in the organization: #29431, #29422, #29346, #29336, #29309, #27934, #27564, #27540, #27506.

comment:4 in reply to:  3 Changed 2 years ago by David Coudert

Replying to gh-DaveWitteMorris:

I am glad to see this, because there are several open tickets on these topics. Other tickets I noticed that seem to fit the description and I hope will be included in the organization: #29431, #29422, #29346, #29336, #29309, #27934, #27564, #27540, #27506.

You are right, some of them must be finalized, some other closed.

For #27564, we may implement a Tree class like BipartiteGraph and to add it specific methods. This could help organizing methods.

comment:5 Changed 2 years ago by David Coudert

Description: modified (diff)

comment:6 Changed 2 years ago by vipul73921

Description: modified (diff)

comment:7 Changed 2 years ago by Samuel Lelièvre

Keywords: gsoc20 added; gsoc removed
Summary: Meta ticket: improvement of distances, radius, diameter and eccentricitiesMeta ticket: graphs: improve distances, radius, diameter, eccentricities

comment:8 Changed 2 years ago by David Coudert

Description: modified (diff)

comment:9 Changed 2 years ago by vipul73921

Description: modified (diff)
Type: taskdefect

comment:10 Changed 2 years ago by vipul73921

Description: modified (diff)
Type: defecttask

comment:11 Changed 2 years ago by David Coudert

Description: modified (diff)

Tickets move to sage-duplicate/invalid/wontfix:

comment:12 Changed 2 years ago by vipul73921

Description: modified (diff)

comment:13 Changed 2 years ago by David Coudert

Description: modified (diff)
Keywords: gsoc2020 added; gsoc20 removed

comment:14 Changed 2 years ago by vipul73921

Description: modified (diff)

comment:15 Changed 2 years ago by David Coudert

Description: modified (diff)

comment:16 Changed 2 years ago by David Coudert

Description: modified (diff)

comment:17 Changed 2 years ago by David Coudert

Description: modified (diff)

comment:18 Changed 2 years ago by David Coudert

Description: modified (diff)

comment:19 Changed 2 years ago by Matthias Köppe

Milestone: sage-9.2sage-9.3

comment:20 Changed 18 months ago by Matthias Köppe

Milestone: sage-9.3sage-9.4

Sage development has entered the release candidate phase for 9.3. Setting a new milestone for this ticket based on a cursory review.

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

Milestone: sage-9.4sage-9.5

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

Milestone: sage-9.5sage-9.6

comment:23 Changed 6 months ago by Matthias Köppe

Milestone: sage-9.6sage-9.7

comment:24 Changed 4 weeks ago by Matthias Köppe

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