File Exchange

image thumbnail

hamiltonian(Graph, Source, Destination)

version 1.0.0.0 (3.13 KB) by Pramit Biswas
This MATLAB function can be used to find Hamiltonian Path or Cycle

10 Downloads

Updated 28 Jun 2015

View License

This MATLAB function c% Let us create the following graph
(1)--(2)--(3)-------(4)
| / \ | |
| / \ | |
| / \ | |
(5)-------(6) |
| |
| |
| |
(7)-------------------(8)

g=[0 1 0 0 1 0 0 0;
1 0 1 0 1 1 0 0;
0 1 0 1 0 1 0 0;
0 0 1 0 0 0 0 1;
1 1 0 0 0 1 1 0;
0 1 1 0 1 0 0 0;
0 0 0 0 1 0 0 1;
0 0 0 1 0 0 1 0]
s=5; % Source
d=1; % Destination
P = hamiltonianPath(g,s,d);

P will be an array mentioning the path/cycle, if path/cycle found; or a
string: 'No Path/Cycle Found', if path/cycle not found

#Note: This code can be used for finding Hamiltonian cycle also. For
that, make sure Source and Destination are same.

Cite As

Pramit Biswas (2020). hamiltonian(Graph, Source, Destination) (https://www.mathworks.com/matlabcentral/fileexchange/51610-hamiltonian-graph-source-destination), MATLAB Central File Exchange. Retrieved .

Comments and Ratings (12)

@pkc yes this code only provides a single Hamiltonian path. Thanks for correcting. @dedeff sorry, my mistake.

pkc

@ Pramit Biswas, I think dedeff was looking for multiple Hamiltonian paths for each given source and destination pair. Correct me if I'm wrong, but doesn't your code find only one Hamiltonian path for each given source and destination pair?

@dedeff, yes of course. Read the description, please.

dedeff

Hi, is it possible to find all the hamiltonian Path from a source to a destination?

Pramit Biswas

@zein what is the exact error?

Pramit Biswas

@zein check your "Graph" variable

zein smak

after i download this file, open with matlab. there is an error, why?

Error in hamiltonian (line 39)
if ~isreal(Graph)

Pramit Biswas

@kalohr: For some reason, the graph is distorted when uploading the file. Consider download and check the function file.
Need to create simple connection matrix. Means, if node 1 is connected to node 2 then g(1,2)=1 and if node 1 is not connected to node 3 then g(1,3)=0, and so on.

Pramit Biswas

@gustav: simple.
just make two nested for loop, and call this function to get all the path.

Remember: it can take a long time for larger graph

Do you known how to find all the hamiltonian paths? if there is more than one

kalohr

thanks for the contribution

could you be kind enough as to explain how g represents the graph above ?

MATLAB Release Compatibility
Created with R10
Compatible with any release
Platform Compatibility
Windows macOS Linux