Reputation: 49
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