Mathematica code for the Directed Chinese Postman Problem

Harold Thimbleby,
UCLIC, UCL Interaction Centre

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


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.


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.


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.)


The paper's simple example


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.


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).


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


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.


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.


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.


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.


Convert Mathematica format to Java

{ 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);

Converted by Mathematica      August 13, 2002