Is a DAG appropriate for a metro network?

[khinsen]

This looks like an interesting idea, but I wonder about the basic premise that a metro network can be represented as a DAG, given that it's neither directed nor acyclic.

[vbarbaresi]

Indeed, the premise doesn't seem promising at first glance. But the construction of a DAG from the cyclic graph is an interesting problem, and it turns out we don't need to remove many vertices. The constructed DAG is not far from reality, which makes sense because it's not in the best interest of the transport network to construct too many cycles.

[khinsen]

There are certainly many interesting problems in dealing with transport network graphs. Are there any studies about the optimal number of cycles? I'd expect that there should always be some to ensure redundancy, otherwise the network would easily break down in case of an accident or of construction work.

[vbarbaresi]

I don't know any studies yet, this subject is new to me, but I plan to look into it.

About Paris (I don't know much about the other cities):

I know for a fact that they often use some of this redundancy to quickly transport some maintenance equipment across lines. I haven't computed things like the critical path, but I think the average path cost isn't so bad. I would be interested to analyze and get relevant statistics from the metro graph in a future Python project.

I don't think this redundancy was intended by design, it comes from historical reasons. During the war they shut down some stations, because there were too many of them. There are still too many lines relatively to the very small area of Paris. This causes traffic issues on some portions which are too busy: a delay on one line can impact the rest of the network. Redundancy is a good thing, but sharing too many paths in your network is detrimental.