ceCode cpp">// euler3.cpp
#include <iostream>n>
#include <algorithm>an>
#include <vector>
#include <stack>
#include "assertions.hh&q=
uot;
#define LOG_LEVEL LOG_TRACE
#include "debug-log.hh&qu=
ot;
using namespace std;

template<typename T&=
gt;
struct vertex {
  vertex(const T& _data) : data(_data) { }
  void add_edge(vertex<T>* dest);
  void remove_edge(vertex<T>* dest);
  int degree() { return=
 edges.size(); }
  ostream& show(ostream&);
  void add_directed_edge(vertex<T>* dest) {=
 edges.push_back(dest); }
  void remove_directed_edge(vertex<T>* dest=
);
  T data;
  vector<vertex<T>*> edges;
};

// This adds undirected edge (both directions).
template<typename T&=
gt;
void vertex<T>::add_edge(vertex<T>* d=
est)
{
  assert(dest !=3D NULL);
  add_directed_edge(dest);
  dest->add_directed_edge(this);
}

template<typename T&=
gt;
void vertex<T>::remove_edge(vertex<T>=
* dest)
{
  assert(dest !=3D NULL);
  remove_directed_edge(dest);
  dest->remove_directed_edge(this);
}

template<typename T&=
gt;
void vertex<T>::remove_directed_edge(vertex=
<T>* dest)
{
  edges.erase(find(edges.begin(), edges.end(), dest));
}

template<typename T&=
gt;
ostream& vertex<T>::show(ostream& out)
{
  out << data << ':';
  for(unsigned i =3D pan class=3D"dv">0; i < edges.size(); i++) {
    out << ' ' << edges[i]-&g=
t;data;
  }
  return out << 'pan>\n';
}

// Now graph is a thin wrapper around a set of vertices.=

template<typename T&=
gt;
struct graph {
  ~graph();                     // destructor
  vertex<T>* add_vertex(const T& _data);
  vector<vertex<T>*> euler_path();
  ostream& show(ostream&);
private:
  vector<vertex<T>*> vertices;
};

template<typename T&=
gt;
graph<T>::~graph()
{
  for(unsigned i =3D pan class=3D"dv">0; i < vertices.size(); i++) {
    delete vertices.at(i);
  }
  vertices.clear();
}

template<typename T&=
gt;
vertex<T>* graph<T>::add_vertex(const=
 T& _data)
{
  vertex<T>* v =3D new vertex<T>(_dat=
a);
  vertices.push_back(v);
  return v;
}

// Print the graph's adjacency list
template<typename ve=
rtex>
ostream& graph<vertex>::show(ostream& out)
{
  for(unsigned i =3D pan class=3D"dv">0; i < vertices.size(); i++) {
    vertices[i]->show(out);
  }
  return out;
}

template<typename ve=
rtex>
ostream& operator << (ostream& out,=
 graph<vertex>& g)
{
  return g.show(out);
}

// Calculate and return an euler path. Algorithm basical=
ly taken from
// here: http://www.graph-magics.com/articles/euler.php<=
/span>
//
// NOTE: this is destructive -- it removes edges from th=
e graph. So if
// you need the graph afterwards, make a copy.
template<typename T&=
gt;
vector<vertex<T>*> graph<T>::euler_path()
{
  // If all vertices have even degree, choose any of the=
m.
  unsigned i =3D 0;
  vertex<T>* curr =3D vertices.at(i);
  // If there are exactly 2 vertices having an odd degre=
e: choose one
  // of them. This will be the current vertex.
  unsigned num_odd =3D 0>;
  for( ; i < vertices.size(); i++) {
    if(vertices.at(i)->degree() % =3D"dv">2 =3D=3D 1) {
      num_odd++;
      curr =3D vertices.at(i);
    }
  }
  log(LOG_INFO, "There were " << =
num_odd << " odd-degree vertices.">);
  vector<vertex<T>*> path;
  stack<vertex<T>*> stack;
  if(num_odd !=3D 2 &am=
p;& num_odd !=3D 0) {
    log(LOG_ERROR, "Sorry, no Euler path exists.&qu=
ot;);
    return path;
  }
  log(LOG_DEBUG, "Starting at " <<=
; curr->data << '=
\n' << *this<=
/span>);
  // Repeat until the current vertex has no more neighbo=
rs and the
  // stack is empty.
  while(curr->degree() > >0 || stack.size() > 0) {
    // If current vertex has no neighbors,
    if(curr->degree() =3D=3D ">0) {
      log(LOG_DEBUG, "* Adding " <&l=
t; curr->data << " to path.");
      // Add it to path
      path.push_back(curr);
      // Remove the last vertex from the stack and set i=
t as the
      // current one.
      curr =3D stack.top();
      stack.pop();
      log(LOG_DEBUG, "  New curr is " &=
lt;< curr->data);
    }
    else {
      // Add the vertex to the stack
      log(LOG_DEBUG, "* Pushing " <&=
lt; curr->data << " to stack."=
);
      stack.push(curr);
      // Take any of its neighbors, remove the edge betw=
een selected
      // neighbor and that vertex, and set that neighbor=
 as the
      // current vertex
      vertex<T>* n =3D curr->edges.at(0);
      log(LOG_DEBUG, "  Removing " <=
< curr->data << " <-> "n> << n->data);
      curr->remove_edge(n);
      curr =3D n;
      log(LOG_TRACE, *this);
    }
  }
  path.push_back(curr);
  return path;
}

template<typename T&=
gt;
ostream& operator << (ostream& out,=
 const vector<vertex<T>*>& vec)
{
  for(unsigned i =3D pan class=3D"dv">0; i < vec.size(); i++) {
    if(i > 0) {
      out << ", ";
    }
    out << vec.at(i)->data;
  }
  return out;
}

graph<char>* rubensburg_demo()
{
  // Set up graph
  graph<char>* gr =3D ne=
w graph<char>;
  vertex<char>* a =3D gr->add_vertex(an class=3D"st">'A');
  vertex<char>* b =3D gr->add_vertex(an class=3D"st">'B');
  vertex<char>* c =3D gr->add_vertex(an class=3D"st">'C');
  vertex<char>* d =3D gr->add_vertex(an class=3D"st">'D');
  vertex<char>* e =3D gr->add_vertex(an class=3D"st">'E');
  vertex<char>* f =3D gr->add_vertex(an class=3D"st">'F');
  vertex<char>* g =3D gr->add_vertex(an class=3D"st">'G');
  a->add_edge(b);
  a->add_edge(b);
  a->add_edge(e);
  a->add_edge(f);
  a->add_edge(g);
  b->add_edge(e);
  b->add_edge(f);
  c->add_edge(d);
  e->add_edge(c);
  e->add_edge(g);

  assert_eq(5, a->degree());
  assert_eq(2, g->degree());
  assert_eq(1, d->degree());

  return gr;
}

graph<int>* even_degree_demo()
{
  graph<int>* gr =3D new=
 graph<int>;
  vertex<int>* a =3D gr->add_vertex(n class=3D"dv">13);
  vertex<int>* b =3D gr->add_vertex(n class=3D"dv">16);
  vertex<int>* c =3D gr->add_vertex(n class=3D"dv">18);
  a->add_edge(b);
  a->add_edge(c);
  b->add_edge(c);
  assert_eq(2, a->degree());
  assert_eq(2, b->degree());
  assert_eq(2, c->degree());
  return gr;
}

// This is the actual K=C3=B6nigsberg graph, for which n=
o Euler path
// exists.
graph<string>* impossible_demo()
{
  graph<string>* gr =3D new graph<string=
>;
  vertex<string>* a =3D gr->add_vertex("au=
stin");
  vertex<string>* b =3D gr->add_vertex("ba=
ltimore");
  vertex<string>* c =3D gr->add_vertex("ch=
icago");
  vertex<string>* d =3D gr->add_vertex("da=
llas");
  a->add_edge(b);
  a->add_edge(b);
  a->add_edge(d);
  b->add_edge(c);
  b->add_edge(c);
  b->add_edge(d);
  c->add_edge(d);
  return gr;
}

int main()
{
  cout << "=3D=3D=3D=3D=3D=3D=3D Even-degree =
test\n";
  graph<int>* g0 =3D even_degree_demo();
  cout << g0->euler_path() << '>\n';
  delete g0;

  cout << "=3D=3D=3D=3D=3D=3D=3D Odd-degree t=
est\n";
  graph<char>* g1 =3D rubensburg_demo();
  cout << g1->euler_path() << '>\n';
  delete g1;

  cout << "=3D=3D=3D=3D=3D=3D=3D Impossible t=
est\n";
  graph<string>* g2 =3D impossible_demo();
  cout << g2->euler_path() << '>\n';
  delete g2;

  return 0;
}