Re: decision making tree for a euler walk

[ruben safir]

On 02/24/2017 05:11 AM, ruben safir wrote:
> I'm just not quiet solving this. I think it walked the tree correctly
> but my tunnel count is a wee bit off.
>
>

~~~~ {.cpp}
#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <stack>
#include "assertions.hh"
#define LOG_LEVEL LOG_TRACE
#include "debug-log.hh"
using namespace std;

// Represent an undirected graph using hash maps and sets. The vertex
// type can be anything that supports equality and hashing.
template<typename vertex>
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> neighbors;
typedef unordered_map<vertex, unordered_multiset<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 vertex>
ostream& graph<vertex>::show(ostream& out)
{
for(typename adjancency_map::iterator i = adjacency_map.begin();
i != adjacency_map.end();
i++)
{
out << i->first << ':';
for(typename neighbors::iterator j = i->second.begin();
j != i->second.end();
j++)
{
out << ' ' << *j;
}
out << '\n';
}
return out;
}

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

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

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

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

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

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

// Calculate and return an euler path. Algorithm basically taken from
// here: http://www.graph-magics.com/articles/euler.php
//
// NOTE: this is destructive -- it removes edges from the graph. So if
// you need the graph afterwards, make a copy.
template<typename vertex>
vector<vertex> graph<vertex>::euler_path()
{
// If all vertices have even degree, choose any of them.
typename adjancency_map::iterator i = adjacency_map.begin();
vertex curr = i->first;
// If there are exactly 2 vertices having an odd degree: choose one
// of them. This will be the current vertex.
unsigned num_odd = 0;
for( ; i != adjacency_map.end(); i++) {
if(degree(i->first) % 2 == 1) {
num_odd++;
curr = i->first;
}
}
log(LOG_INFO, "There were " << num_odd << " odd-degree vertices.");
vector<vertex> path;
stack<vertex> stack;
if(num_odd != 2 && num_odd != 0) {
log(LOG_ERROR, "Sorry, no Euler path exists.");
return path;
}
log(LOG_DEBUG, "Starting at " << curr << '\n' << *this);
// Repeat until the current vertex has no more neighbors and the
// stack is empty.
while(degree(curr) > 0 || stack.size() > 0) {
// If current vertex has no neighbors,
if(degree(curr) == 0) {
log(LOG_DEBUG, "* Adding " << curr << " to path.");
// Add it to path
path.push_back(curr);
// Remove the last vertex from the stack and set it as the
// current one.
curr = stack.top();
stack.pop();
log(LOG_DEBUG, " New curr is " << curr);
}
else {
// Add the vertex to the stack
log(LOG_DEBUG, "* Pushing " << curr << " to stack.");
stack.push(curr);
// Take any of its neighbors, remove the edge between selected
// neighbor and that vertex, and set that neighbor as the
// current vertex
typename neighbors::iterator n = adjacency_map.at(curr).begin();
log(LOG_DEBUG, " Removing " << curr << " <-> " << *n);
remove_edge(curr, *n);
curr = *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>
ostream& operator << (ostream& out, const vector<T>& vec)
{
for(unsigned i = 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(13));
assert_eq(2, g.degree(16));
assert_eq(2, g.degree(18));
return g;
}

// This is the actual Königsberg graph, for which no Euler path
// exists.
graph<string> impossible_demo()
{
graph<string> g;
g.add_edge("austin", "baltimore");
g.add_edge("austin", "baltimore");
g.add_edge("austin", "dallas");
g.add_edge("baltimore", "chicago");
g.add_edge("baltimore", "chicago");
g.add_edge("baltimore", "dallas");
g.add_edge("chicago", "dallas");
return g;
}

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

cout << "======= Odd-degree test\n";
graph<char> g1 = rubensburg_demo();
cout << g1.euler_path() << '\n';

cout << "======= Impossible test\n";
graph<string> g2 = impossible_demo();
cout << g2.euler_path() << '\n';

return 0;
}
~~~~