Pair of non-intersecting shortest paths on undirected graph

Specific Domains Graphs
,
1

Hello,
I only have a very basic background in graph theory and don’t really know the ideas behind most of the algorithms that are used for path/cycle detection, yet I have somehow found myself in a position where I’m working with graphs and it seems that the LightGraphs library is not able to provide a direct and efficient solution to the problem I need to solve(I assume it might be a rare use case, so I’m not blaming anyone).

Before embarking on the task of writing my own algorithm(for which I would first need to understand how the already-existent efficient algorithms are built) I tried to combine what I’ve found in LightGraphs to reach my goal and I did it, but I feel it’s a really bad approach and turns out to have really bad performance.

The problem is the following:
given a pair of nodes (i,j) belonging to an undirected graph, I want to find the length of the two non-intersecting shortest paths between i and j.
In other words, I want to find the shortest cycle(circuit, ring, whatever you like…) through i and j.

Now LightGraphs does not really have any implementation for cycle detection on undirected graphs; I think I had read somewhere on the web the developers’ explanation for this choice regarding the ambiguity of defining cycles on undirected graphs(I didn’t really agree with their points though…), so the useful formulation here will be that in terms of the shortest paths rather than cycle.

This is the best I could come up with:

function minring(g::SimpleGraph{Int}, i::Int, j::Int)
    npaths = 10
    k_shortest = yen_k_shortest_paths(g, i, j, weights(g), npaths)
    for (ip,p) in enumerate(k_shortest.paths)
        if intersect(p, k_shortest.paths[1]) == [i,j]
            return k_shortest.dists[1] + k_shortest.dists[ip]
        end # if
    end # for
    return typemax(Int)
end # function

yen_k_shortest_paths returns the npaths shortest paths from i to j on graph g, sorted by increasing length. Therefore what I do is evaluate a fixed number of shortest paths, hope that among the generated paths there is one that does not intersect the shortest one(=intersect should return only the start and end points) and then sum up their lengths to find the ring length.

A few measures to show how yen_k_shortest_paths behaves on a sample random graph with 1000 vertices and 2000 edges:

julia> @benchmark yen_k_shortest_paths(g, rand(1:1000), rand(1:1000), weights(g), 10)
BenchmarkTools.Trial: 
  memory estimate:  135.97 KiB
  allocs estimate:  1023
  --------------
  minimum time:     31.841 μs (0.00% GC)
  median time:      23.365 ms (0.00% GC)
  mean time:        22.616 ms (4.41% GC)
  maximum time:     30.136 ms (8.08% GC)
  --------------
  samples:          221
  evals/sample:     1

julia> @benchmark yen_k_shortest_paths(g, rand(1:1000), rand(1:1000), weights(g), 100)
BenchmarkTools.Trial: 
  memory estimate:  220.16 MiB
  allocs estimate:  2107351
  --------------
  minimum time:     256.932 ms (6.24% GC)
  median time:      292.091 ms (6.20% GC)
  mean time:        289.920 ms (6.01% GC)
  maximum time:     324.093 ms (6.16% GC)
  --------------
  samples:          18
  evals/sample:     1

[the evaluation of rand takes <10 ns, and interpolating the variables does not make any difference]
Now consider that I have to do this multiple times for each node in the graph and repeat on a lot of different graphs(also larger graphs, roughly 10^4 vertices, 2*10^4 edges, adding approximately a factor of 10 to computing time, Yen’s algorithm being ~O(vertices + edges)). It’s going to take quite some time.
If I use a low value of npaths the timing is lower but it’s easy to miss non-intersecting paths, while increasing npaths leads to a large slowdown. For my use cases npaths=50 seems to be enough to get correct results(the pairs for which I need to do this evaluation are typically not too far away from each other, but I can’t be sure that this is always the case, so I would like to know that I get them all correct without relying on the choice of npaths).
So I was wondering:

  1. is there any tool in LightGraphs that I missed that would allow me to solve this problem?
  2. is there any other graph library that could help me?
  3. can I approach the problem in a different, more convenient way?

Thank you to anyone willing to help.

2

No guarantees that it is correct, but I would at least try the following:

  1. Find the shortest path from i to j.
  2. Remove all edges from the non-endpoint nodes on that path.
  3. Find a new shortest path from i to j.
3 Likes
3

Note that this algorithm has 2 advantages: it quickly sets an upper bound on cost for a cycle, and it will always fine a cycle if one exists.

1 Like
4

How embarrassing, it was so easy :cold_sweat:
By using a_star and removing the edges from a copy of the graph I get some ~50x speedup and indeed no missing cycles.
By changing the structure a little and using dijkstra_shortest_paths I can probably get to some ~100x or even 200x with respect to the one I posted originally.

It’s incredible how easy it is to mess up something so simple. Thank you very much.

1 Like
5

Sadly this is not always correct. In this example

1---2---3
|   |   |
|   5---4
|   |    
7---6

there is a cycle through 1 and 4 but if you’re unlucky to get the first shortest path as 1-2-5-4, there’s no way back.

This does work but is likely way overkill and hardly the fastest solution:

julia> using Pkg

julia> pkg"add LongestPaths#weighted_paths"
[...]
julia> using LightGraphs, LongestPaths

julia> g = SimpleGraph(7)
{7, 0} undirected simple Int64 graph

julia> add_edge!.(Ref(g), [(1,2),(1,7),(2,3),(2,5),(3,4),(4,5),(5,6),(6,7)]);

julia> g2 = SimpleDiGraph(g)
{7, 16} directed simple Int64 graph

julia> w = Dict(e => (4 in e ? 10 : -1) for e in Tuple.(edges(g2)))
Dict{Tuple{Int64,Int64},Int64} with 16 entries:
  (4, 3) => 10
  (2, 3) => -1
  (5, 6) => -1
  (5, 4) => 10
  (2, 1) => -1
  (2, 5) => -1
  (1, 7) => -1
  (7, 1) => -1
  (4, 5) => 10
  (3, 2) => -1
  (5, 2) => -1
  (7, 6) => -1
  (6, 5) => -1
  (6, 7) => -1
  (1, 2) => -1
  (3, 4) => 10

julia> r = find_longest_cycle(g2, 1, weights = w)
Turning off use_ip_warmstart to work around a Cbc bug.
  1     0 [-2.0 18.0] 0.0 0 Optimal 18.0 18.0
  2     0 [-2.0 18.0] 0.0 2 Optimal 18.0 18.0
  3     0 [-2.0 16.0] 0.0 4 Optimal 16.0 16.0
  4     0 [15.0 15.0] 0.0 8 Optimal 15.0 15.0
Longest cycle with bounds [15.0, 15.0] and a recorded cycle of weight 15.

julia> r.longest_path
7-element Array{Int64,1}:
 1
 7
 6
 5
 4
 3
 2
2 Likes
6

Thank you for the counterexample, but I don’t really understand what the attached code is doing, nor how it relates in general to the problem of looking for the shortest cycle. I’ll be thankful if you(or anyone else) could explain

7

The README of LongestPaths and the doc string for find_longest_cycle should be informative.

In short LongestPaths is about finding the longest simple (no repeated nodes) path/cycle in a graph. This is an NP-hard problem that is considerably (and that’s an understatement) harder than finding shortest paths. However, if you give the edges negative weight, the maximization problem will favor having as few edges as possible, so it has been turned around to a search for a shortest path. It’s not a particularly efficient way to find a shortest path, but it works.

find_longest_cycle looks for cycles including one required node. However, your problem has two required nodes. This can be emulated by weighting the edges going to the second required node by a sufficiently high positive value. That way the maximum path weight can only be obtained by cycles that include that node, if any such cycles exist at all. So the solution, once found, will be the shortest cycle that passes both required nodes.

1 Like