Dijkstra using bound question

Dijkstra.java Code like barefoot -> master (13.08.2017)

I am wondering about the break of exiting the while loop -> max != null && current.four() > max) when current Mark has a higher bound, this includes reaching bound -> succbound - bound.cost(successor, 1 - target.fraction()) succesor bound -> current.four() + bound.cost(successor)

Because when breaking the loop all left priorites in the queue will not be in the transitions. This is for me not reasonable for the reason that the order of successors should be random and not intentionable ordered. Am I wrong in this assumption?

Assumption:

Succesors are ordered randomly ? -> Iterator successors = current.one().successors();

If my assumption is correct this break should be removed.

 while (priorities.size() > 0) {
            Mark current = priorities.poll();

            if (targetEdges.isEmpty()) {
                logger.trace("finshed all targets");
                break;
            }

            if (max != null && current.four() > max) {
                logger.trace("reached maximum bound");
                break;
            }
.... // code not necessary shown for this question ...

 Iterator<E> successors = current.one().successors();

 while (successors.hasNext()) {
                E successor = successors.next();

                double succcost = current.three() + cost.cost(successor);
                double succbound = bound != null ? current.four() + bound.cost(successor) : 0.0;

                if (targetEdges.containsKey(successor)) { // reach target edge
                    for (P target : targetEdges.get(successor)) {
                        double reachcost = succcost - cost.cost(successor, 1 - target.fraction());
                        double reachbound = bound != null
                                ? succbound - bound.cost(successor, 1 - target.fraction()) : 0.0;

                        logger.trace(
                                "reached target {} with successor edge {} and fraction {} with {} cost",
                                target, successor.id(), target.fraction(), reachcost);

                        Mark reach = new Mark(successor, current.one(), reachcost, reachbound);
                        reaches.put(reach, target);
                        priorities.add(reach);
                    }
                }

                if (!entries.containsKey(successor)) {
                    logger.trace("added successor edge {} with {} cost", successor.id(), succcost);
                    Mark mark = new Mark(successor, current.one(), succcost, succbound);

                    entries.put(successor, mark);
                    priorities.add(mark);
                }
            }

Enclosed is an json example of an HMM-break due to this behavior described above

[{
    "time": "2017-08-08 11:25:50+0000",
    "id": "30343130303031303036323930",
    "point": "POINT(4.435831206184 51.198107382397)"
},
{
    "time": "2017-08-08 11:26:00+0000",
    "id": "30343130303031303036323930",
    "point": "POINT(4.436823647046 51.199911928297)"
},
{
    "time": "2017-08-08 11:26:10+0000",
    "id": "30343130303031303036323930",
    "point": "POINT(4.437777055934 51.20158898784)"
},
{
    "time": "2017-08-08 11:26:20+0000",
    "id": "30343130303031303036323930",
    "point": "POINT(4.438881118299 51.203221180403)"
},
{
    "time": "2017-08-08 11:26:30+0000",
    "id": "30343130303031303036323930",
    "point": "POINT(4.440169787962 51.204774391744)"
},
{
    "time": "2017-08-08 11:26:40+0000",
    "id": "30343130303031303036323930",
    "point": "POINT(4.441924193822 51.205754733085)"
},
{
    "time": "2017-08-08 11:26:50+0000",
    "id": "30343130303031303036323930",
    "point": "POINT(4.444137706146 51.206043690826)"
},
{
    "time": "2017-08-08 11:27:00+0000",
    "id": "30343130303031303036323930",
    "point": "POINT(4.444830506023 51.207221774429)"
},
{
    "time": "2017-08-08 11:27:10+0000",
    "id": "30343130303031303036323930",
    "point": "POINT(4.444517943304 51.208346005571)"
},
{
    "time": "2017-08-08 11:27:40+0000",
    "id": "30343130303031303036323930",
    "point": "POINT(4.442988052019 51.208206995832)"
},
{
    "time": "2017-08-08 11:27:50+0000",
    "id": "30343130303031303036323930",
    "point": "POINT(4.441642543291 51.208170774264)"
},
{
    "time": "2017-08-08 11:28:00+0000",
    "id": "30343130303031303036323930",
    "point": "POINT(4.44077781115 51.206976461368)"
},
{
    "time": "2017-08-08 11:28:10+0000",
    "id": "30343130303031303036323930",
    "point": "POINT(4.439769932742 51.205517319858)"
},
{
    "time": "2017-08-08 11:28:20+0000",
    "id": "30343130303031303036323930",
    "point": "POINT(4.438605559746 51.20388100838)"
},
{
    "time": "2017-08-08 11:28:30+0000",
    "id": "30343130303031303036323930",
    "point": "POINT(4.437546150865 51.202324849503)"
},
{
    "time": "2017-08-08 11:28:40+0000",
    "id": "30343130303031303036323930",
    "point": "POINT(4.436614339904 51.200741613974)"
},
{
    "time": "2017-08-08 11:28:50+0000",
    "id": "30343130303031303036323930",
    "point": "POINT(4.435708181122 51.19912641652)"
},
{
    "time": "2017-08-08 11:29:00+0000",
    "id": "30343130303031303036323930",
    "point": "POINT(4.434683144565 51.197406289675)"
},
{
    "time": "2017-08-08 11:29:10+0000",
    "id": "30343130303031303036323930",
    "point": "POINT(4.433353746312 51.195810533056)"
},
{
    "time": "2017-08-08 11:29:20+0000",
    "id": "30343130303031303036323930",
    "point": "POINT(4.431492546094 51.194422465644)"
},
{
    "time": "2017-08-08 11:29:30+0000",
    "id": "30343130303031303036323930",
    "point": "POINT(4.429019085546 51.193218241922)"
},
{
    "time": "2017-08-08 11:29:40+0000",
    "id": "30343130303031303036323930",
    "point": "POINT(4.426184318901 51.192244707468)"
},
{
    "time": "2017-08-08 11:29:50+0000",
    "id": "30343130303031303036323930",
    "point": "POINT(4.423186193152 51.191531120343)"
},
{
    "time": "2017-08-08 11:30:00+0000",
    "id": "30343130303031303036323930",
    "point": "POINT(4.420304902363 51.191075914992)"
},
{
    "time": "2017-08-08 11:30:10+0000",
    "id": "30343130303031303036323930",
    "point": "POINT(4.417319790224 51.191286853537)"
},
{
    "time": "2017-08-08 11:30:20+0000",
    "id": "30343130303031303036323930",
    "point": "POINT(4.414007634937 51.191943851686)"
},
{
    "time": "2017-08-08 11:30:30+0000",
    "id": "30343130303031303036323930",
    "point": "POINT(4.410602317274 51.191766126923)"
},
{
    "time": "2017-08-08 11:30:40+0000",
    "id": "30343130303031303036323930",
    "point": "POINT(4.407716474742 51.190690597001)"
},
{
    "time": "2017-08-08 11:30:50+0000",
    "id": "30343130303031303036323930",
    "point": "POINT(4.406329963479 51.189592719171)"
},
{
    "time": "2017-08-08 11:31:00+0000",
    "id": "30343130303031303036323930",
    "point": "POINT(4.405610843937 51.189114964879)"
},
{
    "time": "2017-08-08 11:31:10+0000",
    "id": "30343130303031303036323930",
    "point": "POINT(4.40407902046 51.188955263983)"
},
{
    "time": "2017-08-08 11:31:20+0000",
    "id": "30343130303031303036323930",
    "point": "POINT(4.403717771424 51.188001622265)"
},
{
    "time": "2017-08-08 11:31:30+0000",
    "id": "30343130303031303036323930",
    "point": "POINT(4.404286704541 51.186955694046)"
},
{
    "time": "2017-08-08 11:31:40+0000",
    "id": "30343130303031303036323930",
    "point": "POINT(4.404502657381 51.186463815651)"
},
{
    "time": "2017-08-08 11:31:50+0000",
    "id": "30343130303031303036323930",
    "point": "POINT(4.403100282243 51.185907928692)"
},
{
    "time": "2017-08-08 11:32:00+0000",
    "id": "30343130303031303036323930",
    "point": "POINT(4.401417237744 51.185281584432)"
},
{
    "time": "2017-08-08 11:32:10+0000",
    "id": "30343130303031303036323930",
    "point": "POINT(4.399996499695 51.184763818533)"
}]

You have a valid point in your arguments but let me first understand your intensions:

"[T]he order of successors should be random and not intentionable ordered." - Do you refer to successors as the edges to be traversed and stored in the priority queue? Well, this is intentionably ordered as of the Dijkstra algorithm to search first shortest paths.
The cost and bound are two different cost functions. Here, cost defines the shortest path and is therefore the basis for ordering of the priority queue. In turn, bound defines a maximum depth for the search.
You're right about the concern that the break can eliminate paths that are below the maximum bound. For example, let the priority queue contain two paths p1 and p2 to be evaluated next where p1 is the shorter path and does not hit the target and p2 is the longer path but hits the target. If p1 exceeds the maximum bound, we also eliminate p2 which is the shortest path to the target although it may or may not exceed the maximum bound.

As a solution to 3., we must consider the following: If we replace the break with a continue we would eliminate only paths that exceed the maximum bound, but a result may not be the (globally seen) shortest path because the shortest path could be the one that has been eliminated.

This would have the following semantics: The result is the shortest path (according to cost) that is within the maxmimum bound (according to bound). [... which means there may exist a shorter path (according to cost) which is not in the result set because it exceeds the maximum bound (according to bound).]

Suggestion: Try to replace the break with a continue and check if your example behaves as would expect. If so, I would fix right away and document the (new) defined behavior.

Hi Sebastian,

thank your for this fast reply. I tested this issue already and on the sample is works fine. I will do a regression test with more complex tests this week. And will update you on this term.

1.Where are the succesors as the neighbors of a road ordered? I just found the iterator in AbstractEdge class. 2.The function bound.cost(successor) retrieves the full length of a road. 3.So I do still not understand why the a break should apply, you implemented for every path two marks: One with the maxmium depth and one with relative depth (point). IF the relative depth is shorter then the maxbound but the maximum depth of path is not. The path is still in the transition.

Alright, the iteration over successor edges is an arbitrary order that is of no further importance.
bound.cost(successor) retrieves the cost value for the full length of the road according to the bound function; and cost.cost(successor) retrieves the cost value for the full length of the road according to the cost function.
Well, the conclusion is the break should not apply. Anyways, there are no two marks. Each path has two cost values that are both complete in the sense that they include a cost value for the full path of an edge with all its predecessors to the source. The two values rely just on different cost functions, i.e., cost and bound. Each cost value is added separately if we add an edge to the path. The thing that you probably mix up is that if a path hits a target, we evaluate not the full edge but only the fraction up to the target point.

In my point of view adding the line

entries.put(successor, reach); for the if targetEdges part would be more effective.

while (successors.hasNext()) {
                E successor = successors.next();

                double succcost = current.three() + cost.cost(successor);
                double succbound = bound != null ? current.four() + bound.cost(successor) : 0.0;

                if (targetEdges.containsKey(successor)) { // reach target edge
                    for (P target : targetEdges.get(successor)) {
                        double reachcost = succcost - cost.cost(successor, 1 - target.fraction());
                        double reachbound = bound != null
                                ? succbound - bound.cost(successor, 1 - target.fraction()) : 0.0;

                        logger.trace(
                                "reached target {} with successor edge {} and fraction {} with {} cost",
                                target, successor.id(), target.fraction(), reachcost);

                        Mark reach = new Mark(successor, current.one(), reachcost, reachbound);
                        reaches.put(reach, target);

                         **entries.put(successor, reach);**
                        priorities.add(reach);
                    }
                }

                if (!entries.containsKey(successor)) {
                    logger.trace("added successor edge {} with {} cost", successor.id(), succcost);
                    Mark mark = new Mark(successor, current.one(), succcost, succbound);

                    entries.put(successor, mark);
                    priorities.add(mark);
                }

You mean removing the break from https://github.com/bmwcarit/barefoot/blob/c7b55daab5fe14c3e0b02f9e76e22ca509633ac4/src/main/java/com/bmwcarit/barefoot/topology/Dijkstra.java#L206 and adding entries.put(successor, reach) after https://github.com/bmwcarit/barefoot/blob/c7b55daab5fe14c3e0b02f9e76e22ca509633ac4/src/main/java/com/bmwcarit/barefoot/topology/Dijkstra.java#L254? What's the effect? Why should it be more effective than something else and in comparison to what? I don't see how this can replace the feature of bounding the search depth to some maximum.

HI, our tests were successful. The continue instead of the break did not produce any miscalucted routes. And the HMM break was fixed.

bmwcarit / barefoot

Dijkstra using bound question #67