Refactor shortest paths

a8f3419b-6383-42be-b93c-ecaa87929754 commented 9 years ago

At the moment, there are several methods that compute shortest paths. However, there is no standard for inputs and outputs of these methods:

some of them only work with unweighted graphs (distance_all_pairs(), distances_distribution(), eccentricity());
some of them use default_weight (shortest_path_all_pairs), while others do not check weights (shortest_paths)
some of them output paths, while others output predecessors (shortest_path_all_pairs).

The goal of this ticket is to standardize all these behaviors, and to make all routines work also with weighted graphs. The schema of the routine calls I would like to implement is attached (some calls are already present).

As a next step, we will include some Boost shortest path algorithms (Bellman-Ford, Johnson), with ticket !#18931.

CC: @nathanncohen @dcoudert

Component: graph theory

Keywords: Shortest path, eccentricity, Dijkstra

Author: Michele Borassi

Branch/Commit: 3f371f8

Reviewer: David Coudert

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

a8f3419b-6383-42be-b93c-ecaa87929754 commented 9 years ago

Attachment: Dependencies.png

Dependencies between shortest path routines

a8f3419b-6383-42be-b93c-ecaa87929754 commented 9 years ago

Changed keywords from none to Shortest path, eccentricity, Dijkstra

a8f3419b-6383-42be-b93c-ecaa87929754 commented 9 years ago

Description changed:

--- 
+++ 
@@ -1 +1,9 @@
+At the moment, there are several methods that compute shortest paths. However, there is no standard for inputs and outputs of these methods:

+* some of them only work with unweighted graphs (distance_all_pairs(), distances_distribution(), eccentricity());
+* some of them use default_weight (shortest_path_all_pairs), while others do not check weights (shortest_paths)
+* some of them output paths, while others output predecessors (shortest_path_all_pairs).
+
+The goal of this ticket is to standardize all these behaviors, and to make all routines work also with weighted graphs. The schema of the routine calls I would like to implement is attached (some calls are already present).
+
+As a next step, we will include some Boost shortest path algorithms (Bellman-Ford, Johnson), with ticket !#18931.

a8f3419b-6383-42be-b93c-ecaa87929754 commented 9 years ago

Author: Michele Borassi

dcoudert commented 9 years ago

comment:2

This is very challenging but definitely useful.

a8f3419b-6383-42be-b93c-ecaa87929754 commented 9 years ago

Branch: u/borassi/refactor_shortest_paths

a8f3419b-6383-42be-b93c-ecaa87929754 commented 9 years ago

comment:4

Hello!

This patch is clearly not the final version: however, before proceeding, I would like to know if you like how I defined the "standard" for shortest path functions. In particular, the new input variables are:

by_weight: if True, the graph is considered weighted (needed for backward compatibility);
algorithm: the algorithm (Dijkstra, BFS, etc);
weight_function: the function that provides weights (if None, the label is used).

The result of weight_function must always be convertible to a float, otherwise exceptions are raised.

You can see the result of the refactoring of the function shortest_paths, with comments. Any feedback will be appreciated!

Best,

Michele

PS: is it true that Dijkstra is not implemented in Sage, and we rely on NetworkX? In this case, I should also insert Boost Dijkstra for efficiency (but this will be done in a subsequent ticket).

New commits:

`dca3781`	`Temp`
`08e9daa`	`Temp`
`a8d2217`	`Modified inputs for shortest_paths routine`

a8f3419b-6383-42be-b93c-ecaa87929754 commented 9 years ago

Commit: a8d2217

dcoudert commented 9 years ago

comment:5

What's the proposed behavior when by_weight==False? Otherwise I agree with what you propose.

There is a bidirectional_dijkstra method in src/sage/graphs/base/c_graph.pyx. I don't know if it is used or not...

David.

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 9 years ago

comment:6

Hellooooooooooooooo Michele,

Several remarks on your branch:

``by_weight`` - if ``True``, the graph is considered weighted. Could you be more specific by saying that the edges are considered to be weighted?
Documentation of algorithm: could you document the default value and its behaviour?
This sounds like a dangerous behaviour: ``weight_function`` (function) - used only if ``by_weight==True``; If somebody calls g.shortest_paths(v,weight_function=my_function), we know for sure that (s)he wants the edges to be considered. Why shouldn't we define by_weight to True when weight_function is not None?
Documentation of weight_function: here is an attempt at making the following paragraph a bit shorter.
```
-a function that inputs an edge ``e`` and outputs its weight. An edge
-has the form ``(u,v,l)``, where ``u`` and ``v`` are vertices, ``l`` is
-a label (that can be of any kind). The ``weight_function`` can be used
-to transform the label into a weight. In particular:
+a function that takes a labelled edge `(u,v,l)` as input and returns
+its weight. If set to `None` when `by_weight=True`, the label `l` is
+used as the edge's weight.
```
The is_weighted flag is not used much in Sage, and I believe that it should be removed in the long term:
- You never know if it is about edge/vertex weights
- Setting a graph to be "weighted" does not check anything about the vality of weights
- You may want one function to consider the graph as weighted and not another one. Changing an attribute in between is not pratical, and is actually impossible for immutable graphs.
I do not think necessary to document which exceptions are raised when the input is bad, e.g. conversion to float. Do what you want.
You add many arguments to this function: they should be tested in the function's doctest.

Good evening,

Nathann

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 9 years ago

comment:7

There is a bidirectional_dijkstra method in src/sage/graphs/base/c_graph.pyx. I don't know if it is used or not...

It is used in GenericGraph.shortest_path.

Nathann

a8f3419b-6383-42be-b93c-ecaa87929754 commented 9 years ago

comment:8

Hi!

I tried to address your remarks, and I will upload the new version in a few moments. I have also started working on the other methods: still, the code is not clean, so I think you should only review the methods shortest_paths and check_weight_function (even if the whole code should be correct, because all tests are passed).

One question: since most of the arguments are the same for several routines, is there a way to avoid copy-paste in the documentation?

Thank you very much! Good evening,

Michele

What's the proposed behavior when by_weight==False?

Added to the documentation

There is a bidirectional_dijkstra method in src/sage/graphs/base/c_graph.pyx.

Yes, but there is no "standard" Dijkstra... Maybe, if I have time before the end of the project, I will add one.

!by_weight! - if !True!, the graph is considered weighted. Could you be more specific by saying that the edges are considered to be weighted?

Done

Documentation of algorithm: could you document the default value and its behaviour?

Done

This sounds like a dangerous behaviour: ``weight_function`` (function) - used only if ``by_weight==True``; If somebody calls g.shortest_paths(v,weight_function=my_function), we know for sure that (s)he wants the edges to be considered. Why shouldn't we define by_weight to True when weight_function is not None?

Done

Documentation of weight_function: here is an attempt at making the following paragraph a bit shorter.

-a function that inputs an edge e and outputs its weight. An edge
-has the form (u,v,l), where u and v are vertices, l is
-a label (that can be of any kind). The weight_function can be used
-to transform the label into a weight. In particular:
+a function that takes a labelled edge `(u,v,l)` as input and returns
+its weight. If set to `None` when `by_weight=True`, the label `l` is
+used as the edge's weight.

I have modified heavily the paragraph, taking inspiration from your proposal.

The is_weighted flag is not used much in Sage, and I believe that it should be removed in the long term:

You never know if it is about edge/vertex weights

Setting a graph to be "weighted" does not check anything about the vality of weights

You may want one function to consider the graph as weighted and not another one. Changing an attribute in between is not pratical, and is actually impossible for immutable graphs.

I removed all references to is_weighted: now I just check that the weight function outputs numbers

I do not think necessary to document which exceptions are raised when the input is bad, e.g. conversion to float. Do what you want.

Done!

You add many arguments to this function: they should be tested in the function's doctest.

Added some doctests.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

dca691b Good quality shortest_paths, implemented other routines

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from a8d2217 to dca691b

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 9 years ago

comment:10

Hello,

I think you should only review the methods shortest_paths and check_weight_function

The second function should be a hidden one, i.e. _check_weight_function. It is only a checking routine that we need internally. I am always wary of these routines by the way, especially when they apply to linear-time algorithms....

Anyawy. You should probably replace .edges() by .edge_iterator() in there, for otherwise the first line of the loop is actually as time/space consuming as a full graph copy (even worse actually, as it is pure python stuff).

One question: since most of the arguments are the same for several routines, is there a way to avoid copy-paste in the documentation?

No magical way that I know. It's either this or "see the doc of for more inforamtion". Or you can have a **kwds instead of copy/pasting the arguments in the function's prototype and foward them all to the subcall, saying that "all arguments of function (see its doc) are accepted". No magic, really.

If ``None`` and ``by_weight`` is ``True``, we output ``l`` by default. We output 'l'? What about 'we use the edge's label as a weight'?

Nathann

dcoudert commented 9 years ago

comment:11

Hello,

In method check_weight_function

Checks that an edge weight function outputs only numbers. -> Check that an edge weight function outputs only numbers.
The title of the example A wrong weight function:: must be changed. The weight function is correct but not the edge label.
for e in self.edges(): -> for e in self.edge_iterator(): ?

In method shortest_paths

If the weight function is wrong:: same as above

Also I'm wondering if we may have conflicts with tickets #18868 about memory allocation and #18864 on eccentricity

David.

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 9 years ago

comment:12

Also I'm wondering if we may have conflicts with tickets #18868 about memory allocation and #18864 on eccentricity

There was. I just fixed it.

Nathann

dcoudert commented 9 years ago

comment:13

I'm not sure I understand what you have done...

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 9 years ago

comment:14

I made #18864 a dependency of #18868. And in #18868 I handled the conflict.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

`80cb899`	`trac #18864: correct version`
`ce9d265`	`trac #18864: return Sage integers`
`a1b36da`	`trac #18864: Merged with 6.8.rc1`
`2723175`	`trac #18868: a MemoryAllocator object for easier Cython memory management`
`bf39672`	`trac #18868: back to calloc`
`9597eec`	`trac #18868: Changes to MemoryAllocator`
`f514301`	`Optimize MemoryAllocator and add allocarray()`
`39f8839`	`Fix exception handling`
`0304d9f`	`trac #18868: Merged with #18864`
`d4ceebf`	`Merged with #18868.`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from dca691b to d4ceebf

a8f3419b-6383-42be-b93c-ecaa87929754 commented 9 years ago

comment:16

Helloooooooo!

I have applied all your suggestions, and I have merged this ticket with !#18868 in order to avoid conflicts.

Soon I will modify the other methods, and finally ask for a review!

See you, Michele

dcoudert commented 9 years ago

comment:17

great !

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

`545b7bb`	`Temporary`
`cd88904`	`Temp`
`38c10d4`	`Problem with documentation`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from d4ceebf to 38c10d4

a8f3419b-6383-42be-b93c-ecaa87929754 commented 9 years ago

comment:19

Hello!

I have a problem building the documentation in this branch, and I really have no idea what's going on (I lost the whole morning trying to fix it, with no success). Could you help me, at least by telling me what does the following log mean? The code is in this ticket...

Error building the documentation.
Traceback (most recent call last):
  File "/home/michele/Programmi/sage/src/doc/common/builder.py", line 1626, in <module>
    getattr(get_builder(name), type)()
  File "/home/michele/Programmi/sage/src/doc/common/builder.py", line 292, in _wrapper
    getattr(get_builder(document), 'inventory')(*args, **kwds)
  File "/home/michele/Programmi/sage/src/doc/common/builder.py", line 503, in _wrapper
    x.get(99999)
  File "/home/michele/Programmi/sage/local/lib/python/multiprocessing/pool.py", line 558, in get
    raise self._value
OSError: [graphs   ] /home/michele/Programmi/sage/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py:docstring of sage.graphs.generic_graph.graph_isom_equivalent_non_edge_labeled_graph:25: WARNING: Explicit markup ends without a blank line; unexpected unindent.

Makefile:742: recipe for target 'doc-html' failed
make[2]: *** [doc-html] Error 1
make[2]: Leaving directory '/home/michele/Programmi/sage/build/make'
Makefile:563: recipe for target 'all' failed
make[1]: *** [all] Error 2
make[1]: Leaving directory '/home/michele/Programmi/sage/build/make'

Thank you very much!

Michele

dcoudert commented 9 years ago

comment:20

After performing the following changes, I'm able to compile the doc.

In _path_length, change

       WARNING: if the graph is unweighted, the algorithm does not check that
       the path exists. Moreover, also if the weight_function does not return a
       number, an error is raised.

To

        .. WARNING::

            If the graph is unweighted, the algorithm does not check that the
            path exists. Moreover, also if the weight_function does not return a
            number, an error is raised.

The WARNING: should declare a block, so may be you should insert space/blank line (not sure).

In wiener_index, change

       .. [KRG96b] S. Klavzar, A. Rajapakse, and I. Gutman. The Szeged and the
       Wiener index of graphs. *Applied Mathematics Letters*, 9(5):45--49,
       1996.

to

       .. [KRG96b] S. Klavzar, A. Rajapakse, and I. Gutman. The Szeged and the
         Wiener index of graphs. *Applied Mathematics Letters*, 9(5):45--49,
         1996.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 38c10d4 to 760ea87

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

`3612655`	`Temp`
`760ea87`	`Refactored shortest paths (first working draft)`

a8f3419b-6383-42be-b93c-ecaa87929754 commented 9 years ago

comment:22

Finally, I have a version of the refactoring that might be reviewed. Hope you like it!

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 760ea87 to 5c78561

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

`793dc12`	`Merged with 6.9.beta0`
`5c78561`	`Small correction in doctest`

dcoudert commented 9 years ago

comment:24

Hello,

The patch passes all long tests, but I have a problem when building the documentation (duplicate citation KRG96b). I don't know which is the best solution. You could eventually point to the other module documentation instead of repeating citation.

[graphs   ] /Users/dcoudert/sage/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py:docstring of sage.graphs.generic_graph.GenericGraph.wiener_index:72: WARNING: duplicate citation KRG96b, other instance in /Users/dcoudert/sage/src/doc/en/reference/graphs/sage/graphs/distances_all_pairs.rst
Error building the documentation.
Traceback (most recent call last):
  File "/Users/dcoudert/sage/src/doc/common/builder.py", line 1626, in <module>
    getattr(get_builder(name), type)()
  File "/Users/dcoudert/sage/src/doc/common/builder.py", line 292, in _wrapper
    getattr(get_builder(document), 'inventory')(*args, **kwds)
  File "/Users/dcoudert/sage/src/doc/common/builder.py", line 503, in _wrapper
    x.get(99999)
  File "/Users/dcoudert/sage/local/lib/python/multiprocessing/pool.py", line 558, in get
    raise self._value
OSError: [graphs   ] /Users/dcoudert/sage/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py:docstring of sage.graphs.generic_graph.GenericGraph.wiener_index:72: WARNING: duplicate citation KRG96b, other instance in /Users/dcoudert/sage/src/doc/en/reference/graphs/sage/graphs/distances_all_pairs.rst

make[1]: *** [doc-html] Error 1

David.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

3f371f8 Removed duplicate reference

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 5c78561 to 3f371f8

a8f3419b-6383-42be-b93c-ecaa87929754 commented 9 years ago

comment:26

I removed the duplicate reference: now the citation refers to the other module.

dcoudert commented 9 years ago

comment:27

Hello,

now the doc build properly and it looks fine. For me this ticket is now good to go.

Best, David.

dcoudert commented 9 years ago

Reviewer: David Coudert

vbraun commented 9 years ago

Changed branch from u/borassi/refactor_shortest_paths to 3f371f8

sagemath / sage

Refactor shortest paths #18938