Делал проект по созданию и обходу графов.
Вот репозиторий:
https://github.com/InfinityFly8/graphCreator.git
Графы создаются, но не обходятся нормально. То есть обход срабатывает с шансом 90%, но иногда не возвращаются значения из рекурсивной функции. Файл testgraph.py запускает проверку. Просто я сейчас не имею доступа к отладчику, поэтому и спрашиваю. В проверочном файле есть узлы start и end. Если рекурсия приводит к ним, то обратно не выходит, хотя ссылки на другие узлы есть. В чем проблема? Проект написал за пол дня, но с этой ошибкой мучаюсь уже третий день. Весь фокус в том, что я сейчас надолго не дома, а с собой только телефон. Программирую в простеньком редакторе и в termux (полноценный эмулятор терминала под андроид). Для учебы вполне нормально, но без отладчика как-то не то. И да, я пробовал breakpoint().
Код, ответственный за обход:
def recursiveSearch(f, t, accum):
#return all correct routes
nonlocal chgraph
VAL = 0
VISITED = 1
STACK = 0
SUM = 1
print("%"*7, accum)
#if target in current node's arcs
if t in chgraph[f]["arcs"]:
yield (accum[STACK]+[t], accum[SUM] + chgraph[f]["arcs"][t][VAL])
#if False:
# pass
else:
recstat = []
for arc in chgraph[f]["arcs"]:
#set and check visited flag
if chgraph[f]["arcs"][arc][VISITED]:
continue
#chgraph[f]["arcs"][arc][VISITED] = True
if f in chgraph[arc]["arcs"]:
chgraph[arc]["arcs"][f][VISITED] = True
#search target in child arcs
if t in chgraph[arc]["arcs"]:
yield (accum[STACK] + [arc, t], accum[SUM] + chgraph[f]["arcs"][arc][VAL] + chgraph[arc]["arcs"][t][VAL])
#if arc == t:
# yield (accum[STACK]+[arc], accum[SUM] + chgraph[f]["arcs"][arc][VAL])
else:
recstat.append(arc)
#yield from recursiveSearch(arc, t, (accum[0]+[arc], accum[1] + chgraph[f]["arcs"][arc][STAT] ))
#direct first, recursive last
for rec in recstat:
if len(accum[STACK]) < 2:
print("---New Stack---")
yield from recursiveSearch(rec, t, (accum[STACK]+[rec], accum[SUM] + chgraph[f]["arcs"][rec][VAL] ))
if From == To:
return ([From], 0)
minroute = ([From], None)
for route in recursiveSearch(f=From, t=To, accum=([From], 0)):
print("///", route)
if minroute[1] is None:
minroute = route
elif route[1] < minroute[1]:
minroute = route
else:
continue
return minroute
Код, ответственный за тестирование:
#graphCreator test
import random
from . import graphCreator
testgraph = graphCreator.Graph(int)
testgraph.createNode("start", a=12, b=10, c=13)
testgraph.createNode("a", start=12, b=5, c=11, d=15, e=17, f=20)
testgraph.createNode("b", start=10, a=5, c=6, d=16, e=13, f=17)
testgraph.createNode("c", start=13, a=11, b=6, d=19, e=16, f=20)
testgraph.createNode("d", a=15, b=16, c=19, e=4, f=10, g=27, h=35, i=39)
testgraph.createNode("e", a=17, b=13, c=16, d=4, f=6, g=33, h=24, i=30)
testgraph.createNode("f", a=20, b=17, c=20, d=10, e=6, g=39, h=26, i=40)
testgraph.createNode("g", d=27, e=33, f=39, h=15, i=21, end=52)
testgraph.createNode("h", d=35, e=24, f=26, g=15, i=16, end=48)
testgraph.createNode("i", d=39, e=30, f=40, g=21, h=16, end=50)
testgraph.createNode("end", g=52, h=48, i=50)
graphnodes = testgraph.getGraph()
for node in graphnodes:
print('"%s":\t' % node, graphnodes[node], end = "\n\n\n")
#allnodes = testgraph.getNodeNames()
allnodes = ["start", "start", "a", "b", "c", "g", "h", "i", "end", "end"]
success = 0
for i in range(40):
print("\n" * 2, "#" * 20, "\n" * 2)
startRoute = random.choice(allnodes)
endRoute = random.choice(allnodes)
route = testgraph.routeGraph(startRoute, endRoute)
print("From:", startRoute, sep="\t")
print("To:", endRoute, sep="\t")
print("Way:", " => ".join(route[0]), sep="\t")
print("Sum:", route[1], sep="\t")
if not route[1] is None:
success += 1
print("\n"*3, "###"*5, "###"*5, "Success: " + str(success), sep="\n")
