# In LPA*, how are predecessors/successors of a vertex defined?

While trying to implement LPA* (mostly based on its description in the same authors’ paper on its derivative D*Lite), I noticed it mentions predecessors and successors of a vertex without giving a full explanation.

I understand that $Pred(u)$ is the set of all vertices from which an edge leads towards $u$, and $Succ(u)$ is the set of all vertices towards which an edge leads from $u$. Predecessors and successors must be immediate neighbors (thus e.g. a predecessor of a predecessor of $u$ is not necessarily a predecessor of $u$).

In practice, however, it is quite common to have edges that are not directional, i.e. can be traversed both ways (which is equivalent to the same two nodes being connected by two antiparallel directional edges). I infer that for two vertices $u$ and $v$ connected in this way, $u$ would be both a predecessor and a successor of $v$ (and vice versa). In other words, $Pred(u) \cap Succ(u)$ is not necessarily empty.

Am I correct to assume that predecessor and successor are defined only by the existence of an edge traversable in a given direction, and are specifically not related to start cost?

If you have an undirected graph, you can convert it to a directed graph by including edges in both directions: for each undirected edge $(u,v)$, add directed edges $u \to v$ and $v \to u$. So, if you have undirected edges, imagine applying this transformation and then running LPA* on the resulting graph. That should make it clear what to do.
Alternatively: in an undirected graph, Pred(u) is the set of all edges incident on $u$, and so is Succ(u) (there is no distinction between them in an undirected graph). So, yes, they can overlap.
• Thanks for the clarification. I asked because my LPA* implementation would run into an endless loop while calculating vertext cost. I was able to rectify that by explicitly exempting the shortest-path predecessor of u from being updated in ComputeShortestPath(), even if it also is a successor. May 29, 2018 at 19:41