<feed xmlns='http://www.w3.org/2005/Atom'>
<title>delta/python-packages/networkx.git/networkx/algorithms/tests, branch docdraft</title>
<subtitle>github.com: networkx/networkx.git
</subtitle>
<link rel='alternate' type='text/html' href='http://git.baserock.org/cgit/delta/python-packages/networkx.git/'/>
<entry>
<title>Moves and updates docs for hybrid power law graphs</title>
<updated>2015-05-02T22:50:38+00:00</updated>
<author>
<name>Jeffrey Finkelstein</name>
<email>jeffrey.finkelstein@gmail.com</email>
</author>
<published>2015-05-02T22:50:38+00:00</published>
<link rel='alternate' type='text/html' href='http://git.baserock.org/cgit/delta/python-packages/networkx.git/commit/?id=430851bbd428c8d5843882e3e06f2d8b6eb62483'/>
<id>430851bbd428c8d5843882e3e06f2d8b6eb62483</id>
<content type='text'>
This commit combines two changes. First, it moves the module
`networkx.generators.hybrid` to `networkx.algorithms.hybrid` (and moves
the corresponding test modules as well). Second, it adds missing
documentation to the functions in that module.
</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
This commit combines two changes. First, it moves the module
`networkx.generators.hybrid` to `networkx.algorithms.hybrid` (and moves
the corresponding test modules as well). Second, it adds missing
documentation to the functions in that module.
</pre>
</div>
</content>
</entry>
<entry>
<title>Adds vertex and edge contraction functions.</title>
<updated>2015-04-29T20:28:12+00:00</updated>
<author>
<name>Jeffrey Finkelstein</name>
<email>jeffrey.finkelstein@gmail.com</email>
</author>
<published>2015-03-26T21:21:32+00:00</published>
<link rel='alternate' type='text/html' href='http://git.baserock.org/cgit/delta/python-packages/networkx.git/commit/?id=bb1d14d2dd243875853cf22dafa66779f3df4f1b'/>
<id>bb1d14d2dd243875853cf22dafa66779f3df4f1b</id>
<content type='text'>
This implements vertex and edge contraction as functions that return new
graph objects with the specified vertices or edge contracted.

This fixes issue #1057.
</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
This implements vertex and edge contraction as functions that return new
graph objects with the specified vertices or edge contracted.

This fixes issue #1057.
</pre>
</div>
</content>
</entry>
<entry>
<title>Fix link prediction tests that failed under PyPy</title>
<updated>2015-04-28T20:04:40+00:00</updated>
<author>
<name>Raf Guns</name>
<email>rafguns@gmail.com</email>
</author>
<published>2015-04-28T19:23:29+00:00</published>
<link rel='alternate' type='text/html' href='http://git.baserock.org/cgit/delta/python-packages/networkx.git/commit/?id=7c2758740c4627204294f4a767cd9f31247e5048'/>
<id>7c2758740c4627204294f4a767cd9f31247e5048</id>
<content type='text'>
The tests expected the ouput of nx.non_edges to preserve a certain
order. This is no longer the case. The change also removes some code
duplication in the test suite.
</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
The tests expected the ouput of nx.non_edges to preserve a certain
order. This is no longer the case. The change also removes some code
duplication in the test suite.
</pre>
</div>
</content>
</entry>
<entry>
<title>Update algorithms/dag.py and algorithms/tests/test_dag.py to be PEP8 complaint</title>
<updated>2015-04-24T23:45:47+00:00</updated>
<author>
<name>Mridul Seth</name>
<email>seth.mridul@gmail.com</email>
</author>
<published>2015-04-24T23:45:47+00:00</published>
<link rel='alternate' type='text/html' href='http://git.baserock.org/cgit/delta/python-packages/networkx.git/commit/?id=3968de45fc83f05117646e4bfbe2ec8fee4dfae9'/>
<id>3968de45fc83f05117646e4bfbe2ec8fee4dfae9</id>
<content type='text'>
</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
</pre>
</div>
</content>
</entry>
<entry>
<title>Added longest_path and longest_path_length for DAG</title>
<updated>2015-04-24T23:30:53+00:00</updated>
<author>
<name>Mridul Seth</name>
<email>seth.mridul@gmail.com</email>
</author>
<published>2015-04-09T19:42:34+00:00</published>
<link rel='alternate' type='text/html' href='http://git.baserock.org/cgit/delta/python-packages/networkx.git/commit/?id=b836dba90d94135c14445b77a7415e9fba291d1b'/>
<id>b836dba90d94135c14445b77a7415e9fba291d1b</id>
<content type='text'>
</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
</pre>
</div>
</content>
</entry>
<entry>
<title>Adds triadic census function to new `triads` module</title>
<updated>2015-04-24T06:00:59+00:00</updated>
<author>
<name>Jeffrey Finkelstein</name>
<email>jeffrey.finkelstein@gmail.com</email>
</author>
<published>2015-04-23T02:10:37+00:00</published>
<link rel='alternate' type='text/html' href='http://git.baserock.org/cgit/delta/python-packages/networkx.git/commit/?id=c004822f8d68034ee0b41d35acfb72ece313fe13'/>
<id>c004822f8d68034ee0b41d35acfb72ece313fe13</id>
<content type='text'>
</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
</pre>
</div>
</content>
</entry>
<entry>
<title>Fix copyrights</title>
<updated>2015-04-21T16:51:07+00:00</updated>
<author>
<name>JGab</name>
<email>jean.gabriel.young@gmail.com</email>
</author>
<published>2015-04-21T16:51:07+00:00</published>
<link rel='alternate' type='text/html' href='http://git.baserock.org/cgit/delta/python-packages/networkx.git/commit/?id=bc987a9a5e3de487b231bfb27e4d0ee929d924c6'/>
<id>bc987a9a5e3de487b231bfb27e4d0ee929d924c6</id>
<content type='text'>
</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
</pre>
</div>
</content>
</entry>
<entry>
<title>Improve documentation and add more tests.</title>
<updated>2015-04-17T16:04:49+00:00</updated>
<author>
<name>Jordi Torrents</name>
<email>jordi.t21@gmail.com</email>
</author>
<published>2015-04-13T16:15:06+00:00</published>
<link rel='alternate' type='text/html' href='http://git.baserock.org/cgit/delta/python-packages/networkx.git/commit/?id=31a8ef2d21df2d60fcb13b631c77c6e87ba5be0d'/>
<id>31a8ef2d21df2d60fcb13b631c77c6e87ba5be0d</id>
<content type='text'>
Added example of an efficient function to compute k shortest paths
in the example section of shortest_simple_paths docstrings. Added
more tests, I think all relevant code for this function is covered
now.
</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
Added example of an efficient function to compute k shortest paths
in the example section of shortest_simple_paths docstrings. Added
more tests, I think all relevant code for this function is covered
now.
</pre>
</div>
</content>
</entry>
<entry>
<title>Improve shortest_simple_paths implementation and add more tests.</title>
<updated>2015-04-17T16:04:49+00:00</updated>
<author>
<name>Jordi Torrents</name>
<email>jordi.t21@gmail.com</email>
</author>
<published>2015-04-08T23:38:33+00:00</published>
<link rel='alternate' type='text/html' href='http://git.baserock.org/cgit/delta/python-packages/networkx.git/commit/?id=65d7b52685af3990d711b7b19759687b3a53a3f5'/>
<id>65d7b52685af3990d711b7b19759687b3a53a3f5</id>
<content type='text'>
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.
</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
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.
</pre>
</div>
</content>
</entry>
<entry>
<title>Add shortest_simple_paths function.</title>
<updated>2015-04-17T16:04:49+00:00</updated>
<author>
<name>Jordi Torrents</name>
<email>jordi.t21@gmail.com</email>
</author>
<published>2015-04-08T02:01:44+00:00</published>
<link rel='alternate' type='text/html' href='http://git.baserock.org/cgit/delta/python-packages/networkx.git/commit/?id=90d958897e3b29a33ebf352e55498e72a2959ace'/>
<id>90d958897e3b29a33ebf352e55498e72a2959ace</id>
<content type='text'>
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?
</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
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?
</pre>
</div>
</content>
</entry>
</feed>
