Preprocessing fails to find nodes and may find incorrect nodes

[dvbuntu]

Describe the bug In preprocessing.py, the check for exceptions when where are no nodes violating the resource limit is tripped early by the "Source" or "Sink" node itself. The paths for these are necessarily 1 long, and may come up in the list comprehension before other actually resource constraint violated paths. The exception catches the index error, meaning we never add some of the violated nodes.

In large graphs, assuming a random order of keys in the dict, there is a smaller probability of this happening. But in small graphs, the chance of missing a node is much higher.

A somewhat related issue is that the node selected for removal may be wrong. By picking the next-to-last node in a path, we may be removing a node that is on some other path between the Source and the Sink. I think the correct node to remove should be the last node in the path, the one we cannot reach. There may be cases where we wouldn't even want to remove this node, I haven't examined all the possibilities.

To Reproduce

from cspy import BiDirectional
import numpy as np
import networkx as nx
from networkx import DiGraph

# make a simple graph, with labeled resource usage
# B clearly superfluous
#            1       1
#   Source ---> A ----> Sink
#               ^ 
#            10 \---->B
H = DiGraph(n_res=1)
max_res = [5]
min_res = [1]
H.add_edge('Source', 'A', res_cost=np.array([1]), weight=1)
H.add_edge('A', 'B', res_cost=np.array([10]), weight=1)
H.add_edge('B', 'A', res_cost=np.array([10]), weight=1)
H.add_edge('A', 'Sink', res_cost=np.array([1]), weight=1)

# seems to works, but error is masked
bidirec = BiDirectional(H, max_res, min_res, direction='forward', seed=42, preprocess=False)
bidirec.run()
print(bidirec.path, bidirec.total_cost, bidirec.consumed_resources)
bidirec = BiDirectional(H, max_res, min_res, direction='forward', seed=42, preprocess=True)
bidirec.run()
print(bidirec.path, bidirec.total_cost, bidirec.consumed_resources)

length_s, path_s = nx.single_source_bellman_ford(H, 'Source', weight=getw)
length_t, path_t = nx.single_source_bellman_ford(H.reverse(copy=True), 'Sink', weight=getw)

nodes_source = {}
nodes_sink = {}

# B should be identified (or rather A because of B)
# But get IndexError
try:
    nodes_source.update({
    path_s[key][-2]: (val, r)
    for key, val in length_s.items()
    if val > max_res[r] or val < min_res[r]
    })
    nodes_sink.update({
    path_t[key][-2]: (val, r)
    for key, val in length_t.items()
    if val > max_res[r] or val < min_res[r]
    })
except IndexError:
    print(nodes_source, nodes_sink)

# Fix to check if key is already at Source or Sink
nodes_source.update({
    path_s[key][-2]: (val, r)                              # I think this index should be -1
    for key, val in length_s.items()
    if key != 'Source' and (val > max_res[r] or val < min_res[r])
    })
nodes_sink.update({
    path_t[key][-2]: (val, r)                              # I think this index should be -1
    for key, val in length_t.items()
    if key != 'Sink' and (val > max_res[r] or val < min_res[r])
    })
print(nodes_source, nodes_sink)

## But now node 'A' is slated to be removed, causing graph to be disconnected
H.remove('A')
bidirec = BiDirectional(H, max_res, min_res, direction='forward', seed=42, preprocess=False)
bidirec.run() # failure

Expected behavior preprocessing.py should ignore "Source" or "Sink" itself when checking related length keys. Further, the node to be removed should be the final node in the path, not the next to last, as that node may be required for other paths. There may be a more theoretically robust preprocessing that identifies offending edges and removes those; any nodes that become disconnected could then be safely removed.

Desktop (please complete the following information):

• OS: CentOS
• cspy 1.0.0a0
• numpy 1.19.2
• networkx 2.5
• Python 3.8.5

Additional context This bug can happen in modest size (say 25) random graphs with reasonable probability. I'd be happy to make a pull request if that's easiest, but I don't have a build system setup to run all the tests before submitting.

[torressa]

Hey again @dvbuntu, thanks for bringing up another bug!

There are some preprocessing techniques but most of them use the source-to-all shortest paths which has to run twice (one for each direction) and then times the number of resources. So it can get really slow. Also, they are only effective on certain types of networks (e.g. doesn't work on connected graphs like the ones you get in VRP instances).

In a recent paper, link found in #67, has a much faster and elegant solution to this. They also have a crazy good implementation Haven't gotten round to implementing it yet, but was definitely one of my priorities.

You are very welcome to open a PR with the fix for this :) the workflows will show if the test pass. The build process is pretty straight forward if you set up docker, or alternatively install cmake on your machine.

[dvbuntu]

Looking at the preprocessing more closely, I'm not sure that it's checking the min_res correctly. It looks for minimum weight paths and checks if the shortest path (for a given resource) is less than the minimum constraint. But if the shortest path is too short, there could be some longer path which is valid.

Ideally, we'd check if the longest path is not long enough. But we can't just make the weights negative and look for the shortest since that will likely introduce negative-weight cycles (for the original weights being positive). But the Longest Path Problem is NP-Hard, so we're not going to have a quick way to do this check. We may want to just avoid checking the minimum constraint in the preprocessor.

[dvbuntu]

PR #74 opened to address this and some closely related bugs.

[torressa]

Thanks for the PR and for taking some time to think about this, it is greatly appreciated! Everything passed so just merged it, the release wheel won't work as it needs another version number but will sort it out with the other stuff (#68, #69, etc). I'll leave this open until then

[dvbuntu]

Sounds good, thanks for taking a look and merging. Great library by the way! Happy to help make it even better.