# C program - Visually display Graph and checking for Hamiltonian Paths? [closed]

I have a very large graph in my c program with a list of nodes and edges. I want to print out the visual representation of this. What is the best way to go about this?

Additionally what's the best way to go about checking if said graph is hamiltonian and printing out a hamiltonian path? I can't find a decent algorithm.

• What do you mean by a "decent algorithm"? There certainly is an algorithm: just enumerate all possible paths from vertex $u$ to $v$ and check if each one is Hamiltonian, for all possible $u, v$. Of course that will take at least exponential time. Do you intend "decent" to be polynomial time? In that case you might have problems, since HAMILTONIAN PATH is NP-complete. What research have you done on this problem? – Rick Decker Apr 12 '15 at 21:40
• The fact that HAMILTONIAN CIRCUIT or PATH is NP-complete is not the end of the story. First, that could be exponential or sub-exponential time algorithm which might be practical for moderate values of $n$ (indeed, there are non-trivial algorithms for HAMILTONIAN CIRCUIT or PATH). Second, they could be some heuristics that work well in practice. Unfortunately, I'm not sure that this is the correct crowd to ask about algorithms of this sort. It would help if you provided more information on where your graphs come from. – Yuval Filmus Apr 13 '15 at 1:26
• Sorry, I'm new to the website. Didn't realize it was in the wrong section. I will post it somewhere else. Thank you again for those who answered anyhow. – Adam Apr 14 '15 at 11:08

Graphviz should do what you want.

http://www.graphviz.org/

You can you use it as program or as a library.

If you use as a program, then you just need to write a file of your graphs in the dot language and run graphviz on it.

Now, for the hamiltonian problem, you should know that this problem is NP-complete. Brute force is the most obvious solution. But you dont want that.

There is no general solution in polynomial time.

You could find a good solution for specific cases.