The Eulerian Path Problem

The Euleraian Problem originated from the Seven Bridges of Konigsberg http://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg. The abstraction of the problem is to construct an Eulerian Path http://en.wikipedia.org/wiki/Eulerian_path

Here I implemented an algoirthm based on http://tuxv.blogspot.com/2007/05/eulerian-path.html. The problem with the original solution is that the author seems confused with directed and undirected graph. Essentially, the Eulerian Path solves a problem of a directed graph (although the appearance of the graph may be undirected). The clever discovery here is that an edge can be walked only once thus making it directed when exploring a solution.

Quote:
Constructing Eulerian paths and cycles

Consider a graph known to have all edges in the same component and at most two vertices of odd degree. We can construct an Eulerian path (not a cycle) out of this graph by using Fleury's algorithm, which dates to 1883. We start with a vertex of odd degree—if the graph has none, then start with any vertex. At each step we move across an edge whose deletion does not result in more than one connected component, unless we have no choice, then we delete that edge. At the end of the algorithm there are no edges left, and the sequence of edges we moved across forms an Eulerian cycle if the graph has no vertices of odd degree or an Eulerian path if there are two vertices of odd degree.

The definition of a Hamiltonian path is very similar (a Hamiltonian path visits every vertex exactly once, while an Eulerian path visits every edge exactly once). In practice, however, it is much more difficult to construct a Hamiltonian path or determine whether a graph is Hamiltonian, as that problem is NP-complete

Following is the C++ source code:

#include < iostream>
#include < vector>
#include < list>

using namespace std;
#define N 4
/*
int bridges[N][N] = {
    {0, 1, 0, 1},
    {1, 0, 1, 1},
    {0, 1, 0, 1},
    {0, 0, 0, 0},
};
*/
int bridges[N][N] = {
    {0, 1, 0, 1},
    {1, 0, 1, 1},
    {0, 1, 0, 1},
    {0, 0, 1, 0},
};

#define graph bridges

list< int> path;

void walk(int src){
    for(int i = 0; i < N; i ++)
        if(graph[src][i]){
            graph[src][i] = 0;
            walk(i);
        }else{
            if(graph[i][src]){
                graph[i][src] = 0;
                walk(i);
            }
        }
    path.push_back(src);
}

int main(){
    walk(0);

    while(!path.empty()){
        cout << path.back() << endl;
        path.pop_back();
    }
}

The graph (ajacency-matrix represention) is directed because it's not symmetric (the transpose is not equal to the original matrix). The problem solver has the freedom to choose a direction for an edge. When designing the ajacency-matrix, it's important to observe the rule that one must start from a node with odd degree. Suppose the node is numbered s, and it has 2k+1 degree, then it must have k+1 outgoing edges and k incoming edges.