Issue 18938: Refactor shortest paths

archive/issues_018701.json:

{
    "assignees": [],
    "body": "<div id=\"comment:0\"></div>\n\nAt the moment, there are several methods that compute shortest paths. However, there is no standard for inputs and outputs of these methods:\n\n* some of them only work with unweighted graphs (distance_all_pairs(), distances_distribution(), eccentricity());\n* some of them use default_weight (shortest_path_all_pairs), while others do not check weights (shortest_paths)\n* some of them output paths, while others output predecessors (shortest_path_all_pairs).\n\nThe 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).\n\nAs a next step, we will include some Boost shortest path algorithms (Bellman-Ford, Johnson), with ticket !#18931.\n\nCC:  @nathanncohen @dcoudert\n\nComponent: **graph theory**\n\nKeywords: **Shortest path, eccentricity, Dijkstra**\n\nAuthor: **Michele Borassi**\n\nBranch/Commit: **[`3f371f8`](https://github.com/sagemath/sagetrac-mirror/commit/3f371f844ecd2667b268d74fa258787f3c6da1c4)**\n\nReviewer: **David Coudert**\n\n_Issue created by migration from https://trac.sagemath.org/ticket/18938_\n\n",
    "closed_at": "2015-08-05T10:51:44Z",
    "created_at": "2015-07-22T13:27:18Z",
    "labels": [
        "https://github.com/sagemath/sage/labels/c%3A%20graph%20theory",
        "https://github.com/sagemath/sage/labels/p%3A%20major%20/%203",
        "https://github.com/sagemath/sage/labels/bug"
    ],
    "milestone": "https://github.com/sagemath/sage/milestones/sage-6.9",
    "reactions": [],
    "repository": "https://github.com/sagemath/sage",
    "title": "Refactor shortest paths",
    "type": "issue",
    "updated_at": "2015-08-05T10:51:44Z",
    "url": "https://github.com/sagemath/sage/issues/18938",
    "user": "https://github.com/sagetrac-borassi"
}

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

archive/issue_events_266443.json:

{
    "actor": "https://github.com/sagetrac-borassi",
    "created_at": "2015-07-22T13:27:18Z",
    "event": "milestoned",
    "issue": "https://github.com/sagemath/sage/issues/18938",
    "milestone_number": null,
    "milestone_title": "sage-6.8",
    "type": "issue_event",
    "url": "https://github.com/sagemath/sage/issues/18938#event-266443"
}

archive/issue_events_266444.json:

{
    "actor": "https://github.com/sagetrac-borassi",
    "created_at": "2015-07-22T13:27:18Z",
    "event": "labeled",
    "issue": "https://github.com/sagemath/sage/issues/18938",
    "label": "https://github.com/sagemath/sage/labels/p%3A%20major%20/%203",
    "label_color": "ffbb00",
    "label_name": "p: major / 3",
    "label_text_color": "ffffff",
    "type": "issue_event",
    "url": "https://github.com/sagemath/sage/issues/18938#event-266444"
}

archive/issue_comments_265825.json:

{
    "body": "Attachment: **[Dependencies.png](https://github.com/sagemath/sage/files/ticket18938/Dependencies.png)**\n\nDependencies between shortest path routines",
    "created_at": "2015-07-22T13:52:57Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/18938",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/18938#issuecomment-265825",
    "user": "https://github.com/sagetrac-borassi"
}

Attachment: Dependencies.png

Dependencies between shortest path routines

archive/issue_events_266445.json:

{
    "actor": "https://github.com/sagetrac-borassi",
    "created_at": "2015-07-22T13:54:27Z",
    "event": "labeled",
    "issue": "https://github.com/sagemath/sage/issues/18938",
    "label": "https://github.com/sagemath/sage/labels/c%3A%20graph%20theory",
    "label_color": "0000ff",
    "label_name": "c: graph theory",
    "label_text_color": "ffffff",
    "type": "issue_event",
    "url": "https://github.com/sagemath/sage/issues/18938#event-266445"
}

archive/issue_events_266446.json:

{
    "actor": "https://github.com/sagetrac-borassi",
    "created_at": "2015-07-22T13:54:27Z",
    "event": "labeled",
    "issue": "https://github.com/sagemath/sage/issues/18938",
    "label": "https://github.com/sagemath/sage/labels/bug",
    "label_color": "d73a4a",
    "label_name": "bug",
    "label_text_color": "ffffff",
    "type": "issue_event",
    "url": "https://github.com/sagemath/sage/issues/18938#event-266446"
}

archive/issue_comments_265826.json:

{
    "body": "Changed keywords from none to **Shortest path, eccentricity, Dijkstra**",
    "created_at": "2015-07-22T13:54:27Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/18938",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/18938#issuecomment-265826",
    "user": "https://github.com/sagetrac-borassi"
}

Changed keywords from none to Shortest path, eccentricity, Dijkstra

archive/issue_comments_265827.json:

{
    "body": "Description changed:\n``````diff\n--- \n+++ \n@@ -1 +1,9 @@\n+At the moment, there are several methods that compute shortest paths. However, there is no standard for inputs and outputs of these methods:\n \n+* some of them only work with unweighted graphs (distance_all_pairs(), distances_distribution(), eccentricity());\n+* some of them use default_weight (shortest_path_all_pairs), while others do not check weights (shortest_paths)\n+* some of them output paths, while others output predecessors (shortest_path_all_pairs).\n+\n+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).\n+\n+As a next step, we will include some Boost shortest path algorithms (Bellman-Ford, Johnson), with ticket !#18931.\n``````\n",
    "created_at": "2015-07-22T13:54:27Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/18938",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/18938#issuecomment-265827",
    "user": "https://github.com/sagetrac-borassi"
}

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.

archive/issue_comments_265828.json:

{
    "body": "Author: **Michele Borassi**",
    "created_at": "2015-07-22T13:54:27Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/18938",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/18938#issuecomment-265828",
    "user": "https://github.com/sagetrac-borassi"
}

Author: Michele Borassi

archive/issue_comments_265829.json:

{
    "body": "<div id=\"comment:2\" align=\"right\">comment:2</div>\n\nThis is very challenging but definitely useful.",
    "created_at": "2015-07-22T15:53:26Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/18938",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/18938#issuecomment-265829",
    "user": "https://github.com/dcoudert"
}

comment:2

This is very challenging but definitely useful.

archive/issue_comments_265830.json:

{
    "body": "Branch: **[u/borassi/refactor_shortest_paths](https://github.com/sagemath/sagetrac-mirror/tree/u/borassi/refactor_shortest_paths)**",
    "created_at": "2015-07-22T16:02:50Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/18938",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/18938#issuecomment-265830",
    "user": "https://github.com/sagetrac-borassi"
}

Branch: u/borassi/refactor_shortest_paths

archive/issue_comments_265831.json:

{
    "body": "<div id=\"comment:4\" align=\"right\">comment:4</div>\n\nHello!\n\nThis 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:\n\n* by_weight: if True, the graph is considered weighted (needed for backward compatibility);\n* algorithm: the algorithm (Dijkstra, BFS, etc);\n* weight_function: the function that provides weights (if None, the label is used).\n\nThe result of weight_function must always be convertible to a float, otherwise exceptions are raised.\n\nYou can see the result of the refactoring of the function shortest_paths, with comments. Any feedback will be appreciated!\n\nBest,\n\nMichele\n\nPS: 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).\n\n---\nNew commits:\n<table><tr><td><a href=\"https://github.com/sagemath/sagetrac-mirror/commit/dca3781dfa4efb1f3d6dbb8a6fcbec62acc9b614\"><code>dca3781</code></a></td><td><code>Temp</code></td></tr><tr><td><a href=\"https://github.com/sagemath/sagetrac-mirror/commit/08e9daa22c474c9afa4e7a6ebf03da3a10cb1ad7\"><code>08e9daa</code></a></td><td><code>Temp</code></td></tr><tr><td><a href=\"https://github.com/sagemath/sagetrac-mirror/commit/a8d22178cff80ffe9da8d0b46c15ec30fe2d3a87\"><code>a8d2217</code></a></td><td><code>Modified inputs for shortest_paths routine</code></td></tr></table>\n",
    "created_at": "2015-07-22T16:08:24Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/18938",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/18938#issuecomment-265831",
    "user": "https://github.com/sagetrac-borassi"
}

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`

archive/issue_comments_265832.json:

{
    "body": "Commit: **[`a8d2217`](https://github.com/sagemath/sagetrac-mirror/commit/a8d22178cff80ffe9da8d0b46c15ec30fe2d3a87)**",
    "created_at": "2015-07-22T16:08:24Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/18938",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/18938#issuecomment-265832",
    "user": "https://github.com/sagetrac-borassi"
}

Commit: a8d2217

archive/issue_comments_265833.json:

{
    "body": "<div id=\"comment:5\" align=\"right\">comment:5</div>\n\nWhat's the proposed behavior when `by_weight==False`?\nOtherwise I agree with what you propose.\n\n\n\nThere is a `bidirectional_dijkstra` method in `src/sage/graphs/base/c_graph.pyx`. I don't know if it is used or not...\n\nDavid.",
    "created_at": "2015-07-23T16:24:32Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/18938",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/18938#issuecomment-265833",
    "user": "https://github.com/dcoudert"
}

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.

archive/issue_comments_265834.json:

{
    "body": "<div id=\"comment:6\" align=\"right\">comment:6</div>\n\nHellooooooooooooooo Michele,\n\nSeveral remarks on your branch:\n\n- <code>\\`\\`by_weight\\`\\` - if \\`\\`True\\`\\`, the graph is considered weighted.</code> Could you\n  be more specific by saying that the *edges* are considered to be weighted?\n\n- Documentation of `algorithm`: could you document the default value and its\n  behaviour?\n\n- This sounds like a dangerous behaviour:\n  <code>\\`\\`weight_function\\`\\` (function) - used only if \\`\\`by_weight==True\\`\\`;</code>\n  If somebody calls `g.shortest_paths(v,weight_function=my_function)`, we know\n  for sure that (s)he wants the edges to be considered. Why shouldn't we define\n  `by_weight` to `True` when `weight_function is not None`?\n\n- Documentation of `weight_function`: here is an attempt at making the following\n  paragraph a bit shorter.\n\n  ```diff\n  -a function that inputs an edge ``e`` and outputs its weight. An edge\n  -has the form ``(u,v,l)``, where ``u`` and ``v`` are vertices, ``l`` is\n  -a label (that can be of any kind). The ``weight_function`` can be used\n  -to transform the label into a weight. In particular:\n  +a function that takes a labelled edge `(u,v,l)` as input and returns\n  +its weight. If set to `None` when `by_weight=True`, the label `l` is\n  +used as the edge's weight.\n  ```\n  The `is_weighted` flag is not used much in Sage, and I believe that it should\n  be removed in the long term:\n  - You never know if it is about edge/vertex weights\n  - Setting a graph to be \"weighted\" does not check anything about the vality of\n    weights\n  - You may want one function to consider the graph as weighted and not another\n    one. Changing an attribute in between is not pratical, and is actually\n    impossible for immutable graphs.\n\n- I do not think necessary to document which exceptions are raised when the\n  input is bad, e.g. conversion to float. Do what you want.\n\n- You add many arguments to this function: they should be tested in the\n  function's doctest.\n\nGood evening,\n\nNathann",
    "created_at": "2015-07-23T18:05:15Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/18938",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/18938#issuecomment-265834",
    "user": "https://github.com/nathanncohen"
}

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

archive/issue_comments_265835.json:

{
    "body": "<div id=\"comment:7\" align=\"right\">comment:7</div>\n\n> There is a `bidirectional_dijkstra` method in `src/sage/graphs/base/c_graph.pyx`. I don't know if it is used or not...\n\nIt is used in `GenericGraph.shortest_path`.\n\nNathann",
    "created_at": "2015-07-23T18:05:59Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/18938",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/18938#issuecomment-265835",
    "user": "https://github.com/nathanncohen"
}

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

archive/issue_comments_265836.json:

{
    "body": "<div id=\"comment:8\" align=\"right\">comment:8</div>\n\nHi!\n\nI 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).\n\nOne question: since most of the arguments are the same for several routines, is there a way to avoid copy-paste in the documentation?\n\nThank you very much! Good evening,\n\nMichele\n\n> What's the proposed behavior when by_weight==False?\n\nAdded to the documentation\n\n> There is a bidirectional_dijkstra method in src/sage/graphs/base/c_graph.pyx.\n\nYes, but there is no \"standard\" Dijkstra... Maybe, if I have time before the end of the project, I will add one.\n\n> - !``by_weight!`` - if !``True!``, the graph is considered weighted. Could you be more specific by saying that the *edges* are considered to be weighted?\n\nDone\n\n> - Documentation of `algorithm`: could you document the default value and its\n> behaviour?\n\nDone\n\n> - This sounds like a dangerous behaviour:\n> <code>\\`\\`weight_function\\`\\` (function) - used only if \\`\\`by_weight==True\\`\\`;</code>\n> If somebody calls `g.shortest_paths(v,weight_function=my_function)`, we know\n> for sure that (s)he wants the edges to be considered. Why shouldn't we define\n> `by_weight` to `True` when `weight_function is not None`?\n\nDone\n\n> - Documentation of `weight_function`: here is an attempt at making the following\n> paragraph a bit shorter.\n> \n> ```diff\n> -a function that inputs an edge e and outputs its weight. An edge\n> -has the form (u,v,l), where u and v are vertices, l is\n> -a label (that can be of any kind). The weight_function can be used\n> -to transform the label into a weight. In particular:\n> +a function that takes a labelled edge `(u,v,l)` as input and returns\n> +its weight. If set to `None` when `by_weight=True`, the label `l` is\n> +used as the edge's weight.\n> ```\n\nI have modified heavily the paragraph, taking inspiration from your proposal.\n\n> The `is_weighted` flag is not used much in Sage, and I believe that it should\n> be removed in the long term:\n> - You never know if it is about edge/vertex weights\n> - Setting a graph to be \"weighted\" does not check anything about the vality of\n> weights\n> - You may want one function to consider the graph as weighted and not another\n> one. Changing an attribute in between is not pratical, and is actually\n> impossible for immutable graphs.\n\nI removed all references to is_weighted: now I just check that the weight function outputs numbers\n\n> - I do not think necessary to document which exceptions are raised when the\n> input is bad, e.g. conversion to float. Do what you want.\n\nDone!\n\n> - You add many arguments to this function: they should be tested in the\n> function's doctest.\n\nAdded some doctests.",
    "created_at": "2015-07-23T20:31:38Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/18938",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/18938#issuecomment-265836",
    "user": "https://github.com/sagetrac-borassi"
}

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.

archive/issue_comments_265837.json:

{
    "body": "<div id=\"comment:9\"></div>\n\nBranch pushed to git repo; I updated commit sha1. New commits:\n<table><tr><td><a href=\"https://github.com/sagemath/sagetrac-mirror/commit/dca691b5114e24d8a157a8b0bf7f92b2275a87e0\"><code>dca691b</code></a></td><td><code>Good quality shortest_paths, implemented other routines</code></td></tr></table>\n",
    "created_at": "2015-07-23T20:59:48Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/18938",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/18938#issuecomment-265837",
    "user": "https://github.com/sagetrac-git"
}

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

dca691b Good quality shortest_paths, implemented other routines

archive/issue_comments_265838.json:

{
    "body": "Changed commit from **[`a8d2217`](https://github.com/sagemath/sagetrac-mirror/commit/a8d22178cff80ffe9da8d0b46c15ec30fe2d3a87)** to **[`dca691b`](https://github.com/sagemath/sagetrac-mirror/commit/dca691b5114e24d8a157a8b0bf7f92b2275a87e0)**",
    "created_at": "2015-07-23T20:59:48Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/18938",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/18938#issuecomment-265838",
    "user": "https://github.com/sagetrac-git"
}

Changed commit from a8d2217 to dca691b

archive/issue_comments_265839.json:

{
    "body": "<div id=\"comment:10\" align=\"right\">comment:10</div>\n\nHello,\n\n> I think you should only review the methods `shortest_paths` and `check_weight_function`\n\nThe 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....\n\nAnyawy. 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).\n\n> One question: since most of the arguments are the same for several routines, is there a way to avoid copy-paste in the documentation?\n\nNo magical way that I know. It's either this or \"see the doc of <X> 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 <X> (see its doc) are accepted\". No magic, really.\n\n- <code>If \\`\\`None\\`\\` and \\`\\`by_weight\\`\\` is \\`\\`True\\`\\`, we output \\`\\`l\\`\\` by default.</code> We output 'l'? What about 'we use the edge's label as a weight'?\n\nNathann",
    "created_at": "2015-07-24T09:30:16Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/18938",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/18938#issuecomment-265839",
    "user": "https://github.com/nathanncohen"
}

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

archive/issue_comments_265840.json:

{
    "body": "<div id=\"comment:11\" align=\"right\">comment:11</div>\n\nHello,\n\nIn method `check_weight_function`\n- `Checks that an edge weight function outputs only numbers.` -> `Check that an edge weight function outputs only numbers.`\n- The title of the example `A wrong weight function::` must be changed. The weight function is correct but not the edge label.\n- `for e in self.edges():` -> `for e in self.edge_iterator():` ?\n\nIn method `shortest_paths`\n- `If the weight function is wrong::` same as above\n\n\nAlso I'm wondering if we may have conflicts with tickets #18868 about memory allocation and #18864 on eccentricity\n\nDavid.",
    "created_at": "2015-07-24T09:33:42Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/18938",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/18938#issuecomment-265840",
    "user": "https://github.com/dcoudert"
}

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.

archive/issue_comments_265841.json:

{
    "body": "<div id=\"comment:12\" align=\"right\">comment:12</div>\n\n> Also I'm wondering if we may have conflicts with tickets #18868 about memory allocation and #18864 on eccentricity\n\nThere was. I just fixed it.\n\nNathann",
    "created_at": "2015-07-24T09:40:46Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/18938",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/18938#issuecomment-265841",
    "user": "https://github.com/nathanncohen"
}

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

archive/issue_comments_265842.json:

{
    "body": "<div id=\"comment:13\" align=\"right\">comment:13</div>\n\nI'm not sure I understand what you have done...",
    "created_at": "2015-07-24T16:57:35Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/18938",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/18938#issuecomment-265842",
    "user": "https://github.com/dcoudert"
}

comment:13

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

archive/issue_comments_265843.json:

{
    "body": "<div id=\"comment:14\" align=\"right\">comment:14</div>\n\nI made #18864 a dependency of #18868. And in #18868 I handled the conflict.",
    "created_at": "2015-07-24T17:18:20Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/18938",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/18938#issuecomment-265843",
    "user": "https://github.com/nathanncohen"
}

comment:14

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

archive/issue_comments_265844.json:

{
    "body": "<div id=\"comment:15\"></div>\n\nBranch pushed to git repo; I updated commit sha1. Last 10 new commits:\n<table><tr><td><a href=\"https://github.com/sagemath/sagetrac-mirror/commit/80cb89935d8eb8288d6659d7c73d8c05ee1c9411\"><code>80cb899</code></a></td><td><code>trac #18864: correct version</code></td></tr><tr><td><a href=\"https://github.com/sagemath/sagetrac-mirror/commit/ce9d26556e5b1a69002e1a5165933e51ddfc7c05\"><code>ce9d265</code></a></td><td><code>trac #18864: return Sage integers</code></td></tr><tr><td><a href=\"https://github.com/sagemath/sagetrac-mirror/commit/a1b36dafbf11d7f72f8568c51af6fba7003ca096\"><code>a1b36da</code></a></td><td><code>trac #18864: Merged with 6.8.rc1</code></td></tr><tr><td><a href=\"https://github.com/sagemath/sagetrac-mirror/commit/27231756748e4743df056783f524c66099189ccf\"><code>2723175</code></a></td><td><code>trac #18868: a MemoryAllocator object for easier Cython memory management</code></td></tr><tr><td><a href=\"https://github.com/sagemath/sagetrac-mirror/commit/bf39672b9547f32ec01e261e7541f22429bee5b7\"><code>bf39672</code></a></td><td><code>trac #18868: back to calloc</code></td></tr><tr><td><a href=\"https://github.com/sagemath/sagetrac-mirror/commit/9597eec5a42d72f66d56245f7312af3d69bbbf13\"><code>9597eec</code></a></td><td><code>trac #18868: Changes to MemoryAllocator</code></td></tr><tr><td><a href=\"https://github.com/sagemath/sagetrac-mirror/commit/f514301ecf95d895d4321c7782d888d4cd27355f\"><code>f514301</code></a></td><td><code>Optimize MemoryAllocator and add allocarray()</code></td></tr><tr><td><a href=\"https://github.com/sagemath/sagetrac-mirror/commit/39f88395bcef3aa972d48b31d4561c3c8a284d37\"><code>39f8839</code></a></td><td><code>Fix exception handling</code></td></tr><tr><td><a href=\"https://github.com/sagemath/sagetrac-mirror/commit/0304d9f21aa483f8b37bc6959e1a7490cd23ddb5\"><code>0304d9f</code></a></td><td><code>trac #18868: Merged with #18864</code></td></tr><tr><td><a href=\"https://github.com/sagemath/sagetrac-mirror/commit/d4ceebf070104da6401a5331242a698df1c727b2\"><code>d4ceebf</code></a></td><td><code>Merged with #18868.</code></td></tr></table>\n",
    "created_at": "2015-07-27T10:20:39Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/18938",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/18938#issuecomment-265844",
    "user": "https://github.com/sagetrac-git"
}

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.`

archive/issue_comments_265845.json:

{
    "body": "Changed commit from **[`dca691b`](https://github.com/sagemath/sagetrac-mirror/commit/dca691b5114e24d8a157a8b0bf7f92b2275a87e0)** to **[`d4ceebf`](https://github.com/sagemath/sagetrac-mirror/commit/d4ceebf070104da6401a5331242a698df1c727b2)**",
    "created_at": "2015-07-27T10:20:39Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/18938",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/18938#issuecomment-265845",
    "user": "https://github.com/sagetrac-git"
}

Changed commit from dca691b to d4ceebf

archive/issue_comments_265846.json:

{
    "body": "<div id=\"comment:16\" align=\"right\">comment:16</div>\n\nHelloooooooo!\n\nI have applied all your suggestions, and I have merged this ticket with !#18868 in order to avoid conflicts.\n\nSoon I will modify the other methods, and finally ask for a review!\n\nSee you,\nMichele",
    "created_at": "2015-07-27T10:23:36Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/18938",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/18938#issuecomment-265846",
    "user": "https://github.com/sagetrac-borassi"
}

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

archive/issue_comments_265847.json:

{
    "body": "<div id=\"comment:17\" align=\"right\">comment:17</div>\n\ngreat !",
    "created_at": "2015-07-27T18:15:21Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/18938",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/18938#issuecomment-265847",
    "user": "https://github.com/dcoudert"
}

comment:17

great !

archive/issue_comments_265848.json:

{
    "body": "<div id=\"comment:18\"></div>\n\nBranch pushed to git repo; I updated commit sha1. New commits:\n<table><tr><td><a href=\"https://github.com/sagemath/sagetrac-mirror/commit/545b7bbc4cf03103d396184c59cfd6836585df70\"><code>545b7bb</code></a></td><td><code>Temporary</code></td></tr><tr><td><a href=\"https://github.com/sagemath/sagetrac-mirror/commit/cd889046c58144962a368019d8eaab1bafd4981a\"><code>cd88904</code></a></td><td><code>Temp</code></td></tr><tr><td><a href=\"https://github.com/sagemath/sagetrac-mirror/commit/38c10d43143d985adbb57fcb514f3483ee30941d\"><code>38c10d4</code></a></td><td><code>Problem with documentation</code></td></tr></table>\n",
    "created_at": "2015-07-28T10:27:19Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/18938",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/18938#issuecomment-265848",
    "user": "https://github.com/sagetrac-git"
}

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

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

archive/issue_comments_265849.json:

{
    "body": "Changed commit from **[`d4ceebf`](https://github.com/sagemath/sagetrac-mirror/commit/d4ceebf070104da6401a5331242a698df1c727b2)** to **[`38c10d4`](https://github.com/sagemath/sagetrac-mirror/commit/38c10d43143d985adbb57fcb514f3483ee30941d)**",
    "created_at": "2015-07-28T10:27:19Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/18938",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/18938#issuecomment-265849",
    "user": "https://github.com/sagetrac-git"
}

Changed commit from d4ceebf to 38c10d4

archive/issue_comments_265850.json:

{
    "body": "<div id=\"comment:19\" align=\"right\">comment:19</div>\n\nHello!\n\nI 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...\n\n```\nError building the documentation.\nTraceback (most recent call last):\n\u00a0 File \"/home/michele/Programmi/sage/src/doc/common/builder.py\", line 1626, in <module>\n\u00a0\u00a0\u00a0 getattr(get_builder(name), type)()\n\u00a0 File \"/home/michele/Programmi/sage/src/doc/common/builder.py\", line 292, in _wrapper\n\u00a0\u00a0\u00a0 getattr(get_builder(document), 'inventory')(*args, **kwds)\n\u00a0 File \"/home/michele/Programmi/sage/src/doc/common/builder.py\", line 503, in _wrapper\n\u00a0\u00a0\u00a0 x.get(99999)\n\u00a0 File \"/home/michele/Programmi/sage/local/lib/python/multiprocessing/pool.py\", line 558, in get\n\u00a0\u00a0\u00a0 raise self._value\nOSError: [graphs\u00a0\u00a0 ] /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.\n\nMakefile:742: recipe for target 'doc-html' failed\nmake[2]: *** [doc-html] Error 1\nmake[2]: Leaving directory '/home/michele/Programmi/sage/build/make'\nMakefile:563: recipe for target 'all' failed\nmake[1]: *** [all] Error 2\nmake[1]: Leaving directory '/home/michele/Programmi/sage/build/make'\n```\nThank you very much!\n\nMichele",
    "created_at": "2015-07-28T10:30:26Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/18938",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/18938#issuecomment-265850",
    "user": "https://github.com/sagetrac-borassi"
}

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

archive/issue_comments_265851.json:

{
    "body": "<div id=\"comment:20\" align=\"right\">comment:20</div>\n\nAfter performing the following changes, I'm able to compile the doc.\n\n- In `_path_length`, change\n\n```\n       WARNING: if the graph is unweighted, the algorithm does not check that\n       the path exists. Moreover, also if the weight_function does not return a\n       number, an error is raised.\n```\nTo\n\n```\n        .. WARNING::\n\n            If the graph is unweighted, the algorithm does not check that the\n            path exists. Moreover, also if the weight_function does not return a\n            number, an error is raised.\n```\nThe `WARNING:` should declare a block, so may be you should insert space/blank line (not sure). \n\n- In `wiener_index`, change\n\n```\n       .. [KRG96b] S. Klavzar, A. Rajapakse, and I. Gutman. The Szeged and the\n       Wiener index of graphs. *Applied Mathematics Letters*, 9(5):45--49,\n       1996.\n```\nto\n\n```\n       .. [KRG96b] S. Klavzar, A. Rajapakse, and I. Gutman. The Szeged and the\n         Wiener index of graphs. *Applied Mathematics Letters*, 9(5):45--49,\n         1996.\n```",
    "created_at": "2015-07-29T12:52:21Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/18938",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/18938#issuecomment-265851",
    "user": "https://github.com/dcoudert"
}

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.

archive/issue_comments_265852.json:

{
    "body": "Changed commit from **[`38c10d4`](https://github.com/sagemath/sagetrac-mirror/commit/38c10d43143d985adbb57fcb514f3483ee30941d)** to **[`760ea87`](https://github.com/sagemath/sagetrac-mirror/commit/760ea8746d52a8d9fbfb22621ae7063ab93c2ceb)**",
    "created_at": "2015-07-29T14:43:46Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/18938",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/18938#issuecomment-265852",
    "user": "https://github.com/sagetrac-git"
}

Changed commit from 38c10d4 to 760ea87

archive/issue_comments_265853.json:

{
    "body": "<div id=\"comment:21\"></div>\n\nBranch pushed to git repo; I updated commit sha1. New commits:\n<table><tr><td><a href=\"https://github.com/sagemath/sagetrac-mirror/commit/36126551bb752b5157383fa591186b6d772a9ce9\"><code>3612655</code></a></td><td><code>Temp</code></td></tr><tr><td><a href=\"https://github.com/sagemath/sagetrac-mirror/commit/760ea8746d52a8d9fbfb22621ae7063ab93c2ceb\"><code>760ea87</code></a></td><td><code>Refactored shortest paths (first working draft)</code></td></tr></table>\n",
    "created_at": "2015-07-29T14:43:46Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/18938",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/18938#issuecomment-265853",
    "user": "https://github.com/sagetrac-git"
}

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

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

archive/issue_events_266447.json:

{
    "actor": "https://github.com/sagetrac-borassi",
    "created_at": "2015-07-29T14:45:24Z",
    "event": "labeled",
    "issue": "https://github.com/sagemath/sage/issues/18938",
    "label": "https://github.com/sagemath/sage/labels/needs%20review",
    "label_color": "7fff00",
    "label_name": "needs review",
    "label_text_color": "ffffff",
    "type": "issue_event",
    "url": "https://github.com/sagemath/sage/issues/18938#event-266447"
}

archive/issue_comments_265854.json:

{
    "body": "<div id=\"comment:22\" align=\"right\">comment:22</div>\n\nFinally, I have a version of the refactoring that might be reviewed. Hope you like it!",
    "created_at": "2015-07-29T14:45:24Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/18938",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/18938#issuecomment-265854",
    "user": "https://github.com/sagetrac-borassi"
}

comment:22

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

archive/issue_comments_265855.json:

{
    "body": "Changed commit from **[`760ea87`](https://github.com/sagemath/sagetrac-mirror/commit/760ea8746d52a8d9fbfb22621ae7063ab93c2ceb)** to **[`5c78561`](https://github.com/sagemath/sagetrac-mirror/commit/5c7856142001699dbe00ad659a0ea95b66bedbf8)**",
    "created_at": "2015-07-30T16:38:39Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/18938",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/18938#issuecomment-265855",
    "user": "https://github.com/sagetrac-git"
}

Changed commit from 760ea87 to 5c78561

archive/issue_comments_265856.json:

{
    "body": "<div id=\"comment:23\"></div>\n\nBranch pushed to git repo; I updated commit sha1. New commits:\n<table><tr><td><a href=\"https://github.com/sagemath/sagetrac-mirror/commit/793dc1213a1bd3a8b9107ff5cafcc246f9903db1\"><code>793dc12</code></a></td><td><code>Merged with 6.9.beta0</code></td></tr><tr><td><a href=\"https://github.com/sagemath/sagetrac-mirror/commit/5c7856142001699dbe00ad659a0ea95b66bedbf8\"><code>5c78561</code></a></td><td><code>Small correction in doctest</code></td></tr></table>\n",
    "created_at": "2015-07-30T16:38:39Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/18938",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/18938#issuecomment-265856",
    "user": "https://github.com/sagetrac-git"
}

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

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

archive/issue_comments_265857.json:

{
    "body": "<div id=\"comment:24\" align=\"right\">comment:24</div>\n\nHello,\n\nThe 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.\n\n```\n[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\nError building the documentation.\nTraceback (most recent call last):\n  File \"/Users/dcoudert/sage/src/doc/common/builder.py\", line 1626, in <module>\n    getattr(get_builder(name), type)()\n  File \"/Users/dcoudert/sage/src/doc/common/builder.py\", line 292, in _wrapper\n    getattr(get_builder(document), 'inventory')(*args, **kwds)\n  File \"/Users/dcoudert/sage/src/doc/common/builder.py\", line 503, in _wrapper\n    x.get(99999)\n  File \"/Users/dcoudert/sage/local/lib/python/multiprocessing/pool.py\", line 558, in get\n    raise self._value\nOSError: [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\n\nmake[1]: *** [doc-html] Error 1\n```\nDavid.",
    "created_at": "2015-08-04T13:59:40Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/18938",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/18938#issuecomment-265857",
    "user": "https://github.com/dcoudert"
}

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.

archive/issue_events_266448.json:

{
    "actor": "https://github.com/dcoudert",
    "created_at": "2015-08-04T13:59:40Z",
    "event": "unlabeled",
    "issue": "https://github.com/sagemath/sage/issues/18938",
    "label": "https://github.com/sagemath/sage/labels/needs%20review",
    "label_color": "7fff00",
    "label_name": "needs review",
    "label_text_color": "ffffff",
    "type": "issue_event",
    "url": "https://github.com/sagemath/sage/issues/18938#event-266448"
}

archive/issue_events_266449.json:

{
    "actor": "https://github.com/dcoudert",
    "created_at": "2015-08-04T13:59:40Z",
    "event": "labeled",
    "issue": "https://github.com/sagemath/sage/issues/18938",
    "label": "https://github.com/sagemath/sage/labels/needs%20work",
    "label_color": "ffff00",
    "label_name": "needs work",
    "label_text_color": "ffffff",
    "type": "issue_event",
    "url": "https://github.com/sagemath/sage/issues/18938#event-266449"
}

archive/issue_comments_265858.json:

{
    "body": "<div id=\"comment:25\"></div>\n\nBranch pushed to git repo; I updated commit sha1. New commits:\n<table><tr><td><a href=\"https://github.com/sagemath/sagetrac-mirror/commit/3f371f844ecd2667b268d74fa258787f3c6da1c4\"><code>3f371f8</code></a></td><td><code>Removed duplicate reference</code></td></tr></table>\n",
    "created_at": "2015-08-05T06:06:07Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/18938",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/18938#issuecomment-265858",
    "user": "https://github.com/sagetrac-git"
}

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

3f371f8 Removed duplicate reference

archive/issue_comments_265859.json:

{
    "body": "Changed commit from **[`5c78561`](https://github.com/sagemath/sagetrac-mirror/commit/5c7856142001699dbe00ad659a0ea95b66bedbf8)** to **[`3f371f8`](https://github.com/sagemath/sagetrac-mirror/commit/3f371f844ecd2667b268d74fa258787f3c6da1c4)**",
    "created_at": "2015-08-05T06:06:07Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/18938",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/18938#issuecomment-265859",
    "user": "https://github.com/sagetrac-git"
}

Changed commit from 5c78561 to 3f371f8

archive/issue_comments_265860.json:

{
    "body": "<div id=\"comment:26\" align=\"right\">comment:26</div>\n\nI removed the duplicate reference: now the citation refers to the other module.",
    "created_at": "2015-08-05T06:07:02Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/18938",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/18938#issuecomment-265860",
    "user": "https://github.com/sagetrac-borassi"
}

comment:26

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

archive/issue_events_266450.json:

{
    "actor": "https://github.com/sagetrac-borassi",
    "created_at": "2015-08-05T06:07:02Z",
    "event": "unlabeled",
    "issue": "https://github.com/sagemath/sage/issues/18938",
    "label": "https://github.com/sagemath/sage/labels/needs%20work",
    "label_color": "ffff00",
    "label_name": "needs work",
    "label_text_color": "ffffff",
    "type": "issue_event",
    "url": "https://github.com/sagemath/sage/issues/18938#event-266450"
}

archive/issue_events_266451.json:

{
    "actor": "https://github.com/sagetrac-borassi",
    "created_at": "2015-08-05T06:07:02Z",
    "event": "labeled",
    "issue": "https://github.com/sagemath/sage/issues/18938",
    "label": "https://github.com/sagemath/sage/labels/needs%20review",
    "label_color": "7fff00",
    "label_name": "needs review",
    "label_text_color": "ffffff",
    "type": "issue_event",
    "url": "https://github.com/sagemath/sage/issues/18938#event-266451"
}

archive/issue_events_266452.json:

{
    "actor": "https://github.com/dcoudert",
    "created_at": "2015-08-05T07:35:30Z",
    "event": "unlabeled",
    "issue": "https://github.com/sagemath/sage/issues/18938",
    "label": "https://github.com/sagemath/sage/labels/needs%20review",
    "label_color": "7fff00",
    "label_name": "needs review",
    "label_text_color": "ffffff",
    "type": "issue_event",
    "url": "https://github.com/sagemath/sage/issues/18938#event-266452"
}

archive/issue_events_266453.json:

{
    "actor": "https://github.com/dcoudert",
    "created_at": "2015-08-05T07:35:30Z",
    "event": "labeled",
    "issue": "https://github.com/sagemath/sage/issues/18938",
    "label": "https://github.com/sagemath/sage/labels/positive%20review",
    "label_color": "dfffc0",
    "label_name": "positive review",
    "label_text_color": "ffffff",
    "type": "issue_event",
    "url": "https://github.com/sagemath/sage/issues/18938#event-266453"
}

archive/issue_comments_265861.json:

{
    "body": "<div id=\"comment:27\" align=\"right\">comment:27</div>\n\nHello,\n\nnow the doc build properly and it looks fine.\nFor me this ticket is now good to go.\n\nBest,\nDavid.",
    "created_at": "2015-08-05T07:35:30Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/18938",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/18938#issuecomment-265861",
    "user": "https://github.com/dcoudert"
}

comment:27

Hello,

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

Best, David.

archive/issue_events_266454.json:

{
    "actor": "https://github.com/dcoudert",
    "created_at": "2015-08-05T07:35:30Z",
    "event": "demilestoned",
    "issue": "https://github.com/sagemath/sage/issues/18938",
    "milestone_number": null,
    "milestone_title": "sage-6.8",
    "type": "issue_event",
    "url": "https://github.com/sagemath/sage/issues/18938#event-266454"
}

archive/issue_events_266455.json:

{
    "actor": "https://github.com/dcoudert",
    "created_at": "2015-08-05T07:35:30Z",
    "event": "milestoned",
    "issue": "https://github.com/sagemath/sage/issues/18938",
    "milestone_number": null,
    "milestone_title": "sage-6.9",
    "type": "issue_event",
    "url": "https://github.com/sagemath/sage/issues/18938#event-266455"
}

archive/issue_comments_265862.json:

{
    "body": "Reviewer: **David Coudert**",
    "created_at": "2015-08-05T07:35:30Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/18938",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/18938#issuecomment-265862",
    "user": "https://github.com/dcoudert"
}

Reviewer: David Coudert

archive/issue_comments_265863.json:

{
    "body": "Changed branch from **[u/borassi/refactor_shortest_paths](https://github.com/sagemath/sagetrac-mirror/tree/u/borassi/refactor_shortest_paths)** to **[`3f371f8`](https://github.com/sagemath/sagetrac-mirror/commit/3f371f844ecd2667b268d74fa258787f3c6da1c4)**",
    "created_at": "2015-08-05T10:51:44Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/18938",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/18938#issuecomment-265863",
    "user": "https://github.com/vbraun"
}

Changed branch from u/borassi/refactor_shortest_paths to 3f371f8

archive/issue_events_266456.json:

{
    "actor": "https://github.com/vbraun",
    "created_at": "2015-08-05T10:51:44Z",
    "event": "unlabeled",
    "issue": "https://github.com/sagemath/sage/issues/18938",
    "label": "https://github.com/sagemath/sage/labels/positive%20review",
    "label_color": "dfffc0",
    "label_name": "positive review",
    "label_text_color": "ffffff",
    "type": "issue_event",
    "url": "https://github.com/sagemath/sage/issues/18938#event-266456"
}

archive/issue_events_266457.json:

{
    "actor": "https://github.com/vbraun",
    "commit_id": "00f8736263a6ec834d228e456932b04d79947263",
    "commit_repository": "https://github.com/sagemath/sage",
    "created_at": "2015-08-05T10:51:44Z",
    "event": "closed",
    "issue": "https://github.com/sagemath/sage/issues/18938",
    "type": "issue_event",
    "url": "https://github.com/sagemath/sage/issues/18938#event-266457"
}

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

18938.md

18938.md

Issue 18938: Refactor shortest paths

Files

18938.md

Latest commit

History

18938.md

File metadata and controls

Issue 18938: Refactor shortest paths