Succinct circuit representation of graphs

The complexity class PPAD (e.g. computing various Nash equilibria) can be defined as the set of total search problems polytime reducible to END OF THE LINE:

END OF THE LINE: Given circuits S and P with n input bits and n output bits such that P(0n) = 0n != S(0n), find an input x in {0,1}n such that P(S(x)) != x or S(P(x)) != x != 0n.

Circuits or algorithms such as S and P implicitly define an exponentially large graph that is only revealed on a query-by-query basis (to keep the problem in PSPACE!), e.g. Papadimitrou's paper.

However, I don't understand how one would design a circuit that enables arbitrary graphs (if there is a systematic structure to the graph, it appears much easier to find the circuit). For instance, how would one design a polynomially-sized circuit that represents an exponentially-long directed line, with an all-0 label for the source vertex and randomly assigned binary labels to all other vertices? This seems to be implicit in the PPAD-related papers.

The closest I've come from a search online is Galperin/Widgerson's paper, but the circuit described there takes two vertex labels and returns a Boolean answer to "Are these vertices adjacent?"

So, how would you design a polynomially-sized circuit of an exponentially-sized graph that takes an n-bit input and outputs the n-bit label of its predecessor or successor, respectively? Or even, does someone know of a resource that explains this well?