Yen simplest paths enumeration

[Андрей Парамонов]

I'm now working on implementing an algorithm for enumeration of simple paths between two nodes of a digraph. My procedure implements method described in Yen. It has advantage that it returns the shortest paths first and is so tends to return the most interesting routes very fast (much faster than all_simple_paths). Thus it can be used as a practical approximation for all_simple_paths for large and dense graphs where all_simple_paths is unacceptably slow.

Currently I have a working version of yen_simple_paths. However algorithm requires a procedure for finding single shortest path with restrictions. What I did was to modify networkx source and introduce optional ignore_nodes and ignore_edges parameter for shortest path procedures. Please review attached patches and tell if such change can be accepted upstream, wrt interface.

Another alternative is to modify graph itself on each iteration and revert modifications later. But I like this much less as it would introduce unnecessary restrictions (unapplicable to frozen graphs, potential multi-threading etc).

What do you think? If it's acceptable, I'll try to find time to add doc strings, support ignore_nodes and ignore_edges in all *shortest_path* procedures etc.

Best wishes,

Andrey Paramonov

[Андрей Парамонов]

2012/8/28 Андрей Парамонов <cmr....@gmail.com>:

> What I did was to modify networkx source and introduce optional ignore_nodes
> and ignore_edges parameter for shortest path procedures. Please review
> attached patches and tell if such change can be accepted upstream, wrt
> interface.

Upon thinking a bit I'm now considering another approach: instead of
optional ignore_nodes and ignore_edges introduce single optional
callable filter_edge parameter which if specified must take two
arguments u, v (nodes) and return True for (u, v) edges that are
"passable". This should give more flexibility.

Best wishes,
Andrey Paramonov

[Jordi Torrents]

Hi Андрей,

2012/8/28 Андрей Парамонов <cmr....@gmail.com>:

I think that we should support finding shortest paths with
restrictions. Another use case for this (besides yan's simple paths)
is a fast approximation for local node connectivity [1]. I implemented
partially the algorithm proposed in [1] at [2], but it only supports
excluding nodes, and it is based on passing to
_bidirectional_shortest_path a container with nodes to exclude that is
checked for each node traversed during the BFS. I think your
implementation is better; in a first sight, I think I prefer this one
better than a single filer_edges (as you propose in the other mail).
Could you open a pull request at github? We could continue there the
discussion about how to implement this.

Thank you very much.
Salut!

[1] A Fast Algorithm for Node-Independent Paths
http://eclectic.ss.uci.edu/~drwhite/working.pdf

[2] https://bitbucket.org/jtorrents/networkx_sc/src/b145cc385191/networkx/algorithms/connectivity/approximation/connectivity.py

[Андрей Парамонов]

вторник, 28 августа 2012 г., 21:52:28 UTC+4 пользователь jtorrents написал

Could you open a pull request at github? We could continue there the
discussion about how to implement this.

Thank you very much.
Salut!

Here is it:
https://github.com/networkx/networkx/pull/762

Best wishes,
Andrey Paramonov