werlless
werlless

Reputation: 49

Check if its a Hamilton cycle, create an undirected graph using python

I need to write a code which tells if a cycle is hamilton or not.

First i have two text files:

1.file : First line contains the number of vertices and edges while the rest is a pair of two vertices which are connected.Like 0 1 means there is an edge between those two.

2.file: a line with numbers(the vertices) where we need to check if its a hamilton cycle or not.

First of all, how do you write the graph down without loops that are undirected? Because I couldn't get it, it gives me error.

As I tried:

def read_graph(f,l):
"""
Read a graph from a text file.

:param f: the file to read
:return: the edge-list, the starting and final vertex of path
"""

header = f.readline().split()
n, m = [int(s) for s in header]

graph = dict((i, []) for i in range(n))
for j in range(m):
    edge = f.readline().split()
    u, v = [int(s) for s in edge]
    graph[u].append(v)
"second file"
header2=l.readline().split()
k=[]
for s in header2:
    k.append(s)
graph2=dict((i,[]) for i in range (len(k)))
for g in range(len(k)-1):
    edge2=l.readline().split()
    w,z=[int(s) for s in edge2]
    graph2[w].append(z)


return graph, graph2




 ......


if __name__ == '__main__':
    import sys
    with open(sys.argv[1], 'r') as f:
        with open(sys.argv[1], 'r') as l:
            graph = read_graph(f,l)
        print(graph)

The second question:

How do you check if the cycle is hamilton or not? First I am planning to check if it is really a cycle or not, then if it is then check if the vertice occurs only one.
Is there anything else I should do to get my answer, advice or an easier way?

Thank you for replying.

Upvotes: 1

Views: 1327

Answers (0)

Related Questions