' One stroke solver 0.2
' Copyright (c) 2012 Nonki Takahashi. All rights reserved.
'
' History :
' 0.2 2012/08/24 Renamed MAG to SCALE.
' 0.1 2012/07/11 Created.
'
' Constant definition
X0 = 100
Y0 = 100
SCALE = 50
' Main
GraphicsWindow.Title = "One stroke solver 0.2"
InitVertexes()
InitEdges()
DrawGraph() ' draw graph and count edges for each vertex
Turtle.Show()
FindOddVertex()
If error = "" Then
If found = "False" then
v1 = 1
EndIf
FindOneStrokePath()
If error = "" Then
MoveTurtle()
Else
ShowError()
EndIf
Else
ShowError()
EndIf
' End of main
Sub DrawGraph
' param v[] - vertexes of graph
' param e[][] - edges of graph
' return ne[] - number of edges for each vertex
' return emax - number of total ledges in graph
GraphicsWindow.PenColor = "LightGray"
GraphicsWindow.BrushColor = "Green"
ne = ""
emax = 0
For i = 1 To vmax
xi = X0 + SCALE * v[i]["x"]
yi = Y0 + SCALE * v[i]["y"]
For j = 1 To vmax
xj = X0 + SCALE * v[j]["x"]
yj = Y0 + SCALE * v[j]["y"]
If e[i][j] Then
GraphicsWindow.DrawLine(xi, yi, xj, yj)
ne[i] = ne[i] + 1
ne[j] = ne[j] + 1
emax = emax + 1
EndIf
EndFor
GraphicsWindow.DrawText(xi, yi, i)
EndFor
EndSub
Sub FindAdjacentVertex
' param e2[] - edges of graph
' param i - current index of vertex
' param j - start index to find adjacent vertex
' return j - adjacent vertex
' return found - "True" if found
found = "False"
For j = j To vmax
If e2[i][j] Then
e2[i][j] = ""
found = "True"
Goto fav_exit
ElseIf e2[j][i] Then
e2[j][i] = ""
found = "True"
Goto fav_exit
EndIf
EndFor
fav_exit:
EndSub
Sub FindOddVertex
' param ne[] - number of edges for each vertex
' return v1, v2 - index of vertexes which have odd number of edges
' return found - "True" if found
' return error - error message ("" if no error)
v1 = 0
v2 = 0
For i = 1 To vmax
If Math.Remainder(ne[i], 2) = 1 Then
If v1 = 0 Then
v1 = i
ElseIf v2 = 0 Then
v2 = i
Else
v1 = -1
v2 = -1
EndIf
EndIf
EndFor
If v1 > 0 And v2 > 0 Then
found = "True"
error = ""
ElseIf v1 = 0 And v2 = 0 Then
found = "False"
error = ""
ElseIf v1 < 0 And v2 < 0 Then
found = "False"
error = "Error(1): More than three odd vertexes"
Else
found = "False"
error = "Error(2): Unknown v1=" + v1 + " v2=" + v2
EndIf
EndSub
Sub FindOneStrokePath
' return p[] - one stroke path (array of vertex)
' return error - error message ("" if no error)
error = ""
e2 = e ' copy edges to check remaining
n = 1 ' number of vertex in one stroke path
i = v1 ' current index of vertex
p[n] = i
j = 1 ' start index to find adjecent vertex
While e2 <> ""
FindAdjacentVertex()
If found Then
n = n + 1
i = j
p[n] = i
j = 1 ' start index to find adjecent vertex
Else
' Backtruck
j = p[n]
i = p[n - 1]
p[n] = "" ' remove last vertex in one stroke path
n = n - 1
If n <= 0 Then
error = "Error(3): One stroke path not found " + p
Goto fosp_exit
EndIf
e2[i][j] = "True" ' restore last edge to remaining edges
j = j + 1 ' next start index to find adjecent vertex
If j > vmax Then
error = "Error(4): One stroke path not found " + p
Goto fosp_exit
EndIf
EndIf
EndWhile
fosp_exit:
EndSub