3
\$\begingroup\$

I'm doing a project to find the Eulerian path. Cane someone find an example where the algorithm is wrong? The function EulerianPath recursively prints the Eulerian Path.

Some some parts of the code are in Portuguese.

#include <bits/stdc++.h>
using namespace std;

class Grafo{
    private:
        int N,A; // N: Vertices; A: Arestas;
        int graph[100][100]; // matriz do grafo
        bool visited[100];
    public:
        Grafo(int graphsize);
        int getArestas();
        void setArestas(int x, int y);
        bool isComplete();
        int getDegree(int v);
        bool isEuler();
        void EulerCicle();
        void setNodes(int k);
        int maxArestas();
        int Goodman();
        void DFS(int);
        void BFS(int);
        /* Dijkstra */
        int minDistance( int*, bool* );
        int printSolution(int dist[], int n, int parent[], int i, int src);
        void Dijkstra( int, int );
        void printPath(int parent[], int j);
        /**/
        void EulerianPath( int src );
};

Grafo::Grafo(int graphsize){
    N = graphsize;
    memset(graph, 0, sizeof(graph));
    memset(visited, false, sizeof(visited));
}

int Grafo::getArestas(){

    return 0;
}

void Grafo::setNodes(int k){
        N = k;
}

void Grafo::setArestas(int x, int y){
        graph[x-1][y-1] = 1;
        A++;
}

int Grafo::maxArestas(){
    return ((N*(N-1))/ 2);
}

int Grafo::getDegree(int v){
        int aux = 0;
        for(int i = 0; i < N; i++){
            if(graph[i][v] == 1){
                aux++;
            }
        }
        for(int j = 0; j < N; j++){
            if(graph[v][j] == 1){
                aux++;
            }
        }
    return aux/2;
}

bool Grafo::isComplete(){
    if( A == maxArestas())
        return true;
    return false;
}

bool Grafo::isEuler(){
    bool aux = true;
    for(int i = 0; i < N; i++){
        if(getDegree(i) % 2 != 0)
        {
            aux = false;
            break;
        }
    }
    return aux;
}

void Grafo::DFS( int actual ){
    visited[actual] = true;
    for( int i = 0; i < N; i++ )
    {
        if( graph[actual][i] == 1 )
        {
            if( !visited[i] )
            {
                DFS( i );
            }
        }
    }
}

void Grafo::BFS( int s )
{
    queue<int> Q;

    visited[s] = true;
    Q.push(s);

    while( !Q.empty() )
    {
        s = Q.front();
        cout << s+1 << " ";
        Q.pop();

        for( int i = 0; i < N; i++ )
        {
            if( !visited[i] && graph[i][s] == 1 )
            {
                //cout << "here" << endl;
                visited[i] = true;
                Q.push(i);
            }
        }
    }
}

int Grafo::Goodman( ){
    int cont = 0;
    for( int i = 0; i < N; i++ ){
        if( !visited[i] ){
            DFS( i );
            cont++;
        }
    }
    return cont;
}

/* Dijkstra */
int Grafo::minDistance(int dist[], bool sptSet[])
{
   // Initialize min value
   int min = INT_MAX, min_index;

   for (int v = 0; v < N; v++)
     if (sptSet[v] == false && dist[v] <= min)
         min = dist[v], min_index = v;

   return min_index;
}
//
void Grafo::printPath(int parent[], int j )
{
    // Base Case : If j is source
    if (parent[j]==-1)
        return;

    printPath(parent, parent[j]);

    printf("%d ", j);
}

// A utility function to print the constructed distance array
int Grafo::printSolution(int dist[], int n, int parent[], int i, int src )
{
    printf("Vertex\t  Distance\tPath");
//    for (int i = 1; i < N; i++)
//    {  
        cout << endl << src << " -> " << i << " \t\t " << dist[i] << "\t" << src << endl;
        printPath(parent, i );
//    }
}

void Grafo::Dijkstra( int src, int target )
{
     int distancia[N];     // The output array.  distancia[i] will hold the shortest
                      // distanciaance from src to i

     bool sptSet[N]; // sptSet[i] will true if Nertex i is included in shortest
                     // path tree or shortest distanciaance from src to i is finalized

     int parent[N];
     // Initialize all distances as INFINITE and stpSet[] as false
     for (int i = 0; i < N; i++)
        distancia[i] = INT_MAX, sptSet[i] = false, parent[src] = -1;

     // Distance of source vertex from itself is always 0
     distancia[src] = 0;

     // Find shortest path for all vertices
     for (int counter = 0; counter < N-1; counter++)
     {
       // Pick the minimum distance vertex from the set of vertices not
       // yet processed. u is always equal to src in first iteration.
       int u = minDistance(distancia, sptSet);

       // Mark the picked vertex as processed
       sptSet[u] = true;

       // Update distancia value of the adjacent vertices of the picked vertex.
       for (int v = 0; v < N; v++)

         // Update distancia[v] only if is not in sptSet, there is an edge from
         // u to v, and total weight of path from src to  v through u is
         // smaller than current value of distancia[v]
         if (!sptSet[v] && graph[u][v] && distancia[u] != INT_MAX
                                       && distancia[u]+graph[u][v] < distancia[v])
         {
            parent[v] = u;
            distancia[v] = distancia[u] + graph[u][v];
         }
     }

     // print the constructed distance array
     printSolution(distancia, N, parent, target, src );
}
/* Dijkstra FIM */

void Grafo::EulerianPath( int src )
{  

    for (int i = 0; i < N; ++i)
    {
        if( graph[src][i] != 0 )
        {
            graph[src][i] = 0;
            graph[i][src] = 0;
            EulerianPath( i );
        }
    }
    cout << src+1 << endl;

}

int main(){

    int x, y, k;

    cin >> k;
    Grafo G(k);

    while(cin >> x >> y && x != 0 && y != 0 ){
        G.setArestas(x,y);
        G.setArestas(y,x);
    }
    if( G.isEuler() )
        G.EulerianPath( 0 );

    return 0;
}
\$\endgroup\$
  • \$\begingroup\$ Your code can be easily broken when setArestas() is called with values bigger than 100. \$\endgroup\$ – πάντα ῥεῖ Jan 19 '17 at 10:23
4
\$\begingroup\$

A few points:

1. Do not use #include <bits/stdc++.h>

As pointed out in detail here, this may get you in trouble and isn't really portable code.

Always just include the standard headers you need like

#include <queue>

2. Do not use using namespace std;

Again there's a Stack Overflow Q&A pointing out in detail why you shouldn't do so.

3. Keep getter / setter functions consistent

Your function

    int getArestas();

is inconsistent with

    void setArestas(int x, int y);

One would expect a signature like

    void getArestas(int& x, int& y);

Also your implementation always returning 0 looks weird:

int Grafo::getArestas(){

    return 0;
}

If you actually don't need that function, just omit it.

4. Check input values for fixed boundaries

someone can help me to find an example to make the algorithm wrong

At least this point may easily break your code.

You introduce a fixed boundary of 100 when declaring your arrays

    int graph[100][100]; // matriz do grafo
    bool visited[100];

but never check that x and y are smaller than or equal to 100 before dereferencing the array:

void Grafo::setArestas(int x, int y){
        graph[x-1][y-1] = 1;
        A++;
}

This will lead to calling undefined behavior if x or y are grater than 100.

5. Do not use raw C-style arrays in C++

The C++ standard provides the std::array class to specify fixed arrays.

Though in your case it is probably even better to use std::vector instead, since the maximum size is taken from input more or less.

6. Prefer formatted text output to streams in C++

While it is legit to use printf() in C++ code, you should prefer to use the std::ostream operator<<(std::ostream&, T) because it's more typesafe than using the printf() format string.

7. Use bool return values efficiently

For example this piece of code

bool Grafo::isEuler(){
    bool aux = true;
    for(int i = 0; i < N; i++){
        if(getDegree(i) % 2 != 0)
        {
            aux = false;
            break;
        }
    }
    return aux;
}

can be made more efficiently readable as

bool Grafo::isEuler(){
    for(int i = 0; i < N; i++){
        if(getDegree(i) % 2 != 0)
        {
            return false;
        }
    }
    return true;
}

Also

bool Grafo::isComplete(){
    if( A == maxArestas())
        return true;
    return false;
}

can be simplified as

bool Grafo::isComplete(){
    return (A == maxArestas());
}

8. Keep language consistent for naming types, variables and functions

Yes the code have some parts in Portuguese.

You have a weird mix in the style of language used to name types, variables and functions:

class Grafo{ // << Portugese
    private:
        int graph[100][100]; // << English with portugese comment (matriz do grafo)
        bool visited[100]; // << English
    public:
        Grafo(int graphsize); // << Portugese / Egnlish 
        int getArestas();  // << Portugese
        void setArestas(int x, int y);  // << Portugese
        bool isComplete();   // << English
        int getDegree(int v);  // << English
        bool isEuler();  // << English
        void EulerCicle();  // << English
        void setNodes(int k);  // << English
        int maxArestas();   // << Portugese
        int Goodman();   // << English
        void DFS(int);
        void BFS(int);
        /* Dijkstra */
        int minDistance( int*, bool* ); // << English
        int printSolution(int dist[], int n, int parent[], int i, int src);   // << English
        void Dijkstra( int, int );
        void printPath(int parent[], int j); // << English
        /**/
        void EulerianPath( int src ); // << English
};

Choose any language, but keep it consistent please. My personal preference is to use English for naming in code and comments as well.
This will be most widely understood by anyone else who's reading your code.

9. Use const whenever appropriate

You should mark parameters or member functions as const whenever it is appropriate, i.e. these aren't changing the parameters or class' current state:

class Grafo{ // << Portugese
        int getArestas() const;
        bool isComplete() const;
        int getDegree(int v) const;
        bool isEuler() const;
        // etc. ...
};
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.