Relabel to front, what does topological sort according to admissible network mean?

Question

In the CLRS book it says that "relabel to front" algorithm, which solves the maximum-flow problem, maintains a list of topologically sorted vertices in the admissible network and that vertices with zero excess flow are moved to the front of the list.

I do not fully understand what is the meaning of it. I would imagine that the vertices are sorted according to the number of admissible edges incident on it. But then how would moving vertices with no excess flow to front affects the sorting order in this case. Also how come the list is already sorted when it is initialized with random order of vertices?

Edit:

Just realized that topological sorting of vertices in the admissible network means that for every admissible edge (u,v) in the admissible network the vertex u appears before v in the list.

This does not answer the last two parts of my question though, how is that the list is already sorted when initialized and how does moving zero-excess-flow vertices to front affect the order. Thanks.

Answer 1

By definition an "admissible edge" $(u,v)$ is an edge that has a residual capacity $c_f(u,v) > 0$ and the height of the vertex it enters is greater than the vertex it leaves by exactly one $h.u = h.v + 1$.

1- When the list is initialized, there exist no admissible-edges in the admissible-network because the height difference between all pairs of vertices in the network is either $|V|$ or $0$; only the source vertex has a height of $|V|$ while all other vertices has a height of $0$. Therefore, no matter which order of vertices we use, the list will be topologically sorted.

2- After relabeling a vertex $u$, there is at least on edge leaving $u$, but there are no edges entering it (according to lemma 26.28 in CLRS book p.750). Therefore, there can exist no other vertex $v$ such that $(v,u)$ is an edge and $v$ precedes $u$ in the topological order. So moving $u$ to the front of the list keeps it topologically sorted.