Finding shortest paths with python-IGraph on DAGs with negative weights

Question

Task: Find a shortest path for a DAG (directed acyclic graph) with negative weights using python interface to the igraph library, as a list of edges/vertices in a single-source/single-target setup.

Tried: The closest match I found in the documentation is get_shortest_paths. However, when tried the function returns: igraph._igraph.InternalError: Error at structural_properties.c:5220: Weight vector must be non-negative, Invalid value Seems like internally the function tries to apply the Dijkstra's algorithm and fails. In the same time, according to documentation, other shortest path functions (shortest_paths, shortest_paths_dijkstra) are able to adapt the algorithm to the graph's properties.

Questions:

• Is there an alternative function to use in this case?
• Or how to make get_shortest_paths chose a correct internal algorithm?
• Or could the algorithm be specified explicitly (as in the R interface)

Related question:

• Is igraph able to detect that the graph is DAG and use the faster shortest path algorithm on topologically sorted graph?
• Would a custom python code for this be necessarily slower than one of general-purpose internal igraph's algorithms (presumably written in C++)? (|E| is in tens of thousands, |V| is in thousands)

Thanks.

PS. Python 2.7, IGraph 0.6.5

Answer 1

I also had a slow R version. It was taking ~20 minutes for 200k edges and 30k vertices, so I broke down and implemented get.shortest.paths() in R (but not Python; sorry) and igraph_get_shortest_paths_bellman_ford() for graphs with negative edge weights. You can try my fork of R igraph here.

I experienced between 100x and 1000x speedup when switching from my R implementation to C.

Answer 2

get_shortest_paths is not able to handle graphs with negative weights because the underlying C library does not have a corresponding igraph_get_shortest_paths_bellman_ford function yet. It does have an igraph_get_shortest_paths_dijkstra, so the Python interface simply checks whether you have weights and if so, redirects the call to igraph_get_shortest_paths_dijkstra, otherwise it simply calls igraph_get_shortest_paths (which is the unweighted version in the C layer). In contrast, shortest_paths works with negative weights because the C library has a function named igraph_shortest_paths_bellman_ford so it calls the Bellman-Ford implementation when at least one of the edge weights is negative.

Unfortunately the only way out seems to be to implement igraph_get_shortest_paths_bellman_ford in the C layer and then update the Python interface to handle negative weights appropriately.

Answers to related questions:

• igraph does not check whether the graph is a DAG before running any shortest path related function. Yes, shortest paths can be found faster in a DAG but this use-case is so rare that no one bothered to implement the special case so far.

• Custom code written in pure Python is likely to be slower than a C implementation, but it depends on your problem. If you meant the Bellman-Ford algorithm in particular, a pure Python implementation is very likely to be slower, but it may still be usable for the graphs you have. You could try the implementation in NetworkX; as far as I know, NetworkX is pure Python and people still use it for graphs with tens of thousands of nodes and edges.