Реализация графа с использованием Python с добавлением ребра - PullRequest
Новая
       30

Реализация графа с использованием Python с добавлением ребра

0 голосов
/ 01 июня 2018

Тестовая строка представляет структуру, заданную в проекте Эйлера задача 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, где ключ - это узел источника, а значение - списокузлы назначения.При добавлении ребра на график с помощью метода 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'.Может кто-нибудь предложить правильный способ добавления краев.Ключи к словарю - это объект класса node.

1 Ответ

0 голосов
/ 04 июня 2018

Код для добавления ребра не удался с '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))
...