使用 python 添加边缘的图形实现

Question

测试字符串表示欧拉项目问题 18 中给出的结构。试图用图论来解决它。我正在尝试创建的图形结构如下所示。字符串中给出的每个数字都是图形中的一个节点。

3->(7,4)
7->(2,4)
4->(4,6)
2->(8,5)
mytesttring='''
3
7 4
2 4 6
8 5 9 3'''

节点类对象接受元组作为位置和值。 在上面的字符串 mytesttring 中，第一个数字 3 的位置是 (0,0(，值是 3，类似地 7 位置为 (1,0(，值为 7

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 getNodeHash(self):
return hash(str(self.position)+str(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(),)

有向图类如下，它以python字典的形式存储边缘，其中key是源节点，value是目标节点的列表。当通过方法addEdge向图添加边时，它会检查节点是否作为键存在于边字典中。如果目标节点的源在 Edge 字典中未作为键存在，则会抛出"节点不在图形中"错误。

class Diagraph(object):
'''the edges is a dict mapping node to a list of its destination'''
def __init__(self):
self.edges = {}
def addNode(self,node):
if node in self.edges:
raise ValueError('Duplicate node')
else:
self.edges[node]=[]
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)
def getChildrenof(self,node):
return self.edges[node]
def hasNode(self,node):
return node in self.edges

将输入字符串转换为包含各个数字的列表列表。

testlist2=[ list(map(int,elements.split())) for elements in mytesttring.strip().split("n")]
print(testlist2)
out: [[3], [7, 4], [2, 4, 6], [8, 5, 9, 3]]

我能够通过以下方式将节点添加到 Diagraph 对象中。

y=Diagraph()
for i in range(len(testlist2)):
for j in range(len(testlist2)):
if i<=j:
y.addNode(node((j,i),testlist2[j][i]))

这 10 个节点存在于边字典中。但是当我尝试使用方法添加边缘时 addEdge ，它会引发"不在图中的节点"。任何人都可以建议添加边缘的正确方法。字典的键是类node的对象。

Answer 1

当我再次创建节点并尝试将其添加到边缘时，我用于添加边缘的代码因'Node not in graph'而失败node((j,i),testlist2[j][i])。我忘记的一点是它创建了一个新node object即使输入相同。

每个节点都作为字典edges的键存在。我们可以将字典edges的键转换为列表listofkeys=list(y.edges.keys())然后基于node class的getPosition方法创建一个二合字母结构，或者我们可以捕获在列表中创建的节点，然后利用此列表emplist来创建边缘。我修改了代码以添加节点，以便在列表中捕获它。我可以emplist使用此列表来创建边缘和直径。

emplist=[]
for i in range(len(testlist2)):
for j in range(len(testlist2)):
if i<=j:
mynode=node((j,i),testlist2[j][i])
emplist.append(mynode)
y.addNode(mynode)

代码以添加所有边缘。

for node in emplist:
# iterate through all the nodes again and form a logic add the edges
for allnodes in emplist:
if node.getPosition()[0]==allnodes.getPosition()[0]-1 and node.getPosition()[1]==allnodes.getPosition()[1]-1:
y.addEdge(edge(node,allnodes))
if node.getPosition()[0]==allnodes.getPosition()[0]-1 and node.getPosition()[1]==allnodes.getPosition()[1]:
y.addEdge(edge(node,allnodes))