使用 python 添加边的图形实现

Question

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

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

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

节点class对象接受一个元组作为位置和值。在上面的字符串 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如下接受一个源节点和一个目的节点。

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如下，它以python字典的形式存储边，其中key是源节点，value是目标节点列表。通过 addEdge 方法向图中添加边时，它会检查该节点是否作为键存在于边字典中。如果目标节点的源不作为边缘字典中的键存在，则抛出 'Node not in graph' 错误。

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 not in graph'。谁能建议添加边缘的正确方法。字典的键是 class node 的对象。

Answer 1

当我再次创建节点 node((j,i),testlist2[j][i]) 并尝试将其添加到边缘时，我用于添加边缘的代码因 'Node not in graph' 而失败。我忘记的一点是它创建了一个新的 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))

使用 python 添加边的图形实现

Graph implementation using python adding an edge

python

dictionary

class

digraphs

python-3.x