DirectedSequenceRouter.CalculateOptimimal Bug

[juliusfriedman]

There seems to be an issue in the aforementioned where the index can be outside the bounds of the array:

var nextArray = new int[directedWeights.Length / 2];

When directedWeights is empty this results in a 0 length array which is attempted to be written to on the very next line.

I suggest a fix of var nextArray = new int[Math.Max(1,directedWeights.Length / 2]);

A similar fix might be also needed on the lines above:

var paths = new Tuple<int, float>[directedWeights.Length * 2]; // (int previous, float cost)[capacity]; e.g. this line might need a Math.Max(1, )...

There is also an issue later down at the exit of the method:

while (nextHop.Item1 >= 4) { h--; path[h] = nextHop.Item1; nextHop = paths[nextHop.Item1]; }

I think that should also have an && h > 0

With the code modified as:

while (nextHop.Item1 >= 4 && h > 0) { h--; path[h] = nextHop.Item1; nextHop = paths[nextHop.Item1]; }

The method succeeds however I get a Result<Route> with IsError == false and the Value is null.... I am not sure how to proceed from here:

The easy fix I can see is that if the Concatenate method should result in an IsError = true when it's passed an empty set of routes, the other way would be to check if routes.Count == 0 and make an empty route or something...

E.g. perhaps in Result:

/// <summary>
        /// Creates a new result.
        /// </summary>
        public Result(T result)
        {
            _value = result;
            this.ErrorMessage = string.Empty;
            this.IsError = result == null? true : false;
        }

The only other thing I can tell you is that if I do something like this:

if (null == route.Value)
						{
							System.Threading.Thread.Sleep(10);

							goto Route;
						}

I Eventually get an exception:

Route at index 3 is in error: Raw path was not found between 3[0]->4[0]:

Or something similar:

Any help you can provide on this would be great as I need to use Contractions to get the turnPenalty to work unless you know another way.

If I revise my calling code slightly to:

var route = Router.TryCalculate(profile ?? TrainProfileFastest, routerPoints, float.MaxValue, new float?[] { 0, 1 }, cancellationToken);

I get an exception in the same method, Line 270: (Index is out of bounds)

if (fixedTurns?[nextVisit].Item1 != null)

If I modify the for loop like so:

for (var nextTurn = 0; nextTurn < 4 && nextVisit < fixedTurns?.Length; nextTurn++)

I get past that exception but right back to the same exception I cite above (Route at index 3 is in error: Raw path was not found between 3[0]->4[0]:)

I am taking a break for the night but I really would appreciate your assistance in this matter @xivk or @Chaz6 or @bertt or @jbelien or @pietervdvn or anyone else who can assist.

[xivk]

The turn penalty will only work when building a CH that can handle directed queries but it should also work with uncontracted networks?

I looks like one of the routes cannot be found but there is a weight for it? Is that possible?

[juliusfriedman]

If you look at the code for "Contraction-based many-to-many calculates are not supported in the given router db for the given profile" You will see that almost all the Algorithms used require the contracted db, if you know another way please do let me know.

The only way I was able to work around this was by using try with the turnPenalty and falling back to turn based routing when this occurs. (I am pretty sure that TryCalculate shouldn't throw an exception so that is also something to look into)

Also I am not sure how to check the weight for it, if you can supply some instructions to check that I will report back but please also see the comments above which were reporting Index out of bounds etc.

If you can also provide an example of using turnPenalty without a contracted db it would be helpful.

Thank you!

[juliusfriedman]

@xivk, @airbreather

The fix for your tests is achieved by the following:

for (var nextTurn = 0; fixedTurns != null ? nextVisit < fixedTurns.Length : nextTurn < 4; nextTurn++)

Or more optimally to avoid the repeated null check and to use pre rather than post increment:

for (int nextTurn = 0, e = fixedTurns != null ? fixedTurns.Length : 4; nextTurn < e; ++nextTurn)

int internal static int[] CalculateOptimimal(float[][] directedWeights, float turnPenalty, Tuple<bool?, bool?>[] fixedTurns = null)

Line 259 I believe.

Also OptimizeTurns_ShouldUseTurnsWhenItsCheaper is missing the following check in DirectedSequenceRouterTests

Assert.AreEqual(4, turns.Length);
Assert.AreEqual(new[] { 0, 6, 9, 14 }, turns);

Regards.