(!****************************************************** Mosel User Guide Example Problems ================================= file eulerfct.mos ````````````````` Constructing a Eulerian circuit (a closed circuit that uses every given arc exactly once). - Working with lists - - Model version using subroutines - (c) 2008 Fair Isaac Corporation author: S. Heipcke, Oct. 2006 *******************************************************!) model "Eulerian circuit" forward function find_unused(J: list of integer):integer forward function add_loop(node:integer, J: list of integer):integer declarations NODES = 1..12 ! Set of nodes UNUSED: array(NODES) of list of integer TOUR: list of integer end-declarations initializations from 'euler.dat' UNUSED end-initializations ct:=sum(i in NODES) getsize(UNUSED(i)) ! Main loop of the Eulerian circuit algorithm TOUR:=[1] ! Choose node 1 as start point ct-=add_loop(1,TOUR) ! Construct a closed tour from node 1 while(ct>0) ! While there are unused arcs: ct-=add_loop(find_unused(TOUR),TOUR) ! Add new closed subtours to main tour writeln("Tour: ", TOUR) ! Print the result !----------------------------------------------------------------- ! Find first node in list (tour) with unused outgoing arc(s) function find_unused(J: list of integer):integer returned:=0 forall(i in J) if UNUSED(i) <> [] then returned:=i break end-if end-function !----------------------------------------------------------------- ! Add a subtour to the main tour function add_loop(node:integer, J: list of integer):integer declarations NEWJ, TAIL: list of integer end-declarations ! Insertion position (first occurrence of 'node' in list J) pos:= findfirst(J,node) ! Construct a new subtour cur:=node ! Start with current node while(UNUSED(cur) <> []) do NEWJ+=splithead(UNUSED(cur),1) ! Take first unused arc cur:=getlast(NEWJ) ! End point of arc is new current node end-do ! Stop if the subtour is not a closed loop (=> no Eulerian circuit) if cur<>node then ! Compare start and end of subtour writeln("Tour cannot be closed") exit(1) end-if ! Add the new subtour to the main journey TAIL:=splittail(J, -pos) ! Split off the tail from main tour J += NEWJ + TAIL ! Attach subtour and tail to main tour returned:=getsize(NEWJ) end-function end-model