Graph();
bool data_input(const std::string file_name);
void create_A();
bool hamilton(int curr);
void data_output(const std::string file_name);
void no_way_answer(const std::string file_name);
void error_output(const std::string file_name);
~Graph();
Above is an image of a set of the classic Hamiltonian path class. This means that we will be able to understand how it is structured and what functions it performs. Let's go!
#include "Graph.h" - don't forget to connect the declared class to the source (.cpp).
bool Graph::data_input(const string file_name) {
int tek;
ifstream in_file;
in_file.open(file_name);
if (in_file) {
if (in_file >> n && n>0) {
while (!in_file.eof()) {
if(in_file >> tek && tek>0)
Vert.push_back(tek);
else return false;
}
}
else return false;
}
else return false;
in_file.close();
return true;
};
Working with data is easy when you have the right libraries and know how to use them. It's easier to practice on files, because the values are automatically tracked.
Initialize the vertices to zeros:
for (int i = 0; i < n; i++) Visited.push_back(false);In the graph we need to find a path where we pass the vertex only once. See the algorithm below
bool Graph::hamilton(int curr)
{
Path.push_back(curr);
if (Path.size() == n)
return true;
Visited[curr] = true;
for (int nxt = 0; nxt < n; ++nxt) {
if (A[curr][nxt] == 1 && !Visited[nxt])
if (hamilton(nxt)) return true;
}
Visited[curr] = false;
Path.pop_back();
return false;
};
- The algorithm looks simple, but for correct verification we will output everything to a file, including unsuccessful attempts (to track inaccuracies in the code)
void Graph::error_output(const string file_name) {
ofstream errorFile;
errorFile.open(file_name);
errorFile << "Error";
errorFile.close();
}
In data science, this plays a role in storing and optimally accounting for data. Because the Hamiltonian graph contains one cycle and helps in searching for data in a fast way.