Word ladder with both weighted and unweighted edges

word_ladder.py

import string
import sys
from sets import Set
class Node :
    
    def __init__(self, word) :
        self.value = word
        self.neighbors = []
        self.weight = sys.maxint
        self.visited = False
        self.parent = None
        
    def addNeighbor(self, neighbor, cost) :
        self.neighbors.append((neighbor, cost))
        
    def printNode(self) :
        print "Node is {} \n and neighbors are {}".format(self.value, [x[0].value for x in self.neighbors])
    def returnNeighbors(self) : 
        return [ x[0].value for x in self.neighbors]
    def returnNeighborsNode(self) : 
        return [ x[0] for x in self.neighbors]
        
        

def createGraph(sourceWord, targetWord, costs, dictList, anagramDict ) :
    seenDict = {}
    headNode = Node(sourceWord)
    seenDict[sourceWord] = headNode
    nodeList = [ headNode ]
    ctr = 0
    while nodeList :
        # print ctr
        # ctr = ctr + 1
        permute(nodeList, costs, dictList, seenDict, anagramDict)
    return headNode
    
        
def permute(nodeList, costs, dictList, seenDict, anagramDict) :
    node = nodeList.pop(0)
    alphabets = list(string.ascii_lowercase)
    #add/delete/change
    for i in xrange( len(node.value) + 1) :
        for letter in alphabets :
            test_word_add = node.value[ : i ] + letter + node.value[ i : ]
            
            if i < len(node.value) : #avoiding the last letter case
                test_word_delete = node.value[ : i ] + node.value[ i+1 : ]
                test_word_change = node.value[ : i ] + letter + node.value[ i+1 : ]
            
            if sanitizeWord(test_word_add, node) and test_word_add in dictList :
                test_word = addtoVisitedNode(nodeList, test_word_add, seenDict)
                node.addNeighbor( test_word, costs["add"])
            
            if i < len(node.value) : #avoiding the last letter case
            
                if sanitizeWord(test_word_delete, node) and test_word_delete in dictList :
                    test_word = addtoVisitedNode(nodeList, test_word_delete, seenDict)
                    node.addNeighbor( test_word, costs["delete"])
            
            
                if sanitizeWord(test_word_change, node) and test_word_change in dictList :
                    test_word = addtoVisitedNode(nodeList, test_word_change, seenDict)
                    node.addNeighbor(test_word, costs["change"])
            
    
    anagramList = anagramDict["".join(sorted(node.value))]
    for word in anagramList :
        test_word = addtoVisitedNode(nodeList, word, seenDict)
        node.addNeighbor( test_word, costs["anagram"])
            
    return node.returnNeighborsNode()
        
def sanitizeWord(word, sourceNode) :
    if word == sourceNode.value : 
        return False
    for n,c in sourceNode.neighbors :
        if word == n.value :
            return False
    return True
    
def addtoVisitedNode(nodeList, word, seenDict) :
    if word not in seenDict :
        test_word = Node(word)
        seenDict[word] = test_word
        nodeList.append(test_word)
    else :
        test_word = seenDict[word]
    return test_word
    
def BFS(node, targetWord) :
    node.visited =  True
    queue = [node]
    found = False
    while queue :
        node = queue.pop(0)
        # print "Node : {} neighbors : {}".format(node.value, node.returnNeighbors())
        for n,c in node.neighbors :
            if n.visited is False :
                n.visited = True
                n.parent = node
                queue.append(n)
                if n.value == targetWord :
                    found = True
                    break
        if found : break
        
    if found :    
        returnAnswer = []
        total_cost = 0
        while n is not None :
            returnAnswer.append(n.value)
            temp = n
            n = n.parent
            if n is not None :
                for neighbor,cost in n.neighbors :
                    if neighbor == temp :
                        total_cost += cost
                        break
        return total_cost, returnAnswer
    else :
        return None


def Dijkstra(node, targetWord) :
    node.weight = 0
    
    minList = [node]
    while minList :
        node_consideration = minList.pop(0)
        print "working for :", node_consideration.value
        node_consideration.visited = True
        if node_consideration.value == targetWord :
            return node_consideration.weight
        for n,c in node_consideration.neighbors :
            if n.visited is False :
                n.weight = min(n.weight, node_consideration.weight + c   )
                if n not in minList :
                    minList.append(n)
        minList.sort(key=lambda every_node: every_node.weight)
    return -1
            
        
    

        
if __name__ == "__main__" :
    dictList = []
    anagramDict = {}
    for line in sys.stdin :
        word = line.strip()
        if len(word) < 3 :
            continue
        dictList.append(word)
        anaWordGram = "".join(sorted(word))
        if anaWordGram in anagramDict :
            anagramDict[anaWordGram].append(word)
        else :
            anagramDict[anaWordGram] = [word]
        
    dictSet = Set(dictList) #for speed optimization
    dictList = None #release memory
    costs = {"add" : 1, "delete" : 3, "change" : 1, "anagram" : 5  }
    sourceWord = "team"
    targetWord = "mate"
    # dictList = [ "health", "heath", "heats", "hents", "hends", "hands"  ]
    headNode = createGraph(sourceWord, targetWord, costs, dictSet, anagramDict)
    dictSet = None  #release memory
    anagramDict = None #release memory
    print "Graph creation complete"
    total_cost, ans = BFS(headNode, targetWord)
    if ans is not None :
        print total_cost, list(reversed(ans))
    else :
        print "no solution found"
    
    # total_cost = Dijkstra(headNode, targetWord)
    # print total_cost