有如下数字的图结构。
在 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 中使用以下节点和边类创建图结构
节点类，它需要位置作为一个元组和一个值 示例:元素及其位置、值
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 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 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(),)
有向图类如下。图结构构建为字典邻接列表。 {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'
创建并返回要处理的图形对象的函数。
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
如何列出两个节点之间的所有可用路径。特别是 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)
返回终端节点如 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) 不起作用。请任何人提出一种方法这个问题。
最佳答案
给定一棵树
tree = \
[ [1]
, [2, 3]
, [4, 5, 6]
, [7, 8, 9, 10]
, [11, 12, 13, 14, 15]
]
还有一个遍历函数
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 中的高级功能生成器。也许您想了解如何使用更原始的功能来实现解决方案...
我们在这里寻找的通用机制是列表 monad，它捕捉了模糊计算的思想；一些可能返回多个值的过程。
Python 已经提供了列表和使用 [] 构造它们的方法。我们只需要提供绑定(bind)操作，下面命名为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 有一个内置的 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 来抽象此机制。最终，您可以根据需要构建程序，但要知道它不需要比我们在这里编写的更复杂。
更新
作为@user3386109在评论中指出，我上面的程序生成路径，就好像每个父项都连接到所有 个子项一样。然而，这是一个错误，因为您的图表显示 parent 只与相邻 child 有联系。我们可以通过修改我们的程序来解决这个问题——下面以粗体
显示的更改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 来确定哪些节点是“相邻的”，但它使我们的 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 函数起作用的原因是因为您的输入数据是统一且有效的。通过对图像中的路径进行颜色编码，您可以清楚地看到索引 i 和 i + 1 。我们永远不必担心索引越界错误，因为您可以看到 i + 1 永远不会在没有子节点(即最后一行)的节点上计算。如果您要指定无效 数据，traverse 不保证有效结果。
关于python-3.x - 遍历图表中的所有可用路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/50703780/