Answer the question
In order to leave comments, you need to log in
Why does graph traversal not work?
I did a project on creating and bypassing graphs.
Here is the repository: https://github.com/InfinityFly8/graphCreator.git
Graphs are created but not handled normally. That is, the bypass works with a 90% chance, but sometimes the values \u200b\u200bfrom the recursive function are not returned. The testgraph.py file starts the test. I just don't have access to the debugger right now, which is why I'm asking. The test file has start and end nodes. If the recursion leads to them, then it does not go back, although there are links to other nodes. What is the problem? I wrote the project in half a day, but I have been suffering with this error for the third day. The whole trick is that I am now not at home for a long time, but only my phone is with me. I program in a simple editor and in termux (a full-fledged terminal emulator for android). For study, it's quite normal, but without a debugger it's somehow not right. And yes, I have tried breakpoint().
Code responsible for bypassing:
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")
Answer the question
In order to leave comments, you need to log in
A recursive traversal of the graph is not a good solution, since an error with the number of recursions may result. Try to bypass the graph using a queue. I am sure that with this method there will be no crashes, and it will be possible to get around not in O (n!), but in O (n)
Didn't find what you were looking for?
Ask your questionAsk a Question
731 491 924 answers to any question