Гамильтонов цикл Networkx - PullRequest
Новая
       38

Гамильтонов цикл Networkx

3 голосов
/ 29 мая 2020

Я хотел бы добавить в свой дизайн функциональность цикла Гамильтона, но не знаю, как это сделать. Я знаю, что есть такие алгоритмы, как nx.is_tournament.hamiltonian_path и c. Но я не знаю, как именно их реализовать. Ниже приведен пример цикла Эйлера, который мне подходит, и я хотел бы создать цикл Гамильтона аналогичным образом. 

def isEulerian():
    isEulerian = nx.is_eulerian(myGlobalGraph)
    if isEulerian == True:
        trueInfo = 'this is Eulerian graph'
        trueInfo2 = '\n'
        Log.insert(INSERT, trueInfo)
        Log.insert(INSERT, trueInfo2)
        eulerianCircuit = list(nx.eulerian_circuit(myGlobalGraph))
        eulerianCircuitInfo = 'Order of action:'
        eulerianCircuitInfo2 = '\n'
        Log.insert(INSERT, eulerianCircuitInfo)
        Log.insert(INSERT, eulerianCircuitInfo2)
        for i in range(len(eulerianCircuit)):
            x = eulerianCircuit[i][::2]
            eulerianCircuitInfo3 = x
            eulerianCircuitInfo4 = ' > '
            Log.insert(INSERT, eulerianCircuitInfo3)
            Log.insert(INSERT, eulerianCircuitInfo4)
        eulerianCircuitInfo5 = '\n'
        Log.insert(INSERT, eulerianCircuitInfo5)
        eulerianCircuitInfo6 = '\n'
        Log.insert(INSERT, eulerianCircuitInfo6)
    elif isEulerian == False:
        falseInfo = 'this is not Eulerian graph'
        falseInfo2 = '\n'
        falseInfo3 = '\n'
        Log.insert(INSERT, falseInfo)
        Log.insert(INSERT, falseInfo2)
        Log.insert(INSERT, falseInfo3)

1 Ответ

2 голосов
/ 30 мая 2020

Реализация , о которой вы говорите в networkx, работает только с турманентными графами, которые представляют собой графы, в которых между каждым узлом есть ровно одно направленное ребро. Я предполагаю, что вам нужна общая реализация графа, и поэтому она вам не подходит.

Причина (я считаю), что это не реализация для гамильтонова пути в networkx, заключается в том, что проблема поиска одного NP-Complete . Так что, если вы просто создадите алгоритм грубой силы, это будет лучшее, что вы можете сделать.

Вот одна реализация грубой силы , которую я нашел на github.

...