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;
}
1 Answer 1
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. ...
};
setArestas()is called with values bigger than 100. \$\endgroup\$