<feed xmlns='http://www.w3.org/2005/Atom'>
<title>delta/python-packages/networkx.git/networkx/algorithms/simple_paths.py, 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>Spelling error Examples</title>
<updated>2015-06-13T19:41:05+00:00</updated>
<author>
<name>Aric Hagberg</name>
<email>aric.hagberg@gmail.com</email>
</author>
<published>2015-06-13T19:41:05+00:00</published>
<link rel='alternate' type='text/html' href='http://git.baserock.org/cgit/delta/python-packages/networkx.git/commit/?id=a404e5fa278510505b9129b76087ff5266cd7025'/>
<id>a404e5fa278510505b9129b76087ff5266cd7025</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>
<entry>
<title>bugfix per issue 797</title>
<updated>2012-12-18T16:26:18+00:00</updated>
<author>
<name>Seth Bromberger</name>
<email>seth@ncisecurity.com</email>
</author>
<published>2012-12-18T16:26:18+00:00</published>
<link rel='alternate' type='text/html' href='http://git.baserock.org/cgit/delta/python-packages/networkx.git/commit/?id=f22c0f25b393ad63c2a0273dea3bd095bcb4d63f'/>
<id>f22c0f25b393ad63c2a0273dea3bd095bcb4d63f</id>
<content type='text'>
</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
</pre>
</div>
</content>
</entry>
<entry>
<title>Add better examples and docs for all_simple_paths.</title>
<updated>2012-06-18T18:18:54+00:00</updated>
<author>
<name>Aric Hagberg</name>
<email>aric.hagberg@gmail.com</email>
</author>
<published>2012-06-18T18:18:54+00:00</published>
<link rel='alternate' type='text/html' href='http://git.baserock.org/cgit/delta/python-packages/networkx.git/commit/?id=5f4de7bc27d6ecf0fe0b58b74e466002b3201c0a'/>
<id>5f4de7bc27d6ecf0fe0b58b74e466002b3201c0a</id>
<content type='text'>
</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
</pre>
</div>
</content>
</entry>
<entry>
<title>fix failing doctest in all_simple_paths()</title>
<updated>2012-06-13T00:10:17+00:00</updated>
<author>
<name>Aric Hagberg</name>
<email>aric.hagberg@gmail.com</email>
</author>
<published>2012-06-13T00:10:17+00:00</published>
<link rel='alternate' type='text/html' href='http://git.baserock.org/cgit/delta/python-packages/networkx.git/commit/?id=7f1fb7d1cc5ffc0823a78db541e42a2d6bef2ba6'/>
<id>7f1fb7d1cc5ffc0823a78db541e42a2d6bef2ba6</id>
<content type='text'>
</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
</pre>
</div>
</content>
</entry>
<entry>
<title>Cutoff condition needed in sipmle_paths to avoid spurious corner case.</title>
<updated>2012-06-02T02:51:32+00:00</updated>
<author>
<name>Aric Hagberg</name>
<email>aric.hagberg@gmail.com</email>
</author>
<published>2012-06-02T02:51:32+00:00</published>
<link rel='alternate' type='text/html' href='http://git.baserock.org/cgit/delta/python-packages/networkx.git/commit/?id=654dfdafb3495322359db12f6860365cd0f76754'/>
<id>654dfdafb3495322359db12f6860365cd0f76754</id>
<content type='text'>
Addresses #713
</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
Addresses #713
</pre>
</div>
</content>
</entry>
<entry>
<title>Add example in simple_paths.  Check for missing source and target.</title>
<updated>2012-06-01T21:47:43+00:00</updated>
<author>
<name>Aric Hagberg</name>
<email>aric.hagberg@gmail.com</email>
</author>
<published>2012-06-01T21:47:43+00:00</published>
<link rel='alternate' type='text/html' href='http://git.baserock.org/cgit/delta/python-packages/networkx.git/commit/?id=09f35a373e4c48ca969ef3faa4d520352c38ff38'/>
<id>09f35a373e4c48ca969ef3faa4d520352c38ff38</id>
<content type='text'>
Addresses #713
</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
Addresses #713
</pre>
</div>
</content>
</entry>
<entry>
<title>Remove cutoff condition check.  Update docs.</title>
<updated>2012-06-01T21:38:53+00:00</updated>
<author>
<name>Aric Hagberg</name>
<email>aric.hagberg@gmail.com</email>
</author>
<published>2012-06-01T21:38:53+00:00</published>
<link rel='alternate' type='text/html' href='http://git.baserock.org/cgit/delta/python-packages/networkx.git/commit/?id=f971a9a024c73eb7f50c399a193ff96579335e42'/>
<id>f971a9a024c73eb7f50c399a193ff96579335e42</id>
<content type='text'>
Addresses #713
</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
Addresses #713
</pre>
</div>
</content>
</entry>
</feed>
