@energizer888

Почему не работает обход графа?

Делал проект по созданию и обходу графов.
Вот репозиторий: 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")
  • Вопрос задан
  • 131 просмотр
Пригласить эксперта
Ответы на вопрос 1
welcome32
@welcome32
Backend Python developer
Рекурсивный обход графа не есть хорошее решение, так как может выйти ошибка с количеством рекурсий. Попробуйте обходить граф с помощью очереди. Уверен, при таком способе вылетов не будет, и обойти можно будет не за O(n!), a за O(n)
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы