E
E
energizer8882019-03-13 16:08:31
Python
energizer888, 2019-03-13 16:08:31

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

Code responsible for testing:
#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

1 answer(s)
I
Ilya Korol, 2019-07-16
@welcome32

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 question

Ask a Question

731 491 924 answers to any question