-1
$\begingroup$

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.

$\endgroup$

closed as off-topic by David Richerby, Juho, J.-E. Pin, Luke Mathieson, hengxin Apr 13 '15 at 9:44

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions about software development or programming tools are off-topic here, but can be asked on Stack Overflow." – David Richerby, J.-E. Pin, Luke Mathieson, hengxin
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ 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? $\endgroup$ – Rick Decker Apr 12 '15 at 21:40
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Apr 13 '15 at 1:26
  • $\begingroup$ 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. $\endgroup$ – Adam Apr 14 '15 at 11:08
2
$\begingroup$

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.