CODEWITHSUNDEEP
pythonalgorithmgraphnetworkx
Abso
Abso

Reputation: 53

Networkx hamiltonian cycle

I would like to add Hamilton cycle functionality to my design, but I'm not sure how to do it. I know there are algorithms like nx.is_tournament.hamiltonian_path etc. But I don't know how to implement them exactly. Below is an example of an euler cycle that works fine for me and I would like to create a Hamilton cycle in a similar way.

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)

Upvotes: 4

Views: 4038

Answers (1)

Yonlif
Yonlif

Reputation: 1800

The implementation you are referring to in networkx is working only on tournament graphs, which are graphs where there is exactly one directed edge between each node. I assume you need a general graph implementation and therefore it is not suitable for you.

The reason (I believe) these is no implementation for hamiltonian path in networkx, is that the problem of finding one is NP-Complete. So if you would just create a brute force algorithm it will be the best you can do.

Here is one brute force implementation I found on github.

Upvotes: 2

Related Questions