1

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

    3->(7,4)
    7->(2,4)
    4->(4,6)
    2->(8,5)

    mytesttring='''
        3
        7 4
        2 4 6
        8 5 9 3'''

节点类对象接受一个元组作为位置和值。在上面的字符串 myteststring 第一个数字 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向图中添加边时，它会检查节点是否作为边字典中的键存在。如果目标节点的源不是边字典中的键，则抛出“节点不在图中”错误。

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 方法添加边时，它会提高“节点不在图中”。谁能建议添加边缘的正确方法。字典的键是 class 的对象node。

4

1 回答 1

0

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

每个节点都作为字典的键存在edges。我们可以将字典的键转换edges为列表listofkeys=list(y.edges.keys())，然后根据创建图结构的getPosition方法，node class或者我们可以捕获列表中创建的节点，然后利用该列表 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))
于 2018-06-04T07:17:31.113 回答