Dziwne zachowanie algorytmu szukającego cykl Hamiltona

Mam sobie kod:

void hamilton_cycle(Graph::size_type v, Graph &graph, std::vector<bool>& visited, std::queue<Graph::size_type> &q) {
  q.push(v);

  if (q.size() != graph.nodes_count()) {
    visited[v] = true;
    for(auto& n : graph.neighbours(v))
      if (visited[n] == false)
        hamilton_cycle(n, graph, visited, q);
    visited[v] = false;
    q.pop();
  }
}

bool hamilton_cycle(Graph &graph) {
  std::queue<Graph::size_type> q;
  std::vector<bool> visited(graph.nodes_count());

  hamilton_cycle(0, graph, visited, q);

  return graph.is_edge(q.back(), 0);
}

void generate_graph(Graph &graph, double denecity = 0.5, bool with_cycle = true) {
  int size = graph.nodes_count();
  int vertices = floor((size * (size - 1)) * denecity);
  if (with_cycle) {
    int i = 0;
    std::vector<Graph::size_type> cycle(size);
    std::generate(cycle.begin(), cycle.end(), [&]() { return i++; });
    std::random_shuffle(cycle.begin(), cycle.end());

    graph.add_edge(cycle[0], cycle.back());
    for (auto i = 1; i < cycle.size(); i++) {
      graph.add_edge(cycle[i-1], cycle[i]);
    }
    vertices -= cycle.size();
  }

  while (graph.edges_count() < vertices) {
    int a = 0, b = 0;
    do { a = rand() % size; b = rand() % size; } while (a == b);
    graph.add_edge(a, b);
  }
}

Mający w założeniu generować graf z cyklem Hamiltona (i to robi, przynjamniej dla danych jakie podałem), ale to czy znajdzie cykl czy nie już wygląda od widzimisię programu. Z debuggera nie za bardzo udało mi się cokolwiek wywnioskować, więc już zaczyna mi brakować pomysłów co tu może być źle. Ma ktoś jakiś pomysł?

Zacznij może od wyświetlenie danych pierwszego z brzegu grafu dla którego wg ciebie jest cykl zaś algorytm go nie znajduje.
Nie chciałbyś pokazać - Graph::neighbours() ?

Już znalazłem co było nie tak. Zamiast q.pop() na końcu ifa powinno być na końcu całej funkcji return graph.is_edge(q.back(), 0), dzięki czemu nie usuwam przypadkowo ostaniego elementu z kolejki, który mógł by mi zamykać graf. A przynajmniej tak mi się zdaje, bo po tej zmianie działa. Wolno bo wolno, ale działa.

Co do grafu dla którego to powyżej nie działa to jest np.:

0
	4
	2
1
	2
	3
2
	0
	1
3
	4
	1
4
	3
	0
Nie ma

Najpierw mamy podany wierzchołek a następnie wszystkich jego sąsiadów.

Jeśli chodzi o przechowywanie grafu to mam takie klasy:

class Graph {
  public:
    typedef unsigned int size_type;
    typedef std::list<size_type> Neighbours;

  protected:
    size_type m_nodes_count, m_edges_count;

  public:
    Graph(size_type nodes_count = 0) :
      m_nodes_count(nodes_count), m_edges_count(0) {}

    virtual bool is_edge(size_type from, size_type to) = 0;
    virtual Neighbours neighbours(size_type node) = 0;

    virtual Graph& add_edge(size_type from, size_type to) = 0;

    size_type nodes_count() { return m_nodes_count; }
    size_type edges_count() { return m_edges_count; }

    virtual ~Graph() {}
};

class AdjList : public Graph {
  private:
    typedef std::list<size_type> Row;
    std::vector<Row> m_list;

  public:
    AdjList(size_type nodes_count) : Graph(nodes_count) {
      m_list.resize(nodes_count);
    }

    virtual bool is_edge(size_type from, size_type to) override {
      return std::find(m_list[from].begin(), m_list[from].end(), to) != m_list[from].end();
    }

    virtual Graph& add_edge(size_type from, size_type to) override {
      if (!is_edge(from, to)) {
        m_list[from].push_back(to);
        m_list[to].push_back(from);
        m_edges_count++;
      }

      return *this;
    }

    virtual Neighbours neighbours(size_type node) {
      return m_list[node];
    }
};

EDIT:

Błąd musi być jednak w zwracaniu sąsiadów, gdyż w liście oprócz potrzebnych danych jest praktycznie nieskończona liczba powtórzeń tych samych danych + jakichś śmieci :/