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.
