Finding euler cycle

Question

I have an application which creates graph with an Euler cycle. My second application is for finding Euler cycle.

Creating Euler cycle:

1. Create a cycle e.g. 3->6->5->2->0->1->4->3 because Euler cycle should be connected graph
2. Then creating random edges.
3. Saving graph to file.

Finding Euler cycle is based od DFS.

Finding Euler cycle works for 100,200,300 nodes. When it's e.g. 500, application don't show Euler cycle. If you have any suggestions, what should I change in code, post it.

Here is a code for creating graph with Euler cycle:

#include<iostream>
#include<vector>
#include<algorithm>
#include<vector>
#include<ctime>
#include<cstdlib>
#include<list>
#include<stack>
#include<ctime>
#include<fstream>
using namespace std;

    bool matrix[1500][1500];
int main()
{
    srand(time(0));
    ofstream zapis;
    zapis.open("graph cycle euler.txt");

vector<int> cycle;
    //bool macierz[500][500];
    int N, density;
cout<<"N and density: "<<endl;
cin>>N>>density;

    for (int i = 0; i<1500; i++)
    {
        for (int j=0; j<1500; j++)
        {
            matrix[i][j]=0;
        }
    }


for (int i = 0; i<N; i++)
{
    cycle.push_back(i);
}


random_shuffle (cycle.begin(), cycle.end());


matrix[cycle[0]][cycle[cycle.size()-1]]=1;
matrix[cycle[cycle.size()-1]][cycle[0]]=1;

for (int i=0; i<cycle.size()-1; i++)
{
    matrix[cycle[i]][cycle[i+1]]=1;
    matrix[cycle[i+1]][cycle[i]]=1;
//    cout<<cycle[i]<<" "<<cycle[i+1]<<endl;
}


int randnumber, randnumeber2,randnumber3;

//ile=ile-2*N;
int howMany=0;
for (int i=0; i<N; i++)
{
    howMany=howMany+i;
}
howMany=howMany*60/100-N;

while(howMany>=0)
{

    randnumber=rand()%N;
    randnumeber2=rand()%N;
    randnumber3=rand()%N;

    if((matrix[randnumber][randnumeber2]==0) && (matrix[randnumeber2][randnumber3]==0) && (matrix[randnumber][randnumber3]==0) && (randnumber!=randnumeber2) && (randnumber!=randnumber3) && (randnumeber2!=randnumber3))
    {
        matrix[randnumber][randnumeber2]=1;
        matrix[randnumeber2][randnumber]=1;
        matrix[randnumeber2][randnumber3]=1;
        matrix[randnumber3][randnumeber2]=1;
        matrix[randnumber][randnumber3]=1;
        matrix[randnumber3][randnumber]=1;

        howMany=howMany-3;
    }
}

int M=0;
for (int i=0; i<N; i++)
{
    for (int j=0; j<N; j++)
    {
        if(matrix[i][j]==1)
        M++;
    }
}

zapis<<N<<endl<<density<<endl<<M<<endl;

for (int i=0; i<N; i++)
{
    for (int j=0; j<N; j++)
    {
        if(matrix[i][j]==1)
        zapis<< i <<" "<< j<<endl;
    }
}

}

End here is my code for finding Euler cycle.

#include<iostream>
#include<vector>
#include <algorithm>
#include <vector>
#include <ctime>
#include <cstdlib>
#include<list>
#include <stack>
#include<fstream>
using namespace std;

int s;
list<int> L[3000];
stack<int> stos;
void dfs (int v)
{

while (!L[v].empty())
    {

        int x=L[v].front();
        L[v].pop_front();
        for (list<int>::iterator y=L[x].begin(); y != L[x].end(); y++)
            if (v==(*y))
            {
                L[x].erase(y); break;
            }
    dfs(x);
    }
stos.push(v);
}

int main()
{
    ifstream odczyt;
    odczyt.open("graph cycle euler.txt");
int N, gestosc, m;
odczyt>>N>>gestosc>>m;

int w1,w2;
for (int i=0; i<m; i++)
{
    odczyt>>w1>>w2;
    L[w1].push_back(w2);
    //L[w2].push_back(w1);
}

int start=0;

dfs(start);

    while(!stos.empty())
    {
        cout<<stos.top()<<" ";
        stos.pop();
    }
}

Answer 1

The application does not show or keeps computing? I am guessing your program with 500 is running forever due to if((matrix[randnumber][randnumeber2]==0) && (matrix[randnumeber2][randnumber3]==0) ... this condition is not true for the random numbers generated and thus howMany is not decremented, and the loop continues for a long time.

I am not sure what logic you are using for creating the graph. If the degree of all vertices is even, euler cycle will always exist in the graph. You have lot of random in your code, which may take a while.

You really do not need to do all the DFS and other things you have done to find euler cycle. Here is a simple logic:

-- Check to make sure degree of all vertices is even. If not, Euler cycle does not exist. The proof is pretty straightforward and left as an exercise :)

"As a generalization of the Königsberg bridge problem, Euler showed (without proof) that a connected graph has an Eulerian cycle iff it has no graph vertices of odd degree." --- http://mathworld.wolfram.com/EulerianCycle.html

-- Pick any vertex and keep traversing any edge incident on the vertex, which has not been traversed earlier. Keep traversing.....Eventually you will end up with the euler cycle, when all your edges have been traversed.

Please note that this is not same as hamiltonian cycle problem which is NP-C. Finding Euler cycle is polynomial, O(E), since you will be traversing every edge just once.