| |||||||||||||

Eulerian circuit - working with lists Description A Eulerian circuit is a closed circuit that uses every
given arc exactly once. The algorithm is implemented using
the data structure 'list', making use of list operators and list handling routines (splitting off list head or tail, first occurrence of an element). Further explanation of this example:
'Mosel User Guide', Section 8.5 Working with lists
Source Files By clicking on a file name, a preview is opened at the bottom of this page.
Data Files euler.mos (!****************************************************** Mosel User Guide Example Problems ================================= file euler.mos `````````````` Constructing a Eulerian circuit (a closed circuit that uses every given arc exactly once). - Working with lists - (c) 2008 Fair Isaac Corporation author: S. Heipcke, Oct. 2006 *******************************************************!) model "Eulerian circuit" declarations NODES = 1..12 ! Set of nodes UNUSED: array(NODES) of list of integer TOUR: list of integer NEWT, TAIL: list of integer end-declarations initializations from 'euler.dat' UNUSED end-initializations ct:=sum(i in NODES) getsize(UNUSED(i)) TOUR:=[1] ! Choose node 1 as start point while(ct>0) do ! While there are unused arcs: ! Find first node in TOUR with unused outgoing arc(s) node:=0 forall(i in TOUR) if UNUSED(i) <> [] then node:=i break end-if ! Insertion position (first occurrence of 'node' in TOUR) pos:= findfirst(TOUR, node) ! Construct a new subtour starting from 'node' cur:=node ! Start with current node NEWT:=[] while(UNUSED(cur) <> []) do NEWT+=splithead(UNUSED(cur),1) ! Take first unused arc cur:=getlast(NEWT) ! 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(TOUR, -pos) ! Split off the tail from main tour TOUR += NEWT + TAIL ! Attach subtour and tail to main tour ct -= getsize(NEWT) end-do writeln("Tour: ", TOUR) ! Print the result end-model | |||||||||||||

© Copyright 2022 Fair Isaac Corporation. |