ceCode cpp">#include <iostr=
eam>
#include <unordered_map>=

#include <unordered_set>=

#include <vector>
#include <stack>
#include "assertions.hh&q=
uot;
#define LOG_LEVEL LOG_TRACE
#include "debug-log.hh&qu=
ot;
using namespace std;

// Represent an undirected graph using hash maps and set=
s. The vertex
// type can be anything that supports equality and hashi=
ng.
template<typename ve=
rtex>
struct graph {
  void add_edge(vertex v1, vertex v2);
  void remove_edge(vertex v1, vertex v2);
  int degree(vertex v);
  vector<vertex> euler_path();
  ostream& show(ostream&);
private:
  typedef unordered_multiset<vertex> neighb=
ors;
  typedef unordered_map<vertex, unordered_mult=
iset<vertex>> adjancency_map;
  adjancency_map adjacency_map;
  void add_directed(vertex v1, vertex v2);
  void remove_directed(vertex v1, vertex v2);
};

// Print the graph's adjacency list
template<typename ve=
rtex>
ostream& graph<vertex>::show(ostream& out)
{
  for(typename adjancen=
cy_map::iterator i =3D adjacency_map.begin();
      i !=3D adjacency_map.end();
      i++)
    {
      out << i->first << ':'n>;
      for(typename neig=
hbors::iterator j =3D i->second.begin();
          j !=3D i->second.end();
          j++)
        {
          out << ' ' << *j;
        }
      out << '\nan>';
    }
  return out;
}

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

// Add an undirected edge.
template<typename ve=
rtex>
void graph<vertex>::add_edge(vertex v1, ver=
tex v2)
{
  add_directed(v1, v2);
  add_directed(v2, v1);
}

// Add directed edge (private).
template<typename ve=
rtex>
void graph<vertex>::add_directed(vertex v1,=
 vertex v2)
{
  typename adjancency_map::iterator i =3D adjacen=
cy_map.find(v1);
  if( adjacency_map.end() =3D=3D i) {
    adjacency_map[v1] =3D neighbors{v2};
  } else {
    i->second.insert(v2);
  }
}

// Remove undirected edge.
template<typename ve=
rtex>
void graph<vertex>::remove_edge(vertex v1, =
vertex v2)
{
  remove_directed(v1, v2);
  remove_directed(v2, v1);
}

// Remove directed edge (private). A little tricky becau=
se just doing
// .erase(v2) removes *all* the matching vertices from t=
he multiset.
// Using find then .erase in the iterator solves that.span>
template<typename ve=
rtex>
void graph<vertex>::remove_directed(vertex =
v1, vertex v2)
{
  typename neighbors::iterator i =3D adjacency_ma=
p.at(v1).find(v2);
  adjacency_map.at(v1).erase(i);
}

// Return the degree of given vertex.
template<typename ve=
rtex>
int graph<vertex>::degree(vertex v)
{
  return adjacency_map.at(v).size();
}

// 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 ve=
rtex>
vector<vertex> graph<vertex>::euler_path()
{
  // If all vertices have even degree, choose any of the=
m.
  typename adjancency_map::iterator i =3D adjacen=
cy_map.begin();
  vertex curr =3D i->first;
  // 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 !=3D adjacency_map.end(); i++) {
    if(degree(i->first) % 2=
 =3D=3D 1) {
      num_odd++;
      curr =3D i->first;
    }
  }
  log(LOG_INFO, "There were " << =
num_odd << " odd-degree vertices.">);
  vector<vertex> path;
  stack<vertex> 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 << '\n=
' << *this);
  // Repeat until the current vertex has no more neighbo=
rs and the
  // stack is empty.
  while(degree(curr) > 0pan> || stack.size() > 0) {
    // If current vertex has no neighbors,
    if(degree(curr) =3D=3D 0span>) {
      log(LOG_DEBUG, "* Adding " <&l=
t; curr << " 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);
    }
    else {
      // Add the vertex to the stack
      log(LOG_DEBUG, "* Pushing " <&=
lt; curr << " 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
      typename neighbors::iterator n =3D adjacenc=
y_map.at(curr).begin();
      log(LOG_DEBUG, "  Removing " <=
< curr << " <-> " <&l=
t; *n);
      remove_edge(curr, *n);
      curr =3D *n;
      log(LOG_TRACE, *this);
    }
  }
  path.push_back(curr);
  return path;
}

// Grr why isn't this just in the standard library I=
 have to write it
// every damn time.
template<typename T&=
gt;
ostream& operator << (ostream& out,=
 const vector<T>& vec)
{
  for(unsigned i =3D pan class=3D"dv">0; i < vec.size(); i++) {
    if(i > 0) {
      out << ", ";
    }
    out << vec.at(i);
  }
  return out;
}

graph<char> rubensburg_demo()
{
  // Set up graph
  graph<char> g;
  g.add_edge('A','=
B');
  g.add_edge('A','=
B');
  g.add_edge('A','=
E');
  g.add_edge('A','=
F');
  g.add_edge('A','=
G');
  g.add_edge('B','=
E');
  g.add_edge('B','=
F');
  g.add_edge('C','=
D');
  g.add_edge('E','=
C');
  g.add_edge('E','=
G');

  assert_eq(5, g.degree('A=
'));
  assert_eq(2, g.degree('G=
'));
  assert_eq(1, g.degree('D=
'));

  return g;
}

graph<int> even_degree_demo()
{
  graph<int> g;
  g.add_edge(13, 16);
  g.add_edge(13, 18);
  g.add_edge(16, 18);
  assert_eq(2, g.degree(13an>));
  assert_eq(2, g.degree(16an>));
  assert_eq(2, g.degree(18an>));
  return g;
}

// This is the actual K=C3=B6nigsberg graph, for which n=
o Euler path
// exists.
graph<string> impossible_demo()
{
  graph<string> g;
  g.add_edge("austin", t">"baltimore");
  g.add_edge("austin", t">"baltimore");
  g.add_edge("austin", t">"dallas");
  g.add_edge("baltimore", =3D"st">"chicago");
  g.add_edge("baltimore", =3D"st">"chicago");
  g.add_edge("baltimore", =3D"st">"dallas");
  g.add_edge("chicago", st">"dallas");
  return g;
}

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() << 'an class=3D"sc">\n';

  cout << "=3D=3D=3D=3D=3D=3D=3D Odd-degree t=
est\n";
  graph<char> g1 =3D rubensburg_demo();
  cout << g1.euler_path() << 'an class=3D"sc">\n';

  cout << "=3D=3D=3D=3D=3D=3D=3D Impossible t=
est\n";
  graph<string> g2 =3D impossible_demo();
  cout << g2.euler_path() << 'an class=3D"sc">\n';

  return 0;
}