ThirstyShoddyLanservers-2 created by praisethemoon - https://repl.it/@praisethemoon/ThirstyShoddyLanservers-2

main.py

from Tree import Tree, Node
from Search import UniformCostSearch

def runTest1():
  # Example taken from: https://algorithmicthoughts.wordpress.com/2012/12/15/artificial-intelligence-uniform-cost-searchucs/
  S = Node("S")
  A = Node("A") # OK
  B = Node("B") # OK
  C = Node("C") # OK
  D1 = Node("D") # OK
  D2 = Node("D") # OK
  G1 = Node("G1") # OK
  G2 = Node("G2") # OK
  G3 = Node("G3") # OK
  G4 = Node("G4") # OK

  S.addChild(A, 1)
  S.addChild(G1, 12)
  A.addChild(B, 3)
  A.addChild(C, 1)
  B.addChild(D1, 3)
  D1.addChild(G2, 3)
  C.addChild(G3, 2)
  C.addChild(D2, 1)
  D2.addChild(G4, 3)

  tree = Tree(S)

  UniformCostSearch(tree, ["G1", "G2", "G3", "G4"])

  """
  You will get the following output
    #0 -> S w: 0
    #1 -> A w: 1
    #2 -> C w: 2
    #3 -> D w: 3
    #4 -> G3 w: 4

    G3 is actually a child of C, but we see in the visited D because
    the algorithms sorts back the queue and finds that 
    S -> A -> C -> G3 is the shorted path.
  """

if __name__ == "__main__":
  runTest1()

Search.py

"""
Prints the nodes queue,
please note that the queue is actually a stack, sorted reversely.
Elements are extracted using `pop()` for ease of implementation which
is relatively the same as using a real queue and removing this first element,
Except that the first approach takes only one instruction.
"""
def printQueue(queue):
  counter = len(queue)
  for child in queue:
    print("#{}: Node: {}, W: {}".format(counter, child["node"].id, child["w"]))
    counter -= 1
  print("\n")

"""
Print Visited Nodes
"""
def printVisited(visited):
  counter = 0
  for node in visited:
    print("#{} -> {} w: {}".format(counter, node["node"].id, node["w"]))
    counter += 1


"""
Unform Cost algorithm
@param tree: Tree, structure with root node
@param goalNodes: String, List of acceptable target nodes
"""
def UniformCostSearch(tree, goalNodes):
  
  # did we find a solution
  solutionFound = False
  
  # queue, which is technically a stack .., still named queue to match the algorithm description
  queue = [{"node": tree.root, "w": 0}]

  # list of visited nodes
  visited = []

  # counting number of iterations
  iteration = -1


  if tree.root.id in goalNodes:
    visited.append({"node": tree.root, "w": 0})
    solutionFound = True

  while len(queue) != 0 and solutionFound == False:
    iteration += 1
    print("iteration #{}, queue order:".format(iteration))
    printQueue(queue)

    child = queue.pop()
    #print("child", child["node"].id)
    
    if child in visited:
      continue

    if child["node"].id in goalNodes:
      visited.append(child)
      solutionFound = True
      break
    
    visited.append(child)

    childs = child["node"].children
    
    for c in childs:
    
      if not(c["node"] in visited):
        c["w"] += child["w"]
        queue.append(c)
    
    queue = sorted(queue, key=lambda node: node["w"], reverse=True)
  
  if solutionFound:
    print("Found a solution")
  else:
    print("No solution found")

  print("Backtrace:")
  printVisited(visited)

    

Tree.py

# Tree data structure

class Node:
  def __init__(self, name):
    self.id = name
    self.children = []
  
  def addChild(self, node, w):
    self.children.append({
      "node": node, 
      "w": w
    })

class Tree:
  def __init__(self, root):
    self.root = root