Mathematica code for the Directed Chinese Postman Problem

Harold Thimbleby,
UCLIC, UCL Interaction Centre
LONDON
h.thimbleby@ucl.ac.uk

A graph is a list of edges {from,to,weight,name}. Vertices are numbered 1..N. (In Java, vertices are numbered 0..N-1.) 

[Graphics:Images/Chinese_gr_1.gif]

We define selectors to extract components of edges. Thus e·weight is the weight of an edge e; this approach gives us a notation similar to Pascal or Java. 

[Graphics:Images/Chinese_gr_2.gif]

We use a built-in Mathematica linear programming routine. Readability of the program is improved by defining selectors to work with Mathematica's results. (The semantics are that Mathematica finds a solution as a set of forms, such as f[2,3]->5. The selectors extract the appropriate parts of the form.) Mathematica allows us to overload the selectors, so we can reuse the same names for readability. 

[Graphics:Images/Chinese_gr_3.gif]

Now the code to do the work. (Some ideas for code is available in Combinatorica (a standard Mathematica package) but Combinatorica does not handle multigraphs.) 

[Graphics:Images/Chinese_gr_4.gif]

The paper's simple example 

[Graphics:Images/Chinese_gr_5.gif]
[Graphics:Images/Chinese_gr_6.gif]
[Graphics:Images/Chinese_gr_7.gif]
[Graphics:Images/Chinese_gr_8.gif]
[Graphics:Images/Chinese_gr_9.gif]
[Graphics:Images/Chinese_gr_10.gif]
[Graphics:Images/Chinese_gr_11.gif]
[Graphics:Images/Chinese_gr_12.gif]
[Graphics:Images/Chinese_gr_13.gif]
[Graphics:Images/Chinese_gr_14.gif]
[Graphics:Images/Chinese_gr_15.gif]

Graphs with symbolic vertex labels

The code above assumes a graph is represented as a list of edges, using vertex numbers. If you use symbolic vertices, the following utility routines are handy.

ToNats converts a graph with symbolic vertices into a graph using natural numbers. 

[Graphics:Images/Chinese_gr_16.gif]

Given a list of numbers, or a list of lists etc, and a symbolic graph, FromNats converts the numbers back to the corresponding symbols. The routine is recursively defined to handle nested lists (such as graphs themselves, which are lists of lists). 

[Graphics:Images/Chinese_gr_17.gif]

Here's how to use them to define a more general Chinese Postman routine: 

[Graphics:Images/Chinese_gr_18.gif]

The Nokia 2110 mobile phone

Here's a demonstration of the more general routine, operating on a mobile phone menu list. Having got a Chinese Postman routine, the tricky part is converting Nokia's definition of their phone into an edge list. The following is a Mathematica-style transcription of the menu map in the Nokia 2110 user manual; it defines a function menu. 

[Graphics:Images/Chinese_gr_19.gif]

This has to be converted to an edge list. Since this is tricky, the function transition, which collects the edges, is also passed a parameter giving the button press for that edge, which is useful for debugging, since the transitions can easily be checked against the Nokia mobile itself. 

[Graphics:Images/Chinese_gr_20.gif]
[Graphics:Images/Chinese_gr_21.gif]

Write the CPP to a file, and then count how many lines were generated, excluding lines that describe "paths". This simply counts the length, in edges, of the CPP. 

[Graphics:Images/Chinese_gr_22.gif]
[Graphics:Images/Chinese_gr_23.gif]
[Graphics:Images/Chinese_gr_24.gif]
[Graphics:Images/Chinese_gr_25.gif]

So the length of a test that each button press (i.e., edge) of the Nokia phone is correct will take 515 button presses. However, some buttons will occasionally not have any effect. The Nokia has 4 (Up, Down, Quit, Select) buttons, so any vertex with fewer than 4 out-edges has some inactive buttons. So the total of the product of the number of states times the number of buttons minus the sum of the out-degrees (i.e., the number of transitions in the finite state machine) gives us the extra number of presses to check the Nokia phone is understood. 

[Graphics:Images/Chinese_gr_26.gif]
[Graphics:Images/Chinese_gr_27.gif]

Convert Mathematica format to Java 

[Graphics:Images/Chinese_gr_28.gif]
[Graphics:Images/Chinese_gr_29.gif]
{ Graph G = new Graph(88);
  G.addEdge("to View options 1",71,73,1);
  G.addEdge("to Number editor",73,51,1);
  G.addEdge("to Recent calls",73,60,1);
  G.addEdge("to Standby",73,71,1);
  G.addEdge("to Messages",60,45,1);
  G.addEdge("to Number editor",60,51,1);
  G.addEdge("to Standby",60,71,1);
  G.addEdge("to View options 2",60,77,1);
  G.addEdge("to Erase all recent calls",77,28,1);
  G.addEdge("to Dialled calls",77,21,1);
  G.addEdge("to Recent calls",77,60,1);
  G.addEdge("to Received calls",21,59,1);
  G.addEdge("to Erase all recent calls",21,28,1);
  G.addEdge("to Recent calls",21,60,1);
  G.addEdge("to Missed calls",59,49,1);
  G.addEdge("to Dialled calls",59,21,1);
  G.addEdge("to Recent calls",59,60,1);
  G.addEdge("to Erase all recent calls",49,28,1);
  G.addEdge("to Received calls",49,59,1);
  G.addEdge("to Recent calls",49,60,1);
  G.addEdge("to Dialled calls",28,21,1);
  G.addEdge("to Missed calls",28,49,1);
  G.addEdge("to Recent calls",28,60,1);
  G.addEdge("to Call divert",45,6,1);
  G.addEdge("to Recent calls",45,60,1);
  G.addEdge("to Standby",45,71,1);
  G.addEdge("to View options 3",45,78,1);
  G.addEdge("to Message settings",78,47,1);
  G.addEdge("to Listen to voice messages",78,38,1);
  G.addEdge("to Messages",78,45,1);
  G.addEdge("to Read messages",38,58,1);
  G.addEdge("to Message settings",38,47,1);
  G.addEdge("to Messages",38,45,1);
  G.addEdge("to Write messages",58,87,1);
  G.addEdge("to Listen to voice messages",58,38,1);
  G.addEdge("to Messages",58,45,1);
  G.addEdge("to Show deliver reports",87,69,1);
  G.addEdge("to Read messages",87,58,1);
  G.addEdge("to Messages",87,45,1);
  G.addEdge("to Message settings",69,47,1);
  G.addEdge("to Write messages",69,87,1);
  G.addEdge("to Messages",69,45,1);
  G.addEdge("to Listen to voice messages",47,38,1);
  G.addEdge("to Show deliver reports",47,69,1);
  G.addEdge("to Messages",47,45,1);
  G.addEdge("to View options 4",47,79,1);
  G.addEdge("to Set mailbox number",79,67,1);
  G.addEdge("to Message centre number",79,44,1);
  G.addEdge("to Message settings",79,47,1);
  G.addEdge("to Message sent as",44,46,1);
  G.addEdge("to Set mailbox number",44,67,1);
  G.addEdge("to Message settings",44,47,1);
  G.addEdge("to Accept reply costs",46,0,1);
  G.addEdge("to Message centre number",46,44,1);
  G.addEdge("to Message settings",46,47,1);
  G.addEdge("to Delivery reports",0,20,1);
  G.addEdge("to Message sent as",0,46,1);
  G.addEdge("to Message settings",0,47,1);
  G.addEdge("to Message validity",20,48,1);
  G.addEdge("to Accept reply costs",20,0,1);
  G.addEdge("to Message settings",20,47,1);
  G.addEdge("to Set mailbox number",48,67,1);
  G.addEdge("to Delivery reports",48,20,1);
  G.addEdge("to Message settings",48,47,1);
  G.addEdge("to Message centre number",67,44,1);
  G.addEdge("to Message validity",67,48,1);
  G.addEdge("to Message settings",67,47,1);
  G.addEdge("to Phone settings",6,56,1);
  G.addEdge("to Messages",6,45,1);
  G.addEdge("to Standby",6,71,1);
  G.addEdge("to View options 5",6,80,1);
  G.addEdge("to Cancel all diverts",80,10,1);
  G.addEdge("to Divert all calls",80,22,1);
  G.addEdge("to Call divert",80,6,1);
  G.addEdge("to Divert when busy",22,25,1);
  G.addEdge("to Cancel all diverts",22,10,1);
  G.addEdge("to Call divert",22,6,1);
  G.addEdge("to Divert when not answered",25,26,1);
  G.addEdge("to Divert all calls",25,22,1);
  G.addEdge("to Call divert",25,6,1);
  G.addEdge("to Divert if not reachable",26,24,1);
  G.addEdge("to Divert when busy",26,25,1);
  G.addEdge("to Call divert",26,6,1);
  G.addEdge("to Divert all data calls",24,23,1);
  G.addEdge("to Divert when not answered",24,26,1);
  G.addEdge("to Call divert",24,6,1);
  G.addEdge("to Cancel all diverts",23,10,1);
  G.addEdge("to Divert if not reachable",23,24,1);
  G.addEdge("to Call divert",23,6,1);
  G.addEdge("to Divert all calls",10,22,1);
  G.addEdge("to Divert all data calls",10,23,1);
  G.addEdge("to Call divert",10,6,1);
  G.addEdge("to Security options",56,66,1);
  G.addEdge("to Call divert",56,6,1);
  G.addEdge("to Standby",56,71,1);
  G.addEdge("to View options 6",56,81,1);
  G.addEdge("to Language",81,36,1);
  G.addEdge("to Lights",81,37,1);
  G.addEdge("to Phone settings",81,56,1);
  G.addEdge("to Ringing volume",37,64,1);
  G.addEdge("to Language",37,36,1);
  G.addEdge("to Phone settings",37,56,1);
  G.addEdge("to Ringing tone",64,63,1);
  G.addEdge("to Lights",64,37,1);
  G.addEdge("to Phone settings",64,56,1);
  G.addEdge("to Keypad tones",63,35,1);
  G.addEdge("to Ringing volume",63,64,1);
  G.addEdge("to Phone settings",63,56,1);
  G.addEdge("to Warning tones",35,85,1);
  G.addEdge("to Ringing tone",35,63,1);
  G.addEdge("to Phone settings",35,56,1);
  G.addEdge("to Automatic redial",85,2,1);
  G.addEdge("to Keypad tones",85,35,1);
  G.addEdge("to Phone settings",85,56,1);
  G.addEdge("to One touch dialling",2,52,1);
  G.addEdge("to Warning tones",2,85,1);
  G.addEdge("to Phone settings",2,56,1);
  G.addEdge("to Automatic answer",52,1,1);
  G.addEdge("to Automatic redial",52,2,1);
  G.addEdge("to Phone settings",52,56,1);
  G.addEdge("to Cell info display",1,11,1);
  G.addEdge("to One touch dialling",1,52,1);
  G.addEdge("to Phone settings",1,56,1);
  G.addEdge("to Own number sending",11,54,1);
  G.addEdge("to Automatic answer",11,1,1);
  G.addEdge("to Phone settings",11,56,1);
  G.addEdge("to Call waiting",54,8,1);
  G.addEdge("to Cell info display",54,11,1);
  G.addEdge("to Phone settings",54,56,1);
  G.addEdge("to Restore factory settings",8,61,1);
  G.addEdge("to Own number sending",8,54,1);
  G.addEdge("to Phone settings",8,56,1);
  G.addEdge("to Menu list",61,43,1);
  G.addEdge("to Call waiting",61,8,1);
  G.addEdge("to Phone settings",61,56,1);
  G.addEdge("to Language",43,36,1);
  G.addEdge("to Restore factory settings",43,61,1);
  G.addEdge("to Phone settings",43,56,1);
  G.addEdge("to Lights",36,37,1);
  G.addEdge("to Menu list",36,43,1);
  G.addEdge("to Phone settings",36,56,1);
  G.addEdge("to Duration and cost",66,27,1);
  G.addEdge("to Phone settings",66,56,1);
  G.addEdge("to Standby",66,71,1);
  G.addEdge("to View options 7",66,82,1);
  G.addEdge("to Closed user group",82,17,1);
  G.addEdge("to PIN code request",82,57,1);
  G.addEdge("to Security options",82,66,1);
  G.addEdge("to Security level",57,65,1);
  G.addEdge("to Closed user group",57,17,1);
  G.addEdge("to Security options",57,66,1);
  G.addEdge("to Call barring",65,3,1);
  G.addEdge("to PIN code request",65,57,1);
  G.addEdge("to Security options",65,66,1);
  G.addEdge("to View fixed dialling",3,72,1);
  G.addEdge("to Security level",3,65,1);
  G.addEdge("to Security options",3,66,1);
  G.addEdge("to View options 8",3,83,1);
  G.addEdge("to Cancel all barrings",83,9,1);
  G.addEdge("to Outgoing calls",83,53,1);
  G.addEdge("to Call barring",83,3,1);
  G.addEdge("to International calls",53,33,1);
  G.addEdge("to Cancel all barrings",53,9,1);
  G.addEdge("to Call barring",53,3,1);
  G.addEdge("to Int except to home country",33,34,1);
  G.addEdge("to Outgoing calls",33,53,1);
  G.addEdge("to Call barring",33,3,1);
  G.addEdge("to Incoming calls",34,31,1);
  G.addEdge("to International calls",34,33,1);
  G.addEdge("to Call barring",34,3,1);
  G.addEdge("to Incoming calls if abroad",31,32,1);
  G.addEdge("to Int except to home country",31,34,1);
  G.addEdge("to Call barring",31,3,1);
  G.addEdge("to Cancel all barrings",32,9,1);
  G.addEdge("to Incoming calls",32,31,1);
  G.addEdge("to Call barring",32,3,1);
  G.addEdge("to Outgoing calls",9,53,1);
  G.addEdge("to Incoming calls if abroad",9,32,1);
  G.addEdge("to Call barring",9,3,1);
  G.addEdge("to Change access codes",72,12,1);
  G.addEdge("to Call barring",72,3,1);
  G.addEdge("to Security options",72,66,1);
  G.addEdge("to Closed user group",12,17,1);
  G.addEdge("to View fixed dialling",12,72,1);
  G.addEdge("to Security options",12,66,1);
  G.addEdge("to View options 9",12,84,1);
  G.addEdge("to Change barring password",84,13,1);
  G.addEdge("to Change security code",84,16,1);
  G.addEdge("to Change access codes",84,12,1);
  G.addEdge("to Change PIN code",16,15,1);
  G.addEdge("to Change barring password",16,13,1);
  G.addEdge("to Change access codes",16,12,1);
  G.addEdge("to Change PIN2 code",15,14,1);
  G.addEdge("to Change security code",15,16,1);
  G.addEdge("to Change access codes",15,12,1);
  G.addEdge("to Change barring password",14,13,1);
  G.addEdge("to Change PIN code",14,15,1);
  G.addEdge("to Change access codes",14,12,1);
  G.addEdge("to Change security code",13,16,1);
  G.addEdge("to Change PIN2 code",13,14,1);
  G.addEdge("to Change access codes",13,12,1);
  G.addEdge("to PIN code request",17,57,1);
  G.addEdge("to Change access codes",17,12,1);
  G.addEdge("to Security options",17,66,1);
  G.addEdge("to Network selection",27,50,1);
  G.addEdge("to Security options",27,66,1);
  G.addEdge("to Standby",27,71,1);
  G.addEdge("to View options 10",27,74,1);
  G.addEdge("to Show costs in",74,68,1);
  G.addEdge("to Call duration",74,7,1);
  G.addEdge("to Duration and cost",74,27,1);
  G.addEdge("to Call costs",7,4,1);
  G.addEdge("to Show costs in",7,68,1);
  G.addEdge("to Duration and cost",7,27,1);
  G.addEdge("to Call costs limit",4,5,1);
  G.addEdge("to Call duration",4,7,1);
  G.addEdge("to Duration and cost",4,27,1);
  G.addEdge("to Show costs in",5,68,1);
  G.addEdge("to Call costs",5,4,1);
  G.addEdge("to Duration and cost",5,27,1);
  G.addEdge("to Call duration",68,7,1);
  G.addEdge("to Call costs limit",68,5,1);
  G.addEdge("to Duration and cost",68,27,1);
  G.addEdge("to Memory functions",50,40,1);
  G.addEdge("to Duration and cost",50,27,1);
  G.addEdge("to Standby",50,71,1);
  G.addEdge("to Personal reminders",40,55,1);
  G.addEdge("to Network selection",40,50,1);
  G.addEdge("to Standby",40,71,1);
  G.addEdge("to View options 11",40,75,1);
  G.addEdge("to Show own number",75,70,1);
  G.addEdge("to Memory selection",75,41,1);
  G.addEdge("to Memory functions",75,40,1);
  G.addEdge("to Memory status",41,42,1);
  G.addEdge("to Show own number",41,70,1);
  G.addEdge("to Memory functions",41,40,1);
  G.addEdge("to Copy between memories",42,18,1);
  G.addEdge("to Memory selection",42,41,1);
  G.addEdge("to Memory functions",42,40,1);
  G.addEdge("to Memory erasing options",18,39,1);
  G.addEdge("to Memory status",18,42,1);
  G.addEdge("to Memory functions",18,40,1);
  G.addEdge("to Show own number",39,70,1);
  G.addEdge("to Copy between memories",39,18,1);
  G.addEdge("to Memory functions",39,40,1);
  G.addEdge("to Memory selection",70,41,1);
  G.addEdge("to Memory erasing options",70,39,1);
  G.addEdge("to Memory functions",70,40,1);
  G.addEdge("to In-call options",55,30,1);
  G.addEdge("to Memory functions",55,40,1);
  G.addEdge("to Standby",55,71,1);
  G.addEdge("to View options 12",55,76,1);
  G.addEdge("to Countdown timer",76,19,1);
  G.addEdge("to Welcome note",76,86,1);
  G.addEdge("to Personal reminders",76,55,1);
  G.addEdge("to Countdown timer",86,19,1);
  G.addEdge("to Countdown timer",86,19,1);
  G.addEdge("to Personal reminders",86,55,1);
  G.addEdge("to Welcome note",19,86,1);
  G.addEdge("to Welcome note",19,86,1);
  G.addEdge("to Personal reminders",19,55,1);
  G.addEdge("to FAX or data call",30,29,1);
  G.addEdge("to Personal reminders",30,55,1);
  G.addEdge("to Standby",30,71,1);
  G.addEdge("to Ringing options",29,62,1);
  G.addEdge("to In-call options",29,30,1);
  G.addEdge("to Standby",29,71,1);
  G.addEdge("to Number editor",62,51,1);
  G.addEdge("to FAX or data call",62,29,1);
  G.addEdge("to Standby",62,71,1);
  G.addEdge("to Recent calls",51,60,1);
  G.addEdge("to Ringing options",51,62,1);
  G.addEdge("to Standby",51,71,1);
  G.cpt(0);
}

Converted by Mathematica      August 13, 2002