views:

77

answers:

0

Can you see any immediately changes I can do to increase speed and optimization in the script below?

We are suppose to write a script which implements dfs/bfs searches to find "ratatosk". Input is which function to use (dfs or bfs), number of nodes in the tree, root node, which node "ratatosk" is in and the rest of the node numbers.

from sys import stdin
from collections import deque

True = 1
False = 0

class Node:
    barn = None 
    ratatosk = None
    nesteBarn = None # bare til bruk i DFS
    def __init__(self):
        self.barn = []
        self.ratatosk = False
        self.nesteBarn = 0    

def dfs(rot):
 stack = [ [rot, 0] ]
 while True:
  current = stack.pop()
  if current[0].ratatosk == True:
   return current[1]        
  if len(current[0].barn) > 0 :
   for unge in current[0].barn:
    stack.append([unge, current[1]+1])
 return False


def bfs(rot):
 a = 0;
 onthislevel = 1
 level = 0
 nextlevel = 0
 queue = deque([rot])
 app = queue.append    
 while True:
  current = queue.popleft()
  onthislevel=onthislevel-1
  if current.ratatosk == True:
   return level
  a = len(current.barn) 
  if  a > 0 :
   nextlevel = a+nextlevel
   map(app, current.barn)
  if onthislevel == 0:
   level+=1
   onthislevel = nextlevel
   nextlevel = 0 
 return 1


funksjon = stdin.readline().strip()
antall_noder = int(stdin.readline())
noder = []
nodeappend = noder.append;
for i in range(antall_noder):
    nodeappend(Node())
start_node = noder[int(stdin.readline())]
ratatosk_node = noder[int(stdin.readline())]
ratatosk_node.ratatosk = True
for linje in stdin:
    tall = linje.split()
    temp_node = noder[int(tall.pop(0))]
    temp_node_append = temp_node.barn.append;
    for barn_nr in tall:
        temp_node_append(noder[int(barn_nr)])

if funksjon == 'dfs':
    print dfs(start_node)
elif funksjon == 'bfs':
    print bfs(start_node)
elif funksjon == 'velg':
    print bfs(start_node)