How can I turn a vector layer into a graph G = (V, E)?

NetworkX ( A python module for the creation, manipulation, and study of the structure, dynamics, and functions of complex networks ) has a read_shp() function which generates a graphs from shapefiles. You might want to check it out. Here's a short tutorial.

No TPSLIB export as far as I know but does support writing the graphs into formats like GML, GraphML, Pickle, adjacency lists, and GEXF to name a few. The full list of output formats can be found here. I hope this helps. Good luck.