Eulertouren finden - eine ereignisgesteuerte Animation


Abstract

Program EulerAnim demonstrates by means of event-driven animation how Euler tours can be found. First , the use of the program is described. Then some important aspects of the implementation are discussed.   The workbook containing the animation can be downloaded free of charge.

 


Zusammenfassung

Das Programm EulerAnim  demonstriert mit Hilfe einer ereignisgesteuerten Animation, wie Eulertouren gefunden werden können.  Es wird beschrieben, wie das Programm benutzt werden kann. Außerdem werden die wichtigsten Aspekte der Implementierung erörtert.  Die Arbeitsmappe mit der Animation kann kostenlos heruntergeladen werden.

 



 

Die Arbeitsmappe EulerAnim enthält eine ereignisgesteuerte Animation des Hierholzer-Algorithmus zur Zusammenstellung einer Eulertour in einem Graphen.  Der Benutzer kann anhand eines in der Arbeitsmappe enthaltenen Beispiels, aber auch mit Hilfe von ihm selbst eingegebener Graphen, Schritt für Schritt verfolgen, wie Eulertouren gefunden werden.


Im Folgenden wird zunächst erklärt, was eine Eulertour ist. Danach sollte eigentlich der Algorithmus beschrieben werden. Da aber bereits eine ausführliche Beschreibung auf dieser Homepage vorhanden ist, wird nur auf jene Beschreibung verwiesen.


Anschließend wird erläutert, wie man das Programm benutzt. Anhand einer Bilderserie wird gezeigt, wie sich die Animation dem Benutzer präsentiert.


Zum Schluss wird noch auf einige Aspekte der Realisierung eingegangen. Insbesondere wird demonstriert, wie mit Hilfe der Ereignissteuerung die Informationen gewonnen werden, welche dem Benutzer im Animationsgraphen gezeigt werden.


Ganz am Ende des Textes befindet sich eine Möglichkeit zum Herunterladen der Mappe.

 




Was ist eine Eulertour?


Eine Eulertour ist ein Weg durch einen Graphen, bei dem jede Kante (Verbindungslinie) genau einmal befahren wird und der an dem Knoten endet, bei dem er beginnt.


Nicht bei jedem Graph ist eine solche Tour möglich. Eine wichtige Voraussetzung für die Möglichkeit einer Eulertour ist, dass alle Knoten einen geradzahligen Grad haben müssen. Der Grad eines Knotens ist die Anzahl der Verbindungslinien, die sich dort treffen.


Wenn diese Voraussetzung gegeben ist, gibt es nicht nur eine mögliche Eulertour, sondern mehrere, manchmal sogar sehr viele. Insbesondere kann jeder Knoten Ausgangspunkt für eine solche Tour sein.

Betrachten wir den unten stehenden Graphen. Jeder der zehn Knoten hat als Grad eine gerade Zahl. Manche der Knoten, wie z.B. die Knoten 10 und 6, besitzen den Grad 2, andere, wie die Knoten 7, 8 und 5, haben den Grad 4. Eulertouren sollten also möglich sein.



Eine dieser Touren ergibt sich, wenn wir gleich den obersten Knoten, also die Nummer 10, als Startpunkt nehmen und in der unten angegebenen Reihenfolge durchlaufen. Natürlich könnten wir genau so gut den umgekehrten Weg nehmen.



































10

7

4

1

3

2

5

3

4

6

7

8

5

9

8

10



































 

Es existieren mehrere Algorithmen, welche zur Suche nach Eulertouren verwendet werden können. Einer der bekanntesten ist der Hierholzer-Algorithmus, der auch dieser Animation zugrunde liegt. Sie finden eine detaillierte Beschreibung des Algorithmus auf dieser Homepage unter Excel-VBA | Anwendungsbeispiele | Eulertour, zusammen mit einer VBA-Klasse, welche zur Ermittlung von Eulertouren benutzt werden kann. 



 

Die Benutzung des Animationsprogramms


Die Benutzerführung ist in englischer Sprache. Allerdings kann man mit dem Programm auch zurechtkommen, wenn man nur rudimentäre Kenntnisse des Englischen besitzt.

Die Arbeitsmappe EulerAnim enthält drei Arbeitsblätter:


  • Arbeitsblatt StartAnimation enthält eine Schaltfläche zum Starten der Animation. Neben dieser Schaltfläche befindet sich eine kurze Erläuterung des Programms in englischer Sprache (s. nächstes Bild).
  •  Arbeitsblatt sampleInput enthält Beispieldaten in Form zweier Tabellen (s. übernächstes Bild). Die linke Tabelle ist die Layouttabelle. Sie enthält die (x, y)-Koordinaten der Knoten, die sich im Graphen befinden. Die rechte Tabelle ist eine Adjazenzmatrix. In ihr ist festgelegt, welche Verbindungen es zwischen den Knoten des Graphen gibt. Man kann diese Tabellen zum Ausprobieren des Programms oder als Vorlage für eigene Datentabellen benutzen.
  • Arbeitsblatt Euler ist anfangs leer.  Lässt man die Animation laufen, so erscheint auf diesem Arbeitsblatt die Animationsgraphik.  Anhand der Graphik kann der Benutzer Schritt für Schritt den Aufbau der Eulertour verfolgen. Nach dem Animationslauf bleibt die Graphik mit der kompletten Tour auf dem Arbeitsblatt. Erst wenn der Benutzer eine neue Animation startet und hierfür ebenfalls das Arbeitsblatt Euler für die Ausgabe wählt, wird die Graphik gelöscht.

 



 

Klickt der Benutzer auf die Schaltfläche „Start Animation“ so erscheint ein kleines Formular, das der Eingabe der Animationsparameter dient. Diese sind:


  •  Der Arbeitsblattbereich, in dem sich die Layouttabelle befindet. Die Eingabe kann durch Selektieren mit der Maus erfolgen. Die Tabellenüberschrift wird dabei nicht einbezogen.     
  • Der Bereich, in dem sich die Adjazenzmatrix befindet. Auch hier gilt: die Eingabe geschieht am besten durch Selektion mit der Maus. Spalten- und Zeilenbeschriftungen werden nicht einbezogen.     
  • Der Name des Arbeitsblatts, auf dem die Animation dargestellt werden soll. Standardmäßig wird hier der Name Euler vorgeschlagen. Sie können diesen Namen durch einen selbstgewählten ersetzen. Falls ein Arbeitsblatt dieses Namens noch nicht in der Arbeitsmappe existiert, so wird es vom Programm vor der Durchführung der Animation angelegt.


Wenn die Eingaben komplett sind, klickt man auf die Schaltfläche „ Load graph data“.  Das Programm liest nun die Daten ein und überprüft (validiert) sie.

 


 

Nach erfolgreicher Validierung präsentiert sich das Formular in leicht verändertem Zustand (Bild unten).

Das Eingabefeld für das Arbeitsblatt zur Ausgabe ist weiterhin zugänglich. Der Benutzer kann den Namen auch in dieser Phase noch ändern. Ebenfalls zugänglich ist nun das Auswahlfeld zur Wahl des Startknotens zugänglich. Standardmäßig ist dieses Feld mit der höchsten Knotennummer vorbesetzt, welche vom Programm im Graphen gefunden wurde.


Die Schaltfläche zum Laden der Daten ist jetzt deaktiviert, die zum Ausführen der Animation („Draw graph and Euler tour“) ist aktiviert. Sobald die Eingaben komplett sind, kann der Benutzer das Formular durch Klicken auf diese Schaltfläche abschicken.

 

 

Das Programm aktiviert nun das Arbeitsblatt, auf dem sich die Animationsgraphik befindet. Es kann sein, dass die Graphik durch das Formular teilweise verdeckt ist. In diesem Fall genügt es, das Formular mit Hilfe der Maus etwas zur Seite zu schieben.


Anhand der Graphik kann der Benutzer nun Schritt für Schritt verfolgen, wie die Eulertour aufgebaut wird. Die einzelnen Subtouren (s.Algorithmusbeschreibung auf dieser Homepage unter Excel-VBA | Anwendungsbeispiele | Eulertour) sind dabei durch unterschiedliche Farben der Pfeile unterschieden. Die erste Subtour ist immer rot, die zweite blau, die dritte gelb, usw.

 

 

Der Graph mit der eingezeichneten Eulertour bleibt am Ende auf dem Arbeitsblatt stehen, so dass der Benutzer diese in Ruhe studieren kann. Da von einzelnen Knoten auch mehrere Pfeile abgehen können, kann man aus den Pfeilen alleine manchmal nicht auf den ersten Blick den Tourverlauf ersehen.  Aus diesem Grund ist rechts der Graphik der Verlauf der gesamten Tour als Folge von Knotennummern angegeben (von oben nach unten zu lesen).

 

 

 


 

Das Animationsprogramm: Aspekte der Realisierung


Bei der hier beschriebenen Eulertour-Animation handelt es sich um eine ereignisgesteuerte Animation. Das Prinzip ist einfach (s. „Ereignisgesteuerte Animation“ auf dieser Homepage):


Bei der Durchführung des Algorithmus werden an den entscheidenden Stellen Ereignisse ausgelöst, welche von einem anderen Modul aufgefangen und in eine bildliche Darstellung umgesetzt werden.


Das Programm besitzt eine dreischichtige Architektur (s. Bild unten). Die Formularklasse EulerForm verkörpert die Benutzerschnittstelle (UI). Sie erlaubt die Kommunikation zwischen dem Programm und dem Benutzer und ermöglicht diesem, die Parameter einzugeben.


EulerForm gibt diese Parameter an ein Objekt der Klasse EulerAnimator weiter und betraut dieses Objekt damit, die Animation durchzuführen.  Das EulerAnimator-Objekt erfüllt diesen Auftrag, indem es ein Objekt der Klasse Eulertour mit der Durchführung des Algorithmus beauftragt, welcher die Eulertour für die vom Benutzer eingegebenen Parameter ermittelt. Während dieser Durchführung werden im Eulertour-Objekt an den entscheidenden Stellen Ereignisse ausgelöst, die vom EulerAnimator-Objekt aufgefangen und in der Animationsgraphik angezeigt werden. Zum Zeichnen der Animationsgraphik nimmt das EulerAnimator-Objekt die Dienste eines Objekts der Graphikklasse lgraph in Anspruch.

 


Wir betrachten nun im Detail, wie das Prinzip der ereignisgesteuerten Animation den beiden Kernklassen EulerAnimator und Eulertour realisiert ist. Wir beginnen auf der untersten Ebene, also bei der Klasse Eulertour.


Die hier verwendete Animationsversion der Klasse unterscheidet sich von der normalen Version (s. Eintrag Excel-VBA | Anwendungsbeispiele | Eulertour) nur in einem Aspekt: Es wurden für die entscheidenden Stellen des Algorithmus Ereignisse definiert  und in den Code Anweisungen eingefügt, welche diese Ereignisse auslösen. Im unten stehenden Code sind diese Zusätze durch grüne Schrift hervorgehoben.


Zwei Ereignisse wurden definiert:


  • Ereignis newSubtour tritt ein, wenn innerhalb der Ermittlung der Gesamttour eine neue Subtour begonnen wird.
  • Ereignis nextNodeFound wird ausgelöst, wenn innerhalb der Zusammenstellung einer Subtour der nächste Knoten gefunden wurde, der angelaufen werden soll.


Die Anweisungen, welche diese Ereignisse auslösen (RaiseEvent …), befinden sich in den Funktionen tour und subtour.


 

‘----------------------------

‘class Eulertour

‘animation version

‘-----------------------------

 

 

Private a() As Integer               'adjacency matrix of the graph

Private t() As Integer                'node sequence of the tour

Private numNodes As Integer    'number of nodes

 

Public Event newSubtour(ByVal start As Integer)

Public Event nextNodeFound(ByVal nxt As Integer)

 

 

'accepts the adjacency matrix of the graph, checks whether it is

'eulerian and, if so, stores it in a; calculates numNodes

'------------------------------------------------------------------------------------------

Public Function setGraph(ByRef c() As Integer) As Boolean

    If isEulerian(c) Then

        a = c

        numNodes = UBound(c, 1)

        setGraph = True

    Else

        setGraph = False

    End If

End Function

 

 

'checks whether the graph given by adjacency matrix m is eulerian

'----------------------------------------------------------------------------------------------

Public Function isEulerian(ByRef m() As Integer) As Boolean

    isEulerian = True

    Dim i As Integer, j As Integer, d As Integer

   

    If UBound(m, 1) < 3 Then

        isEulerian = False

    Else

        For i = 1 To UBound(m, 1)

            d = 0

            For j = 1 To UBound(m, 2)

                d = d + m(i, j)

            Next j

            If d = 0 Or d Mod 2 <> 0 Then

                isEulerian = False

                Exit Function

            End If

        Next i

    End If

End Function

 

 

'calculates the current degree of a node

'--------------------------------------------------------

Private Function numCons(ByVal node As Integer) As Integer

    Dim i As Integer

    numCons = 0

    For i = 1 To numNodes

        numCons = numCons + a(node, i)

    Next i

End Function

 

 

'checks if there are still edges in the graph,

'i.e. edges which have not been deactivated

'--------------------------------------------------------------

Private Function edgesAvailable() As Boolean

    Dim i As Integer, j As Integer, sum As Integer

    edgesAvailable = False

    sum = 0

    For i = 1 To numNodes

        For j = 1 To numNodes

            sum = sum + a(i, j)

        Next j

    Next i

    edgesAvailable = sum > 0

End Function

 

 

'composes an Euler tour starting from sNode

'---------------------------------------------------------------

Public Function tour(ByVal sNode As Integer) As Integer()

    Dim i As Integer

    Dim wpos As Integer  'position in t where next subtour will start

    Dim s() As Integer   'subtour nodes without start node

   

    Erase t

    ReDim t(1 To 1)

    t(1) = sNode

    wpos = 1

    RaiseEvent newSubtour(sNode)

    s = subtour(t(1))

    embed s, wpos

   

    Do While edgesAvailable

        wpos = searchWpos()

        RaiseEvent newSubtour(t(wpos))

        s = subtour(t(wpos))

        embed s, wpos

    Loop

   

    tour = t

End Function

 

 

'creates a subtour, starting and ending at node from; the result

'array does not contain start node (= from)

'-----------------------------------------------------------------------------------------

Public Function subtour(ByVal from As Integer) As Integer()

    Dim st() As Integer, num As Integer, nodeFree As Boolean

    Dim nxt As Integer, curr As Integer

    num = 0

    nodeFree = True

    curr = from

    Do While nodeFree

        nxt = nxtnode(curr)

        RaiseEvent nextNodeFound(nxt)

        If nxt = -1 Then

            ReDim st(-1 To -1)

            Exit Do

        End If

        If nxt = from Then nodeFree = False  'returned to start

        num = num + 1

        ReDim Preserve st(1 To num)

        st(num) = nxt

        a(curr, nxt) = 0                     'deactivate edge

        a(nxt, curr) = 0

        curr = nxt

    Loop

    subtour = st

End Function

 

 

'searches a node which is reachable from node from;

'gives -1 if there is no such node

'---------------------------------------------------------------------------

Private Function nxtnode(ByVal from As Integer) As Integer

    Dim i As Integer

    nxtnode = -1

    For i = 1 To numNodes

        If a(from, i) = 1 Then

            nxtnode = i

            Exit For

        End If

    Next i

End Function

 

 

'search starting node for the next subround

'-------------------------------------------------------------

Private Function searchWpos() As Integer

    Dim i As Integer

    For i = 1 To UBound(t) - 1

        If numCons(t(i)) > 0 Then

            searchWpos = i

            Exit Function

        End If

    Next i

    searchWpos = -1

End Function

 

 

'embeds subtour s into tour array t after position behindPos

'------------------------------------------------------------------------------------

Private Sub embed(ByRef s() As Integer, ByVal behindPos As Integer)

    Dim oldlength  As Integer

    Dim i As Integer

    oldlength = UBound(t)

    ReDim Preserve t(1 To oldlength + UBound(s))

   

    'make way for the subtour

    For i = oldlength To behindPos + 1 Step -1

        t(i + UBound(s)) = t(i)

    Next i

   

    'inserting nodes of subtour

    For i = 1 To UBound(s)

        t(i + behindPos) = s(i)

    Next i

End Sub

 

 

Es folgt nun der Code der Klasse EulerAnimator. Auch hier sind die Passagen, welche die Ereignissteuerung betreffen, durch Grünschrift hervorgehoben.


Die zentrale Routine ist die Prozedur doAnimation. Diese Prozedur empfängt alle wesentlichen Parameter vom UI und steuert die Animation. Insbesondere bereitet sie durch einige Aufrufe des Graphikklassenobjekts g die Animationsgraphik vor und löst später durch den Aufruf  der Funktion tour des Eulertour-Objekts et die Ermittlung der Eulertour an.


Beachten Sie, dass doAnimation die Ergebnisse des Aufrufs von tour nicht verwerten muss. Die Informationen, welche für die Fortschreibung der Animationsgraphik notwendig sind, werden auf anderem Wege gewonnen, nämlich durch das Auffangen der Ereignisse, welche bei der Ausführung der Eulertourermittlung  ausgelöst werden.


Dass diese Ereignisse aufgefangen und ausgewertet werden, dafür sorgen die beiden Ereignisprozeduren newSubtour und nextNodeFound. Sie nehmen die mit den Ereignissen verbundenen Informationen auf und geben dem Graphikklassenobjekt g die notwendigen Aufträge für die daraus resultierenden Änderungen in der Animationsgraphik.


 

'-------------------------------------

'class EulerAnimator

‘-------------------------------------

'uses classes lgraph, Eulertour

 

Private WithEvents et As Eulertour   'calculation of the tour

Private g As lGraph                         'simple drawing tool

Private colour() As String                 'possible colors

Private currColor As Integer              'current color

Private fromNode As Integer             'current node of depart

Private dur As Single                       'time between moves

 

 

'controls the animation

'---------------------------------------------

'n:            array of node co-ordinates

'c:            adjacency matrix of the graph

'start:       no of node where tour starts

'r:             range where graph will be displayed

'duration:  time between moves

'---------------------------------------------

Public Sub doAnimation(ByRef n() As Single, _

                       ByRef c() As Integer, _

                       ByVal start As Integer, _

                       ByVal r As Range, _

                       ByVal duration)

    Dim i As Integer

    Dim t() As Integer                     'for nodes sequence of tour

    Set g = New lGraph                  'will draw the graph

    Set et = New Eulertour              'will calculate tour

    dur = duration                           'time between moves

    setColours                               'define color sequence

    currColor = 1                            'this is "black"

   

    'prepare graph & display before tour

    g.lGraphIni r, n

    g.addConnections c

    delay 5

    g.changeNode nodeNo:=start, weight:=2  'highlights starting node

   

    'calculate tour

    et.setGraph c

    t = et.tour(start)

   

    'write node sequence of tour to the right of the graph

    r.Cells(1, r.Columns.Count).Offset(0, 1).HorizontalAlignment = xlRight

    r.Cells(1, r.Columns.Count).Offset(0, 1).Value = "Tour"

    For i = 1 To UBound(t)

        r.Cells(1, r.Columns.Count).Offset(i, 1).Value = t(i)

    Next i

   

End Sub

 

 

 

'fills array of colors; order determines colors sequence

'-----------------------------------------------------------------------------

Private Sub setColours()

    ReDim colour(1 To 10)

    colour(1) = "black"

    colour(2) = "red"

    colour(3) = "blue"

    colour(4) = "orange"

    colour(5) = "green"

    colour(6) = "yellow"

    colour(7) = "magenta"

    colour(8) = "darkred"

    colour(9) = "lightblue"

    colour(10) = "lightgreen"

End Sub

 

 

 

'event procedure: executed when a new subtour begins

'-------------------------------------------------------------------------------

Private Sub et_newSubtour(ByVal start As Integer)

    currColor = currColor + 1

    delay dur

    fromNode = start

End Sub

 

 

 

'event procedure: executed when the next destination

'has been identified within a subtour

'-----------------------------------------------------------------------------

Private Sub et_nextNodeFound(ByVal nxt As Integer)

    g.replaceCon fromNode, nxt, colour(currColor), "arrow", 2.5

    delay dur

    fromNode = nxt

End Sub

 

 

 

'causes a delay

'---------------------

Private Sub delay(ByVal duration As Single)

    Dim t As Single

    t = Timer

    Do While Timer < t + duration

        DoEvents

    Loop

End Sub

 

 

Download


Sie können die Arbeitsmappe mit dem beschriebenen Animationsprogramm kostenlos herunterladen und benutzen.  Der Code ist allerdings durch ein Passwort geschützt.


EulerAnim.zip
Komprimiertes Archiv im ZIP Format 80.1 KB