//--------------------------------------------------------------
// Datalogi 2A, September 2002
//
// Simple and slow algorithm for testing whether a graph has  
// an Euler tour
//
// Jens Kristian Jensen
// Martin Zachariasen 
//--------------------------------------------------------------
#include <stdio.h>
#include <LEDA/graph.h>

bool simple_euler(graph& G, 
		  node s, 
		  node v,
		  edge_array<bool>& visited,
		  int left_to_visit)
{
  edge e;

  forall_inout_edges(e, v) {
    if (!visited[e]) {
      visited[e] = true;
      left_to_visit--;
      if (left_to_visit == 0) {
	// All edges have been visited
	if (G.opposite(e, v) == s) {
	  // We have found an Euler tour!
	  return true;
	}
	else {
	  return false;
	}
      }
      if (simple_euler(G, s, G.opposite(e, v), visited, left_to_visit))
	return true;
      visited[e] = false;
      left_to_visit++;
    }
  }
  return false;
}
    
    

int main() {

  graph G;
  node A = G.new_node();
  node B = G.new_node();
  node C = G.new_node();
  node D = G.new_node();
  G.new_edge(A, B);   
  G.new_edge(A, B);   
  G.new_edge(B, C);   
  G.new_edge(B, C);   
  G.new_edge(D, A);   
  G.new_edge(D, B);   
  G.new_edge(D, C);   
  G.print();

  edge_array<bool> visited(G, false);
  if (simple_euler(G, 
		   G.first_node(), 
		   G.first_node(), 
		   visited,
		   G.number_of_edges()))
    cout << "Graph has an Euler tour." << endl;
  else
    cout << "Graph has no Euler tour." << endl;
}