Just from my rusty memory, the roads were after the Crazy Years and before the Prophet. So yes, before the theocracy.
EDIT: I found a link to the chart.
http://templetongate.net/graphics/literature/fhchartlarge.gi...
http://templetongate.net/graphics/literature/fhchartlarge.gi...
Asking for a friend.