Proposal: Eliminate SPTVertex/SPTEdge

[novalis]

Goal: Cleaner code, less small temporary object creation. This is a more formal writeup of some things that have been discussed off-trac.

In OTP, SPTs wrap graph edges and vertices in their SPT counterparts. That makes for a lot of extra objects that could be eliminated. This proposal has been broken into small pieces to facilitate discussion or line-item vetos. The most basic changes are listed first, building up to potentially controversial ones.

'''1. Eliminate SPTVertex/SPTEdge.''' States could be given backVertex and backEdge members, making the SPT implicit and SPTVertex objects unnecessary. bdferris, I imagine you need both a back-Edge and a back-EdgeNarrative for path optimization since Edges using dynamic vehicle arrival times return multiple results.

'''2. Eliminate TraverseResult.''' Edge traversal functions could simply produce a new (modified) State from an existing State, rather than TraverseResult + State. These new States would carry all information now contained in State, TraverseResult, and SPTVertex. This is coherent since any state is already associated with (located at) a single vertex, is the child of another state, and is born of an edge traversal. The exception is an initial state, which would have backVertex=null and backEdge=null. Changes in StateData then always have a corresponding edge to 'justify' the state transition.

'''3. FreeEdge traversal''' could be optimized by putting the back-edge/back-vertex pointers in State instead of StateData. Traversing an edge would always make a new State, but the StateData would sometimes be reused unchanged.

'''4. Some kinds of edges produce multiple results''', so States would either need to provide a chaining mechanism (State.next) or traverse methods would need to return collections of states.

'''5. Priority queues contain States.''' This is particularly appropriate for multi-criteria routing (where States are often called labels or events).

'''6. Shortest path trees contain States.''' SPTs can be reduced to structured collections of States (binned by Vertex for example), with logic for deciding which states to accept or reject based on existing entries. An SPT could be as simple as a list of states for the target vertex plus a closed vertex checklist.

'''7. A path through the graph is implicit in a single State.''' You just follow the chain of links until back=null. Follow them back once to optimize the path, then starting with the new optimized state at the search origin, scan through forward to make an itinerary. For example, something like stateInstance.optimizeBack().getItineraryForward() would only need to create State and Itinerary objects.

'''8. Routing algorithms could conceivably return states''' (at the target) rather than returning an SPT. A distinction could be made between one-to-one and one-to-many algorithms (e.g. transitsheds) with the latter returning Map<Vertex, Collection>.

'''9. Weight could be automatically recalculated''' upon State creation based on the Editor and TraverseOptions.

---

Here's what the A* algorithm would then look like in pseudojava:

{{{ SPT searchForward(origin, target, options) State s0 = new State(origin) double h = heuristic.computeInitialWeight(s0, target) priorityQueue.insert(s0, h) while !priorityQueue.isEmpty() s0 = priorityQueue.extractMin() if (s0.exceedsLimits(options)) continue if (s0.isAt(target)) return spt // or maybe return s0; for (Edge e : s0.vertex.getOutgoing()) State s1 = e.traverseForward(s0, options)) while (s1 != null) s2 = s1 s1 = s1.next s2.unlink() if(spt.add(s2)) h = heuristic.computeForwardWeight(s2, target) priorityQueue.insert(s2, s2.weight + h)

}}}

[novalis]

--andrewbyrd

[novalis]

--andrewbyrd

[novalis]

+1

--novalis

[novalis]

{{{

!html

}}} This ticket has been referenced in ticket #409:

...above.

Path optimization needs to be rewritten anyway when working on ticket #399 (Eliminate SPTVertex/SPTEdge).

--andrewbyrd

[novalis]

(from an email discussion, for posterity):

Combining State with TraverseResult and SPTVertex meant that certain things in State would be changing at every traversal, so having only time in State itself would lead to StateData being duplicated for every new State, which defeated the purpose.

So certain new members of State and certain members of StateData would need to be shuffled around to get a decent level of not-copying. Not wanting to keep track of tentative decisions as to which members required indirection and which did not while getting the StateEditor working, I started by moving everything into State. I kept StateData around anticipating moving most of the members back over there when it became evident to me which would be changed the least frequently.

Since this is now causing confusion, the time has obviously come to re-attach StateData. This has been done in r1566.

Future decisions to move any given member to/from State or StateData should be totally transparent since everything is necessarily accessed through getter/setter methods.

--andrewbyrd