我想在我的设计中加入汉密尔顿循环的功能,但我不知道怎么做。我知道有nx.is_tournament.hamiltonian_path
等算法,但我不知道如何准确地实现它们。下面是一个欧拉循环的例子,对我来说很好,我想以类似的方式创建一个汉密尔顿循环
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)
networkx中所指的implementation仅用于锦标赛图,即每个节点之间只有一条有向边的图。我假设您需要一个通用的图形实现,因此它不适合您
原因(我相信)是networkx中没有哈密顿路径的实现,因为找到哈密顿路径的问题是NP完全的。因此,如果你想创建一个暴力算法,这将是你能做的最好的
这是我在github上找到的一个brute force implementation
相关问题 更多 >
编程相关推荐