I'm writing a function that uses graphs to create all possible states for a bridge and torch problem variation. Instead of creating a new node for each repeated state, I use a lookup table to use the same node. When I run the program, the graph is populated as a complete graph instead of the required state space graph.
This is the structure for my graph class.
class Node:
def __init__(self, lstate: str, rstate: str, nextstates=[]):
self.lstate = lstate
self.rstate = rstate
self.nextnodes = nextstates
def addChild(self, child):
if child not in self.nextnodes:
self.nextnodes.append(child)
def dumpStateInfo(self):
print("left: " + self.lstate + " right: " + self.rstate)
def dumpNodeInfo(self):
self.dumpStateInfo()
class Graph:
def __init__(self, start, end) -> None:
self.root = Node(start, end)
self.lookup = dict()
And here is the function that builds the graph
def createChildren(self, currnode):
currlstate = currnode.lstate
currrstate = currnode.rstate
if currlstate == "" or currrstate == "abcdp":
return
newnodes = []
if "p" in currlstate:
for i in range(len(currlstate) - 2):
for j in range(i + 1, len(currlstate) - 1):
travelers = currlstate[i] + currlstate[j]
lstate = (
currlstate.replace(currlstate[i], "")
.replace(currlstate[j], "")
.replace("p", "")
)
rstate = "".join(sorted(travelers + currrstate)) + "p"
state = lstate + " " + rstate
if state not in self.lookup.keys():
node = Node(lstate, rstate)
self.lookup[state] = node
currnode.addChild(node)
newnodes.append(node)
else:
node = self.lookup[state]
currnode.addChild(node)
print("parent: " + currlstate + " " + currrstate + " : Current State: " + lstate + " " + rstate)
currnode.dumpStateInfo()
node.dumpStateInfo()
#print(len(self.root.nextnodes))
else:
for i in range(len(currrstate) - 1):
traveler = currrstate[i]
rstate = currrstate.replace(traveler, "").replace("p", "")
lstate = "".join(sorted(traveler + currlstate)) + "p"
state = lstate + " " + rstate
if state not in self.lookup.keys():
node = Node(lstate, rstate)
self.lookup[state] = node
currnode.addChild(node)
newnodes.append(node)
else:
node = self.lookup[state]
currnode.addChild(node)
print("parent: " + currlstate + " " + currrstate + " : Current State: " + lstate + " " + rstate)
currnode.dumpStateInfo()
node.dumpStateInfo()
#print(len(self.root.nextnodes))
for i in newnodes:
self.createChildren(i)
def buildTree(self):
currnode = self.root
self.lookup[currnode.lstate + " " + currnode.rstate] = currnode
self.createChildren(currnode)
Output of the print and dump functions
parent: abcdp : Current State: cd abp
left: abcdp right:
left: cd right: abp
parent: abcdp : Current State: bd acp
left: abcdp right:
left: bd right: acp
parent: abcdp : Current State: bc adp
left: abcdp right:
left: bc right: adp
parent: abcdp : Current State: ad bcp
left: abcdp right:
left: ad right: bcp
parent: abcdp : Current State: ac bdp
left: abcdp right:
left: ac right: bdp
parent: abcdp : Current State: ab cdp
left: abcdp right:
left: ab right: cdp
parent: cd abp : Current State: acdp b
left: cd right: abp
left: acdp right: b
parent: cd abp : Current State: bcdp a
left: cd right: abp
left: bcdp right: a
parent: acdp b : Current State: d abcp
left: acdp right: b
left: d right: abcp
parent: acdp b : Current State: c abdp
left: acdp right: b
left: c right: abdp
parent: acdp b : Current State: a bcdp
left: acdp right: b
left: a right: bcdp
parent: d abcp : Current State: adp bc
left: d right: abcp
left: adp right: bc
parent: d abcp : Current State: bdp ac
left: d right: abcp
left: bdp right: ac
parent: d abcp : Current State: cdp ab
left: d right: abcp
left: cdp right: ab
parent: adp bc : Current State: abcdp
left: adp right: bc
left: right: abcdp
parent: bdp ac : Current State: abcdp
left: bdp right: ac
left: right: abcdp
parent: cdp ab : Current State: abcdp
left: cdp right: ab
left: right: abcdp
parent: c abdp : Current State: acp bd
left: c right: abdp
left: acp right: bd
parent: c abdp : Current State: bcp ad
left: c right: abdp
left: bcp right: ad
parent: c abdp : Current State: cdp ab
left: c right: abdp
left: cdp right: ab
parent: acp bd : Current State: abcdp
left: acp right: bd
left: right: abcdp
parent: bcp ad : Current State: abcdp
left: bcp right: ad
left: right: abcdp
parent: a bcdp : Current State: abp cd
left: a right: bcdp
left: abp right: cd
parent: a bcdp : Current State: acp bd
left: a right: bcdp
left: acp right: bd
parent: a bcdp : Current State: adp bc
left: a right: bcdp
left: adp right: bc
parent: abp cd : Current State: abcdp
left: abp right: cd
left: right: abcdp
parent: bcdp a : Current State: d abcp
left: bcdp right: a
left: d right: abcp
parent: bcdp a : Current State: c abdp
left: bcdp right: a
left: c right: abdp
parent: bcdp a : Current State: b acdp
left: bcdp right: a
left: b right: acdp
parent: b acdp : Current State: abp cd
left: b right: acdp
left: abp right: cd
parent: b acdp : Current State: bcp ad
left: b right: acdp
left: bcp right: ad
parent: b acdp : Current State: bdp ac
left: b right: acdp
left: bdp right: ac
parent: bd acp : Current State: abdp c
left: bd right: acp
left: abdp right: c
parent: bd acp : Current State: bcdp a
left: bd right: acp
left: bcdp right: a
parent: abdp c : Current State: d abcp
left: abdp right: c
left: d right: abcp
parent: abdp c : Current State: b acdp
left: abdp right: c
left: b right: acdp
parent: abdp c : Current State: a bcdp
left: abdp right: c
left: a right: bcdp
parent: bc adp : Current State: abcp d
left: bc right: adp
left: abcp right: d
parent: bc adp : Current State: bcdp a
left: bc right: adp
left: bcdp right: a
parent: abcp d : Current State: c abdp
left: abcp right: d
left: c right: abdp
parent: abcp d : Current State: b acdp
left: abcp right: d
left: b right: acdp
parent: abcp d : Current State: a bcdp
left: abcp right: d
left: a right: bcdp
parent: ad bcp : Current State: abdp c
left: ad right: bcp
left: abdp right: c
parent: ad bcp : Current State: acdp b
left: ad right: bcp
left: acdp right: b
parent: ac bdp : Current State: abcp d
left: ac right: bdp
left: abcp right: d
parent: ac bdp : Current State: acdp b
left: ac right: bdp
left: acdp right: b
parent: ab cdp : Current State: abcp d
left: ab right: cdp
left: abcp right: d
parent: ab cdp : Current State: abdp c
left: ab right: cdp
left: abdp right: c
There are 22 total possible states in the system and all the individual nodes have 21 children.
When a mutable (lists, sets, dictionaries, etc.) is set as a default to an argument, python creates that object once and refers to the same object each time it is called in the code. See this.
class Node:
def __init__(self, lstate: str, rstate: str, nextstates=[]):
self.lstate = lstate
self.rstate = rstate
self.nextnodes = nextstates
In this certain instance, all the nodes created share the same list for nextnodes, hence why the nodes are the children of each other.
To create a new object for each node, something like this should be done instead:
def __init__(self, lstate: str, rstate: str, nextnodes=None):
self.lstate = lstate
self.rstate = rstate
if nextnodes == None:
self.nextnodes = []
Creating an empty list inside the function ensures every Node object has a unique list of its own.