0

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.

1
Contributor
1
Reply
2
Views
9 Years
Discussion Span
Last Post by prs55
0

I did put this code on
pathOk function but it does not work.

template <typename ItemType>
bool Graph<ItemType>:athOK(int k, const vector<int>& x)
{
vector<bool> used;
int n = int(adj.size());

if(used[x[k]])
return false;

if(k<n)
return adj [x[k-1]] [x[k]];
else
return adj[x[n-1]][x[n]] && adj[x[1]][x[n]];

}

It is because it contains two dimensional array and the adjacency list defined is not of type 2 dimensional.

Hope u understood my problem..

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.