[Edit: this has been superseded by nx_spatial which is available from pypi (easy_install nx_spatial). Importing shapefiles is now standard in networkx 1.4]
I've been kind of disappointed by the lack of geometric network tools in ESRI's Python GP API, so I wrote up something that loads Shapefiles and Feature Classes into networkx directional graphs (DiGraphs).
It is still a work in progress, but it might be an okay starting off point for something that can help with your problem.
from utilitynetwork import Network
net = Network()
#load single file, method reqs OGR
#load directory full of shapefiles
#load a feature class, req ESRI gp object, should work with shps as well
gp = arcgisscripting.create(9.3)
#Accessing node/edge data is done by the key value (the geometry as a tuple).
#access node data at x=4, y=2
nodekey = (4, 2)
Network is inherits from networkx.DiGraph, so all of that functionality is available.