2012-10-23

Graph theory for railfans: A side story of Authors in a Markov matrix


This is a side story of ``Authors in a Markov matrix: Which author inspires the people most?'' What relationship do railfans and Graph theory have? is the theme of this story. (Japanese version)

My colleague Dietger asked me, ``Do you know how to traverse the all the edges in a graph?'' I asked back, ``Isn't it a Hamiltonian path problem?''

He answered, ``No. Hamiltonian path is the problem to traverse all the nodes only once. Instead of the nodes, I want to know how to visiting all the edges once.'' I intuitively answered, ``Can we solve it on the dual graph?'' But this was wrong. Figures 1, 2, 3 show the what is the face-vertex dual graph, and Figure 3 shows there is no edge dual graph.  For instance, in a triangle mesh, vertices are connected via edges, faces are also connected via edges. Therefore, vertex (node) and face can be (so called) dual. Then, what is the connection between edges? There is no connection between edges, or edges themselves are connection. This is  the difference between face/vertex and edge.
Figure 1: Duality of face and vertex: faces to a dual graph.
Figure 2: Duality of face and vertex: a dual graph to faces.
Figure 3: Edge's duality?
``What kind of application do you think of, if any?'', I asked him. He explained me that this is his friend's problem. His friend is working for a railway company. He needs to check all the railway track in his country regularly with a special train. How efficient he can check the railway is an important problem. This is called a Chinese postman problem in graph theory. Mei Ko Kuan, a Chinese mathematician, is one of the early researcher of this problem, so the name of the problem comes from that. This is related with the Euler path problem (one-stroke problem). Now you see the connection between graph theory and railway.

I recall a similar problem that was presented at PTT (Programming tools and techniques) long time ago. PTT is a kind of club that the people are interested in computer programming. In some reason, there are many railfans also. Kasai presented ``Longest One-way-ticket Problem'' at PTT.  ``Longest Oneway-ticket Problem'' is a problem to find the longest one way ticket you can buy. He thought about the JR (Japan Railway) ticket. http://www.swa.gr.jp/lop/index.html

Kasai tried two different methods: linear programming and brute-force method. The both solution are the same. But, he needed some techniques to simplify the problem for the brute-forth method, e.g., graph simplification and graph subdivision. The result is shown here. http://www.swa.gr.jp/lop/lop_res.html
referred from http://www.swa.gr.jp/lop/lop_res.html
Kasai also explained the algorithm in details (in Japanese). He used a commercial linear programming solver, that was quite expensive in 2000. However, five years later, he revised the method and show how to solve the problem on a personal computer with a free liner programming solver, GLPK (GNU Linear Programming Kit).

I am also surprised that a person compute this longest one way ticket by hand, he started this hobby around 1960s. His hand computed result is quite similar with Kasai's result. Is this person a genius, or human brain has such a incredible ability? I am impressed.

By the way, I believe railfans are all over the world. There is a special TV channel for railfans in Germany. I wonder that the German channel tried such kind of experience. Kasai used Japanese geographic constraint to simplify the graph. He divided whole Japan graph to sub-graphs since Japan is consists of islands. The connection between islands are very limited. Has anyone computed the German longest one way ticket? Or European longest one way ticket? If you know such page, please write me a comment.

No comments: