遍历图表中的所有可用路径
Traversing through all the available paths in a diagraph
有如下数字的图结构。
将此结构加载到 python 中的图形对象中。我把它做成一个多行字符串，如下所示。
myString='''1
2 3
4 5 6
7 8 9 10
11 12 13 14 15'''
将其表示为列表列表。
>>> listofLists=[ list(map(int,elements.split())) for elements in myString.strip().split("\n")]
>>> print(listofLists)
[[1], [2, 3], [4, 5, 6], [7, 8, 9, 10], [11, 12, 13, 14, 15]]
在 python
中使用以下节点和边 class 创建图形结构
节点Class，它需要位置作为元组和值
示例：元素及其位置，值
1 --- position (0,0) and value is 1
2 --- position (1,0) and value is 2
3 --- position (1,1) and value is 3
节点class
class node(object):
def __init__(self,position,value):
'''
position : gives the position of the node wrt to the test string as a tuple
value : gives the value of the node
'''
self.value=value
self.position=position
def getPosition(self):
return self.position
def getvalue(self):
return self.value
def __str__(self):
return 'P:'+str(self.position)+' V:'+str(self.value)
边 class 在两个节点之间创建一条边。
class edge(object):
def __init__(self,src,dest):
'''src and dest are nodes'''
self.src = src
self.dest = dest
def getSource(self):
return self.src
def getDestination(self):
return self.dest
#return the destination nodes value as the weight
def getWeight(self):
return self.dest.getvalue()
def __str__(self):
return (self.src.getPosition(),)+'->'+(self.dest.getPosition(),)
有向图class如下。图结构构建为字典邻接列表。
{node1:[node2,node3],node2:[node3,node4]......}
class Diagraph(object):
'''the edges is a dict mapping node to a list of its destination'''
def __init__(self):
self.edges = {}
'''Adds the given node as a key to the dict named edges '''
def addNode(self,node):
if node in self.edges:
raise ValueError('Duplicate node')
else:
self.edges[node]=[]
'''addEdge accepts and edge class object checks if source and destination node are present in the graph '''
def addEdge(self,edge):
src = edge.getSource()
dest = edge.getDestination()
if not (src in self.edges and dest in self.edges):
raise ValueError('Node not in graph')
self.edges[src].append(dest)
'''getChildrenof returns all the children of the node'''
def getChildrenof(self,node):
return self.edges[node]
'''to check whether a node is present in the graph or not'''
def hasNode(self,node):
return node in self.edges
'''rootNode returns the root node i.e node at position (0,0)'''
def rootNode(self):
for keys in self.edges:
return keys if keys.getPosition()==(0,0) else 'No Root node for this graph'
用于创建和return要处理的图形对象的函数。
def createmygraph(testString):
'''input is a multi-line string'''
#create a list of lists from the string
listofLists=[ list(map(int,elements.split())) for elements in testString.strip().split("\n")]
y = Diagraph()
nodeList = []
# create all the nodes and store it in a list nodeList
for i in range(len(listofLists)):
for j in range(len(listofLists)):
if i<=j:
mynode=node((j,i),listofLists[j][i])
nodeList.append(mynode)
y.addNode(mynode)
# create all the edges
for srcNode in nodeList:
# iterate through all the nodes again and form a logic add the edges
for destNode in nodeList:
#to add the immediate down node eg : add 7 (1,0) to 3 (0,0) , add 2 (2,0) to 7 (1,0)
if srcNode.getPosition()[0]==destNode.getPosition()[0]-1 and srcNode.getPosition()[1]==destNode.getPosition()[1]-1:
y.addEdge(edge(srcNode,destNode))
#to add the bottom right node eg :add 4 (1,1) to 3 (0,0)
if srcNode.getPosition()[0]==destNode.getPosition()[0]-1 and srcNode.getPosition()[1]==destNode.getPosition()[1]:
y.addEdge(edge(srcNode,destNode))
return y
如何列出两个 nodes.Specifically 之间的所有可用路径 1---->11 , 1---->12 , 1---->13 , 1---->14 , 1---->15
对于这种情况，我尝试了左手优先深度优先的方法。但是它无法获取路径。
def leftFirstDepthFirst(graph,start,end,path,valueSum):
#add input start node to the path
path=path+[start]
#add the value to the valueSum variable
valueSum+=start.getvalue()
print('Current Path ',printPath(path))
print('The sum is ',valueSum)
# return if start and end node matches.
if start==end:
print('returning as start and end have matched')
return path
#if there are no further destination nodes, move up a node in the path and remove the current element from the path list.
if not graph.getChildrenof(start):
path.pop()
valueSum=valueSum-start.getvalue()
return leftFirstDepthFirst(graph,graph.getChildrenof(path[-1])[1],end,path,valueSum)
else:
for aNode in graph.getChildrenof(start):
return leftFirstDepthFirst(graph,aNode,end,path,valueSum)
print('no further path to explore')
正在测试代码。
#creating a graph object with given string
y=createmygraph(myString)
作用于return终端节点，如11、12、13、14、15。
def fetchTerminalNode(graph,position):
terminalNode=[]
for keys in graph.edges:
if not graph.edges[keys]:
terminalNode.append(keys)
return terminalNode[position]
运行深度先左先函数
source=y.rootNode() # element at position (0,0)
destination=fetchTerminalNode(y,1) #ie. number 12
print('Path from ',start ,'to ',destination)
xyz=leftFirstDepthFirst(y,source,destination,[],0)
获取元素 11 和 12 的路径，但不获取元素 13、14 或 15 的路径。即 destination=fetchTerminalNode(y,2) 没有 work.Can 请任何人提出解决此问题的方法。
给定一个 tree
tree = \
[ [1]
, [2, 3]
, [4, 5, 6]
, [7, 8, 9, 10]
, [11, 12, 13, 14, 15]
]
还有一个traverse函数
def traverse (tree):
def loop (path, t = None, *rest):
if not rest:
for x in t:
yield path + [x]
else:
for x in t:
yield from loop (path + [x], *rest)
return loop ([], *tree)
遍历所有路径...
for path in traverse (tree):
print (path)
# [ 1, 2, 4, 7, 11 ]
# [ 1, 2, 4, 7, 12 ]
# [ 1, 2, 4, 7, 13 ]
# [ 1, 2, 4, 7, 14 ]
# [ 1, 2, 4, 7, 15 ]
# [ 1, 2, 4, 8, 11 ]
# [ 1, 2, 4, 8, 12 ]
# ...
# [ 1, 3, 6, 9, 15 ]
# [ 1, 3, 6, 10, 11 ]
# [ 1, 3, 6, 10, 12 ]
# [ 1, 3, 6, 10, 13 ]
# [ 1, 3, 6, 10, 14 ]
# [ 1, 3, 6, 10, 15 ]
或者收集列表中的所有路径
print (list (traverse (tree)))
# [ [ 1, 2, 4, 7, 11 ]
# , [ 1, 2, 4, 7, 12 ]
# , [ 1, 2, 4, 7, 13 ]
# , [ 1, 2, 4, 7, 14 ]
# , [ 1, 2, 4, 7, 15 ]
# , [ 1, 2, 4, 8, 11 ]
# , [ 1, 2, 4, 8, 12 ]
# , ...
# , [ 1, 3, 6, 9, 15 ]
# , [ 1, 3, 6, 10, 11 ]
# , [ 1, 3, 6, 10, 12 ]
# , [ 1, 3, 6, 10, 13 ]
# , [ 1, 3, 6, 10, 14 ]
# , [ 1, 3, 6, 10, 15 ]
# ]
上面，我们使用了 Python 中的 high-level 功能的生成器。也许您想了解如何使用更原始的功能来实现解决方案...
我们在这里寻找的通用机制是列表 monad，它捕捉了模糊计算的思想；某些程序可能 return 可能 多个 值。
Python 已经提供了列表以及使用 [] 构建它们的方法。我们只需要提供绑定操作，下面命名为flat_map
def flat_map (f, xs):
return [ y for x in xs for y in f (x) ]
def traverse (tree):
def loop (path, t = None, *rest):
if not rest:
return map (lambda x: path + [x], t)
else:
return flat_map (lambda x: loop (path + [x], *rest), t)
return loop ([], *tree)
print (traverse (tree))
# [ [ 1, 2, 4, 7, 11 ]
# , [ 1, 2, 4, 7, 12 ]
# , [ 1, 2, 4, 7, 13 ]
# , ... same output as above ...
# ]
哦，Python 有一个 built-in product 函数，正好可以满足我们的需要。唯一的区别是路径将输出为元组 () 而不是列表 []
from itertools import product
tree = \
[ [1]
, [2, 3]
, [4, 5, 6]
, [7, 8, 9, 10]
, [11, 12, 13, 14, 15]
]
for path in product (*tree):
print (path)
# (1, 2, 4, 7, 11)
# (1, 2, 4, 7, 12)
# (1, 2, 4, 7, 13)
# (1, 2, 4, 7, 14)
# (1, 2, 4, 7, 15)
# ... same output as above ...
在您的程序中，您试图通过各种 类、node 和 edge 以及 diagraph 来抽象此机制。最终，您可以根据需要构建程序，但要知道它不需要比我们在这里编写的更复杂。
更新
正如 在评论中指出的那样，我上面的程序生成的路径就好像每个 parent 都连接到 all children。然而，这是一个错误，因为您的图表显示 parents 仅连接到 adjacent children。我们可以通过修改我们的程序来解决这个问题——在 bold
中进行以下更改
def traverse (tree):
def loop (path, <b>i,</b> t = None, *rest):
if not rest:
for <b>(j,</b>x<b>)</b> in <b>enumerate (</b>t<b>)</b>:
<b>if i == j or i + 1 == j:</b>
yield path + [x]
else:
for <b>(j,</b>x<b>)</b> in <b>enumerate (</b>t<b>)</b>:
<b>if i == j or i + 1 == j:</b>
yield from loop (path + [x], <b>j,</b> *rest)
return loop ([], <b>0,</b> *tree)
上面我们使用索引 i 和 j 来确定哪些节点是 "adjacent" 但它使我们的 loop 变得混乱。另外，新代码看起来引入了一些重复。给这个意图一个名字 adjacencies 让我们的功能更干净
def traverse (tree):
<b>def adjacencies (t, i):
for (j, x) in enumerate (t):
if i == j or i + 1 == j:
yield (j, x)</b>
def loop (path, i, t = None, *rest):
if not rest:
for <b>(_, x)</b> in <b>adjacencies (t, i)</b>:
yield path + [x]
else:
for <b>(j, x)</b> in <b>adjacencies (t, i)</b>:
yield from loop (path + [x], j, *rest)
return loop ([], 0, *tree)
使用是一样的，只不过这次我们得到的是原题中指定的输出
for path in traverse (tree):
print (path)
# [1, 2, 4, 7, 11]
# [1, 2, 4, 7, 12]
# [1, 2, 4, 8, 12]
# [1, 2, 4, 8, 13]
# [1, 2, 5, 8, 12]
# [1, 2, 5, 8, 13]
# [1, 2, 5, 9, 13]
# [1, 2, 5, 9, 14]
# [1, 3, 5, 8, 12]
# [1, 3, 5, 8, 13]
# [1, 3, 5, 9, 13]
# [1, 3, 5, 9, 14]
# [1, 3, 6, 9, 13]
# [1, 3, 6, 9, 14]
# [1, 3, 6, 10, 14]
# [1, 3, 6, 10, 15]
这个简单的 adjancies 函数起作用的原因是您的输入数据是统一且有效的。您可以通过图像中的 color-coding 路径清楚地看到索引 i 和 i + 1。我们永远不必担心 index-out-of-bounds 错误，因为您可以看到 i + 1 永远不会在没有 children 的节点（即最后一行）上计算。如果您要指定 无效 数据，traverse 不保证有效结果。
PFB 我想出的函数使用 breathfirstSearch 打印根节点和结束节点之间的所有可用路径。
Google Colab/github link
def breathfirstalgo(graph,tempPaths,finalPath):
## iterates over all the lists inside the tempPaths and checks if there are child nodes to its last node.
condList=[graph.getChildrenof(apartList[-1]) for apartList in tempPaths if graph.getChildrenof(apartList[-1])]
tempL=[]
if condList:
for partialList in tempPaths:
#get the children of the last element of partialList
allchild=graph.getChildrenof(partialList[-1])
if allchild:
noOfChild=len(allchild)
#create noOfChild copies of the partialList
newlist=[partialList[:] for _ in range(noOfChild)]
#append the a child element to the new list
for i in range(noOfChild):
newlist[i].append(allchild[i])
#append each list to the temp list tempL
for alist in newlist:
tempL.append(alist)
else:
pass
#after completion of the for loop i.e iterate through 1 level
return breathfirstalgo(graph,tempL,finalPath)
else:
#append all the lists from tempPaths to finalPath that will be returned
for completePath in tempPaths:
finalPath.append(completePath)
return finalPath
如下测试 breathfirstsearch 解决方案。
mygraph=createmygraph(myString)
print('The graph object is ',mygraph)
print('The root node is ',mygraph.rootNode())
#print(mygraph)
all_list=breathfirstalgo(mygraph,tempPaths=[[mygraph.rootNode()]],finalPath=[])
print('alllist is ')
for idx,partlist in enumerate(all_list):
print(printPath(partlist))
将节点class的__str__修改为str(self.value)
后输出如下
The graph object is <__main__.Diagraph object at 0x7f08e5a3d128>
The root node is 1
alllist is
-->1-->2-->4-->7-->11
-->1-->2-->4-->7-->12
-->1-->2-->4-->8-->12
-->1-->2-->4-->8-->13
-->1-->2-->5-->8-->12
-->1-->2-->5-->8-->13
-->1-->2-->5-->9-->13
-->1-->2-->5-->9-->14
-->1-->3-->5-->8-->12
-->1-->3-->5-->8-->13
-->1-->3-->5-->9-->13
-->1-->3-->5-->9-->14
-->1-->3-->6-->9-->13
-->1-->3-->6-->9-->14
-->1-->3-->6-->10-->14
-->1-->3-->6-->10-->15
有如下数字的图结构。
将此结构加载到 python 中的图形对象中。我把它做成一个多行字符串，如下所示。
myString='''1
2 3
4 5 6
7 8 9 10
11 12 13 14 15'''
将其表示为列表列表。
>>> listofLists=[ list(map(int,elements.split())) for elements in myString.strip().split("\n")]
>>> print(listofLists)
[[1], [2, 3], [4, 5, 6], [7, 8, 9, 10], [11, 12, 13, 14, 15]]
在 python
中使用以下节点和边 class 创建图形结构节点Class，它需要位置作为元组和值 示例：元素及其位置，值
1 --- position (0,0) and value is 1
2 --- position (1,0) and value is 2
3 --- position (1,1) and value is 3
节点class
class node(object):
def __init__(self,position,value):
'''
position : gives the position of the node wrt to the test string as a tuple
value : gives the value of the node
'''
self.value=value
self.position=position
def getPosition(self):
return self.position
def getvalue(self):
return self.value
def __str__(self):
return 'P:'+str(self.position)+' V:'+str(self.value)
边 class 在两个节点之间创建一条边。
class edge(object):
def __init__(self,src,dest):
'''src and dest are nodes'''
self.src = src
self.dest = dest
def getSource(self):
return self.src
def getDestination(self):
return self.dest
#return the destination nodes value as the weight
def getWeight(self):
return self.dest.getvalue()
def __str__(self):
return (self.src.getPosition(),)+'->'+(self.dest.getPosition(),)
有向图class如下。图结构构建为字典邻接列表。 {node1:[node2,node3],node2:[node3,node4]......}
class Diagraph(object):
'''the edges is a dict mapping node to a list of its destination'''
def __init__(self):
self.edges = {}
'''Adds the given node as a key to the dict named edges '''
def addNode(self,node):
if node in self.edges:
raise ValueError('Duplicate node')
else:
self.edges[node]=[]
'''addEdge accepts and edge class object checks if source and destination node are present in the graph '''
def addEdge(self,edge):
src = edge.getSource()
dest = edge.getDestination()
if not (src in self.edges and dest in self.edges):
raise ValueError('Node not in graph')
self.edges[src].append(dest)
'''getChildrenof returns all the children of the node'''
def getChildrenof(self,node):
return self.edges[node]
'''to check whether a node is present in the graph or not'''
def hasNode(self,node):
return node in self.edges
'''rootNode returns the root node i.e node at position (0,0)'''
def rootNode(self):
for keys in self.edges:
return keys if keys.getPosition()==(0,0) else 'No Root node for this graph'
用于创建和return要处理的图形对象的函数。
def createmygraph(testString):
'''input is a multi-line string'''
#create a list of lists from the string
listofLists=[ list(map(int,elements.split())) for elements in testString.strip().split("\n")]
y = Diagraph()
nodeList = []
# create all the nodes and store it in a list nodeList
for i in range(len(listofLists)):
for j in range(len(listofLists)):
if i<=j:
mynode=node((j,i),listofLists[j][i])
nodeList.append(mynode)
y.addNode(mynode)
# create all the edges
for srcNode in nodeList:
# iterate through all the nodes again and form a logic add the edges
for destNode in nodeList:
#to add the immediate down node eg : add 7 (1,0) to 3 (0,0) , add 2 (2,0) to 7 (1,0)
if srcNode.getPosition()[0]==destNode.getPosition()[0]-1 and srcNode.getPosition()[1]==destNode.getPosition()[1]-1:
y.addEdge(edge(srcNode,destNode))
#to add the bottom right node eg :add 4 (1,1) to 3 (0,0)
if srcNode.getPosition()[0]==destNode.getPosition()[0]-1 and srcNode.getPosition()[1]==destNode.getPosition()[1]:
y.addEdge(edge(srcNode,destNode))
return y
如何列出两个 nodes.Specifically 之间的所有可用路径 1---->11 , 1---->12 , 1---->13 , 1---->14 , 1---->15 对于这种情况，我尝试了左手优先深度优先的方法。但是它无法获取路径。
def leftFirstDepthFirst(graph,start,end,path,valueSum):
#add input start node to the path
path=path+[start]
#add the value to the valueSum variable
valueSum+=start.getvalue()
print('Current Path ',printPath(path))
print('The sum is ',valueSum)
# return if start and end node matches.
if start==end:
print('returning as start and end have matched')
return path
#if there are no further destination nodes, move up a node in the path and remove the current element from the path list.
if not graph.getChildrenof(start):
path.pop()
valueSum=valueSum-start.getvalue()
return leftFirstDepthFirst(graph,graph.getChildrenof(path[-1])[1],end,path,valueSum)
else:
for aNode in graph.getChildrenof(start):
return leftFirstDepthFirst(graph,aNode,end,path,valueSum)
print('no further path to explore')
正在测试代码。
#creating a graph object with given string
y=createmygraph(myString)
作用于return终端节点，如11、12、13、14、15。
def fetchTerminalNode(graph,position):
terminalNode=[]
for keys in graph.edges:
if not graph.edges[keys]:
terminalNode.append(keys)
return terminalNode[position]
运行深度先左先函数
source=y.rootNode() # element at position (0,0)
destination=fetchTerminalNode(y,1) #ie. number 12
print('Path from ',start ,'to ',destination)
xyz=leftFirstDepthFirst(y,source,destination,[],0)
获取元素 11 和 12 的路径，但不获取元素 13、14 或 15 的路径。即 destination=fetchTerminalNode(y,2) 没有 work.Can 请任何人提出解决此问题的方法。
给定一个 tree
tree = \
[ [1]
, [2, 3]
, [4, 5, 6]
, [7, 8, 9, 10]
, [11, 12, 13, 14, 15]
]
还有一个traverse函数
def traverse (tree):
def loop (path, t = None, *rest):
if not rest:
for x in t:
yield path + [x]
else:
for x in t:
yield from loop (path + [x], *rest)
return loop ([], *tree)
遍历所有路径...
for path in traverse (tree):
print (path)
# [ 1, 2, 4, 7, 11 ]
# [ 1, 2, 4, 7, 12 ]
# [ 1, 2, 4, 7, 13 ]
# [ 1, 2, 4, 7, 14 ]
# [ 1, 2, 4, 7, 15 ]
# [ 1, 2, 4, 8, 11 ]
# [ 1, 2, 4, 8, 12 ]
# ...
# [ 1, 3, 6, 9, 15 ]
# [ 1, 3, 6, 10, 11 ]
# [ 1, 3, 6, 10, 12 ]
# [ 1, 3, 6, 10, 13 ]
# [ 1, 3, 6, 10, 14 ]
# [ 1, 3, 6, 10, 15 ]
或者收集列表中的所有路径
print (list (traverse (tree)))
# [ [ 1, 2, 4, 7, 11 ]
# , [ 1, 2, 4, 7, 12 ]
# , [ 1, 2, 4, 7, 13 ]
# , [ 1, 2, 4, 7, 14 ]
# , [ 1, 2, 4, 7, 15 ]
# , [ 1, 2, 4, 8, 11 ]
# , [ 1, 2, 4, 8, 12 ]
# , ...
# , [ 1, 3, 6, 9, 15 ]
# , [ 1, 3, 6, 10, 11 ]
# , [ 1, 3, 6, 10, 12 ]
# , [ 1, 3, 6, 10, 13 ]
# , [ 1, 3, 6, 10, 14 ]
# , [ 1, 3, 6, 10, 15 ]
# ]
上面，我们使用了 Python 中的 high-level 功能的生成器。也许您想了解如何使用更原始的功能来实现解决方案...
我们在这里寻找的通用机制是列表 monad，它捕捉了模糊计算的思想；某些程序可能 return 可能 多个 值。
Python 已经提供了列表以及使用 [] 构建它们的方法。我们只需要提供绑定操作，下面命名为flat_map
def flat_map (f, xs):
return [ y for x in xs for y in f (x) ]
def traverse (tree):
def loop (path, t = None, *rest):
if not rest:
return map (lambda x: path + [x], t)
else:
return flat_map (lambda x: loop (path + [x], *rest), t)
return loop ([], *tree)
print (traverse (tree))
# [ [ 1, 2, 4, 7, 11 ]
# , [ 1, 2, 4, 7, 12 ]
# , [ 1, 2, 4, 7, 13 ]
# , ... same output as above ...
# ]
哦，Python 有一个 built-in product 函数，正好可以满足我们的需要。唯一的区别是路径将输出为元组 () 而不是列表 []
from itertools import product
tree = \
[ [1]
, [2, 3]
, [4, 5, 6]
, [7, 8, 9, 10]
, [11, 12, 13, 14, 15]
]
for path in product (*tree):
print (path)
# (1, 2, 4, 7, 11)
# (1, 2, 4, 7, 12)
# (1, 2, 4, 7, 13)
# (1, 2, 4, 7, 14)
# (1, 2, 4, 7, 15)
# ... same output as above ...
在您的程序中，您试图通过各种 类、node 和 edge 以及 diagraph 来抽象此机制。最终，您可以根据需要构建程序，但要知道它不需要比我们在这里编写的更复杂。
更新
正如
def traverse (tree):
def loop (path, <b>i,</b> t = None, *rest):
if not rest:
for <b>(j,</b>x<b>)</b> in <b>enumerate (</b>t<b>)</b>:
<b>if i == j or i + 1 == j:</b>
yield path + [x]
else:
for <b>(j,</b>x<b>)</b> in <b>enumerate (</b>t<b>)</b>:
<b>if i == j or i + 1 == j:</b>
yield from loop (path + [x], <b>j,</b> *rest)
return loop ([], <b>0,</b> *tree)
上面我们使用索引 i 和 j 来确定哪些节点是 "adjacent" 但它使我们的 loop 变得混乱。另外，新代码看起来引入了一些重复。给这个意图一个名字 adjacencies 让我们的功能更干净
def traverse (tree):
<b>def adjacencies (t, i):
for (j, x) in enumerate (t):
if i == j or i + 1 == j:
yield (j, x)</b>
def loop (path, i, t = None, *rest):
if not rest:
for <b>(_, x)</b> in <b>adjacencies (t, i)</b>:
yield path + [x]
else:
for <b>(j, x)</b> in <b>adjacencies (t, i)</b>:
yield from loop (path + [x], j, *rest)
return loop ([], 0, *tree)
使用是一样的，只不过这次我们得到的是原题中指定的输出
for path in traverse (tree):
print (path)
# [1, 2, 4, 7, 11]
# [1, 2, 4, 7, 12]
# [1, 2, 4, 8, 12]
# [1, 2, 4, 8, 13]
# [1, 2, 5, 8, 12]
# [1, 2, 5, 8, 13]
# [1, 2, 5, 9, 13]
# [1, 2, 5, 9, 14]
# [1, 3, 5, 8, 12]
# [1, 3, 5, 8, 13]
# [1, 3, 5, 9, 13]
# [1, 3, 5, 9, 14]
# [1, 3, 6, 9, 13]
# [1, 3, 6, 9, 14]
# [1, 3, 6, 10, 14]
# [1, 3, 6, 10, 15]
这个简单的 adjancies 函数起作用的原因是您的输入数据是统一且有效的。您可以通过图像中的 color-coding 路径清楚地看到索引 i 和 i + 1。我们永远不必担心 index-out-of-bounds 错误，因为您可以看到 i + 1 永远不会在没有 children 的节点（即最后一行）上计算。如果您要指定 无效 数据，traverse 不保证有效结果。
PFB 我想出的函数使用 breathfirstSearch 打印根节点和结束节点之间的所有可用路径。
Google Colab/github link
def breathfirstalgo(graph,tempPaths,finalPath):
## iterates over all the lists inside the tempPaths and checks if there are child nodes to its last node.
condList=[graph.getChildrenof(apartList[-1]) for apartList in tempPaths if graph.getChildrenof(apartList[-1])]
tempL=[]
if condList:
for partialList in tempPaths:
#get the children of the last element of partialList
allchild=graph.getChildrenof(partialList[-1])
if allchild:
noOfChild=len(allchild)
#create noOfChild copies of the partialList
newlist=[partialList[:] for _ in range(noOfChild)]
#append the a child element to the new list
for i in range(noOfChild):
newlist[i].append(allchild[i])
#append each list to the temp list tempL
for alist in newlist:
tempL.append(alist)
else:
pass
#after completion of the for loop i.e iterate through 1 level
return breathfirstalgo(graph,tempL,finalPath)
else:
#append all the lists from tempPaths to finalPath that will be returned
for completePath in tempPaths:
finalPath.append(completePath)
return finalPath
如下测试 breathfirstsearch 解决方案。
mygraph=createmygraph(myString)
print('The graph object is ',mygraph)
print('The root node is ',mygraph.rootNode())
#print(mygraph)
all_list=breathfirstalgo(mygraph,tempPaths=[[mygraph.rootNode()]],finalPath=[])
print('alllist is ')
for idx,partlist in enumerate(all_list):
print(printPath(partlist))
将节点class的__str__修改为str(self.value)
The graph object is <__main__.Diagraph object at 0x7f08e5a3d128>
The root node is 1
alllist is
-->1-->2-->4-->7-->11
-->1-->2-->4-->7-->12
-->1-->2-->4-->8-->12
-->1-->2-->4-->8-->13
-->1-->2-->5-->8-->12
-->1-->2-->5-->8-->13
-->1-->2-->5-->9-->13
-->1-->2-->5-->9-->14
-->1-->3-->5-->8-->12
-->1-->3-->5-->8-->13
-->1-->3-->5-->9-->13
-->1-->3-->5-->9-->14
-->1-->3-->6-->9-->13
-->1-->3-->6-->9-->14
-->1-->3-->6-->10-->14
-->1-->3-->6-->10-->15