search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.43k stars 479 forks source link

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

Open dcoudert opened 4 years ago

dcoudert commented 4 years ago

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:

To do:

if by_weight and weight_function is None:
    def weight_function(e):
        return 1 if e[2] is None else e[2]

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

CC: @vipul79321

Component: graph theory

Keywords: gsoc2020

Author: Vipul Gupta, David Coudert

Issue created by migration from https://trac.sagemath.org/ticket/29657

dcoudert commented 4 years ago

Description changed:

--- 
+++ 
@@ -1,3 +1,9 @@
 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
+- 

+**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
+-
dcoudert commented 4 years ago

Description changed:

--- 
+++ 
@@ -2,7 +2,7 @@

 **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 unweighted undirected graphs.

 **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
DaveWitteMorris commented 4 years ago
comment:3

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.

dcoudert commented 4 years ago
comment:4

Replying to @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.

dcoudert commented 4 years ago

Description changed:

--- 
+++ 
@@ -3,6 +3,7 @@
 **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 unweighted undirected graphs.
+- #29734   fix an error in `shortest_path_lengths` method in `generic_graph.py`. The input graph should not be modified.

 **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
09ac5a22-6a87-4290-8c34-5c8dd760bfaf commented 4 years ago

Description changed:

--- 
+++ 
@@ -2,8 +2,9 @@

 **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 unweighted undirected graphs.
+- #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.

 **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
slel commented 4 years ago

Changed keywords from gsoc to gsoc20

dcoudert commented 4 years ago

Description changed:

--- 
+++ 
@@ -8,4 +8,4 @@

 **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.
09ac5a22-6a87-4290-8c34-5c8dd760bfaf commented 4 years ago

Description changed:

--- 
+++ 
@@ -8,4 +8,13 @@

 **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.
+- 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.
+
09ac5a22-6a87-4290-8c34-5c8dd760bfaf commented 4 years ago

Description changed:

--- 
+++ 
@@ -18,3 +18,6 @@

 - `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. 
+
+
dcoudert commented 4 years ago

Description changed:

--- 
+++ 
@@ -20,4 +20,11 @@

 - 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 ...**
+- #29422:  DiFUB algorithm for diameter of real (unweighed) directed graphs
+- #29346:  diameter for large directed real graphs - Algorithm by [Takuya Akiba, Yoichi Iwata, Yuki Kawata](https://doi.org/10.1007/978-3-319-20086-6_5)
+- #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.
dcoudert commented 4 years ago
comment:11

Tickets move to sage-duplicate/invalid/wontfix:

09ac5a22-6a87-4290-8c34-5c8dd760bfaf commented 4 years ago

Description changed:

--- 
+++ 
@@ -5,6 +5,7 @@
 - #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.

 **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
dcoudert commented 4 years ago

Description changed:

--- 
+++ 
@@ -6,6 +6,7 @@
 - #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

 **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
@@ -22,7 +23,6 @@
 - 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 ...**
-- #29422:  DiFUB algorithm for diameter of real (unweighed) directed graphs
 - #29346:  diameter for large directed real graphs - Algorithm by [Takuya Akiba, Yoichi Iwata, Yuki Kawata](https://doi.org/10.1007/978-3-319-20086-6_5)
 - #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 ?
dcoudert commented 4 years ago

Changed keywords from gsoc20 to gsoc2020

09ac5a22-6a87-4290-8c34-5c8dd760bfaf commented 4 years ago

Description changed:

--- 
+++ 
@@ -7,6 +7,7 @@
 - #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.

 **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
dcoudert commented 4 years ago

Description changed:

--- 
+++ 
@@ -1,13 +1,14 @@
 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.
+- #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

 **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
dcoudert commented 4 years ago

Description changed:

--- 
+++ 
@@ -9,6 +9,9 @@
 - #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
+

 **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
dcoudert commented 4 years ago

Description changed:

--- 
+++ 
@@ -11,6 +11,7 @@
 - #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**:
dcoudert commented 4 years ago

Description changed:

--- 
+++ 
@@ -35,3 +35,5 @@
 - #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
mkoeppe commented 3 years ago
comment:20

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