Python 3.2 introduces the `itertools.accumulate()`. Before, we were using less flexible custom code for performing the same task, in `networkx.utils.misc.cumulative_sum`. This commit replaces calls to `cumulative_sum` with calls to `itertools.accumulate()`. Since we currently still support Python 2.7, this commit adds a fallback equivalent definition of accumulate that matches the Python 3.2 implementation. Once support for Python 2.7 is dropped, all of this code can be removed, and calls to `networkx.utils.accumulate()` can be replaced by calls to `itertools.accumulate()`.
I've removed the asserts, fixed the inability to use an arbitrary edge attribute as a weight, and speeded it up by computing separatetly the length/cost of the root and then adding it to the newly found partial path instead of computing the lenth/cost of the whole path when we push it to PathBuffer.
This function is based on Yen's algorithm for finding k shortest paths. It generates all simple paths between source and target starting from the shortest one. See #762 and #793 for prior work on this and discussion. This implementation is based on Andrey's work on #762. It generalizes his approach there to the weighted case, as in Greg's implementation posted on #793. Regarding the discussion on #762 about how to do the filtering of nodes and edges efficiently, this PR adds private modifications of the functions `bidirectional_shortest_path` and `bidirectional_dijkstra` (that accept containers with nodes and edges to exclude during the SP search) for its exclusive use. This still needs work, especially on documentation and tests. I'm pushing it so we can have the discussion with the code available. One thing to discuss is whether or not to include an one liner function to get the k shortest paths. Could be something like this: ```python from itertools import islice def k_shortest_paths(G, source, target, k, weight=None): return list(islice(nx.shortest_simple_paths(G, source, target, weight=weight), k)) ``` I think that, given that `all_simple_paths` is way faster in computing all paths, the principal use of `shortest_simple_paths` will be to get the k best/shortest paths. So it will be a more user friendly interface if we add it. However, we could also add this function as example in the `shortest_simple_paths` docstring. I'm ok either way. Thoughts?
The quotient graph of a graph `G` with respect to an equivalence relation `R` on the nodes of `G` is the graph whose vertex set is the equivalence classes `R` and where there is an edge joining class `c` to class `d` if some vertex in `c` is adjacent to some vertex in `d`. This commit places that function in a new module, `networkx/algorithms/minors.py`, for functions related to graph minors.