Could you guys please help me to solve this pathOk function,
the code is:
// graph.h
#include <iostream>
#include <vector>
#include <queue>
template <typename ItemType>
class Graph
{
public:
Graph(){ };
~Graph() { Clear(); }
void AddVertex(const ItemType& theItem);
void AddEdge(int n, int m);
bool Empty() const;
bool EdgeExists(int n, int m) const;
bool VertexExists(int n) const;
void Clear();
void SetItem(const ItemType& newItem, int n);
ItemType GetItem(int n) const;
int VertexCount() const;
int DegreeOfVertex(int n) const;
void ShowGraph() const;
bool Hamilton(vector<int>& x);
private:
class VertexNode;
typedef VertexNode * NodePointer;
class VertexNode
{
public:
VertexNode(int n) { vert = n; next = 0; }
int vert;
NodePointer next;
};
vector<ItemType> vertex;
vector<NodePointer> adj;
vector<bool> visit;
bool RecursHamilton(int k, vector<int>& x);
bool PathOK(int k, const vector<int>& x);
};
template <typename ItemType>
void Graph<ItemType>::AddVertex(const ItemType& theItem)
{
vertex.push_back(theItem);
adj.push_back(0);
}
template <typename ItemType>
void Graph<ItemType>::AddEdge(int n, int m)
{
NodePointer nPtr = new VertexNode(n),
mPtr = new VertexNode(m);
nPtr->next = adj[m];
adj[m] = nPtr;
mPtr->next = adj[n];
adj[n] = mPtr;
}
template <typename ItemType>
bool Graph<ItemType>::Empty() const
{
return vertex.size() == 0;
}
template <typename ItemType>
bool Graph<ItemType>::EdgeExists(int n, int m) const
{
NodePointer ptr = adj[n];
while (ptr != 0)
{
if (ptr->vert == m) return true;
ptr = ptr->next;
}
return false;
}
template <typename ItemType>
bool Graph<ItemType>::VertexExists(int n) const
{
return n >= 0 && n < int(vertex.size());
}
template <typename ItemType>
void Graph<ItemType>::Clear()
{
NodePointer ptr;
for (int i = 0; i < int(adj.size()); i++)
{
ptr = adj[i];
while (ptr != 0)
{
adj[i] = ptr->next;
delete ptr;
ptr = adj[i];
}
}
vertex.clear();
adj.clear();
}
template <typename ItemType>
void Graph<ItemType>::SetItem(const ItemType& newItem, int n)
{
vertex[n] = newItem;
}
template <typename ItemType>
ItemType Graph<ItemType>::GetItem(int n) const
{
return vertex[n];
}
template <typename ItemType>
int Graph<ItemType>::VertexCount() const
{
return int(vertex.size());
}
template <typename ItemType>
int Graph<ItemType>::DegreeOfVertex(int n) const
{
NodePointer ptr = adj[n];
int degree = 0;
while (ptr != 0)
{
degree++;
ptr = ptr->next;
}
return degree;
}
template <typename ItemType>
void Graph<ItemType>::ShowGraph() const
{
for (int i = 0; i < int(vertex.size()); i++)
{
cout << "[#" << i << ":" << vertex[i] << "]:";
NodePointer ptr = adj[i];
while (ptr != 0)
{
cout << " " << ptr->vert;
ptr = ptr->next;
}
cout << endl;
}
}
template <typename ItemType>
bool Graph<ItemType>::RecursHamilton(int k, vector<int>& x)
{
vector< vector<int> > graph;
int start = k;
int n = int(adj.size());
vector<bool> used;
for( x[k] = 2;x[k] < x[n];x[k]++)
if(PathOK(start,x))
{
used[x[k]] = true;
if(k == n || RecursHamilton(start,x))
cout<<' '<< x[k];
}
return false;
}
template <typename ItemType>
bool Graph<ItemType>::PathOK(int k, const vector<int>& x)
{
// need to implement this function..
}
template <typename ItemType>
bool Graph<ItemType>::Hamilton(vector<int>& x)
{
vector<bool> used;
int n = int(adj.size());
x[1] = 1;
used[1] = true;
for(int i = 2;i<n;i++)
if(used[i] = false)
RecursHamilton(2, x);
return false;
}I need to find out Hamiltonian circuit, it is a cycle starting from one vertex of undirected graph and visiting all th evertices only once except the starting n ending vertex being same.
eg. 012340
I have main problem on PathOk function..
Any help would be highly appreciated.