01.in

5 7
5
3
16
2
0
0 1 3
0 2 1
0 3 6
1 3 2
1 4 7
2 3 15
3 4 2

astar.py

import os
from collections import deque
from util.node import node
from util.path import path
from sortedcontainers import SortedList

def read_inputfile(filename):
    with open(filename) as f:
        content = f.read().splitlines()
    #variables for our representation
    dimensions=list() # nodes,edges
    heuristics=list() # for node 0-n
    edges ={} # for node 0-n: node:[from,to,cost]
    nodes=list()
    paths=list()
    #splitting
    for i in range(0,len(content)):
        if 0==i:
            dimensions=content[i].split(" ")
        else:
            if i>0 and i<1+int(dimensions[0]):
                number = int(content[i])
                heuristics.append(number)
                nodes.append(node(i-1,number,-1))
            else:
                split=content[i].split(" ")
                sourceIndex=int(split[0])
                destinationIndex = int(split[1])
                cost=int(split[2])

                paths.append(path(nodes[sourceIndex],nodes[destinationIndex],cost))
    return dimensions, nodes, paths

def goalCheck(currentNode,targetNode):
    if currentNode.id==targetNode.id:
        return True
    else:
        return False

def getConnectedNodes(currentNode,paths):
    connectedNodes=list()
    for path in paths:
        if(currentNode.id == path.source.id):
            node=path.destination.copy()
            node.setParent(currentNode)
            node.f=path.cost+node.heuristic
            connectedNodes.append(node)
    return connectedNodes

def findSolution(endNode):
    solution=list()
    node=endNode
    while True:
        solution.append(node.id)
        if(node.parent==None):
            solution.reverse()
            return solution
        node=node.parent

def dfs(startingNode,targetNode,paths):
    closed=list()
    fringe=list()
    fringe.append(startingNode)

    while True:
        if(len(fringe)==0):
            return None
        node=fringe.pop(0)
        if not any(node.id == it.id for it in closed):
            print("Current Node= {}, Fringe={}".format(node,fringe))
            if(goalCheck(node,targetNode)):
                return findSolution(node) #getPath method loop from the goal back to the starting node
            else:
                connectedNodes=getConnectedNodes(node,paths)
                fringe[:0]=connectedNodes
                closed.append(node)
        else:
            print("skipped node={}".format(node))

def bfs(startingNode,targetNode,paths):
    closed=list()
    fringe=list()
    fringe.append(startingNode)

    while True:
        if(len(fringe)==0):
            return None
        node=fringe.pop(0)
        if not any(node.id == it.id for it in closed):
            print("Current Node= {}, Fringe={}".format(node,fringe))
            if(goalCheck(node,targetNode)):
                return findSolution(node) #getPath method loop from the goal back to the starting node
            else:
                connectedNodes=getConnectedNodes(node,paths)
                fringe.extend(connectedNodes)
                closed.append(node)
        else:
            print("skipped node={}".format(node))

def a_star(startingNode, targetNode, paths):
    closed=list()
    fringe=SortedList()
    fringe.append(startingNode)

    while True:
        if(len(fringe)==0):
            return None
        node=fringe.pop(0)
        if not any(node.id == it.id for it in closed):
            print("Current Node= {}, Fringe={}".format(node,fringe))
            if(goalCheck(node,targetNode)):
                return findSolution(node) #getPath method loop from the goal back to the starting node
            else:
                connectedNodes=getConnectedNodes(node,paths)
                for tmpNode in connectedNodes:
                    fringe.add(tmpNode)
                #fringe.extend(sorted(connectedNodes))
                closed.append(node)
        else:
            print("skipped node={}".format(node))


(dimensions, nodes, paths)=read_inputfile("in/01.in")
'''file: 01.in
5 7
5
3
16
2
0
0 1 3
0 2 1
0 3 6
1 3 2
1 4 7
2 3 15
3 4 2
'''
print("Got dimensions (nodes,edges) : {}".format(dimensions))
print("Got nodes: {}".format(nodes))
print("Got paths: {}".format(paths))
print("Got BFS Path: {}".format(bfs(nodes[0],nodes[-1],paths)))
print("Got DFS Path: {}".format(dfs(nodes[0],nodes[-1],paths)))
print("Got A* Path: {}".format(a_star(nodes[0],nodes[-1],paths)))

n1=node(0,1,1)
n2=node(1,2,2)
list=SortedList()
list.add(n2)
list.add(n1)
print(list)

node.py

class node:
    def __init__(self, id, heuristic, f):
        self.id=id
        self.heuristic=heuristic
        self.totalCost=0
        self.f=f
        self.parent=None

    def setParent(self,parent):
        self.parent=parent

    def __lt__(self, other):
        return self.f < other.f

    def __repr__(self):
        #return "node:[id={}, heuristic={}, totalCost={}, cost={}, parent={}]".format(self.id,self.heuristic,self.totalCost,self.cost,self.parent)
        if(self.parent != None):
            return "node:[id={}, parentId={}, f={}, heuristic={}]".format(self.id,self.parent.id,self.f, self.heuristic)
        else:
            return "node:[id={}], f={}, heuristic={}]".format(self.id,self.f, self.heuristic)

    def copy(self):
        return node(self.id,self.heuristic,self.f)

path.py

from util.node import node


class path:
    def __init__(self,source,destination,cost):
        self.source=source
        self.destination=destination
        self.cost=cost

    def __repr__(self):
        return "path:[source={}, destination={}, cost={}]".format(self.source,self.destination,self.cost)

explanation of 01.in