I AM MISSING SOMETHING FROM THIS CODE!!! PLEASE HELP ME FINISH IT!! DO NOT JUST
ID: 3834128 • Letter: I
Question
I AM MISSING SOMETHING FROM THIS CODE!!! PLEASE HELP ME FINISH IT!! DO NOT JUST COPY AND PASTE WITHOUT DOING ANYTHING!
THE OTHER TWO PIECES OF CODE ARE THE HEADER FILE AND THE IMPLAMENTATION FILE!!
PLEASE SOMEONE HELP ME FINISH THIS CODE!!!! WHERE IT SAYS "NEED THE CORRECT CODE HERE" IS WHERE I NEED THE HELP CAN SOMEONE JUST HELP ME AND NOT JUST COPYING AND PASTING WITHOUT DOING ANYTHING THAT IS NOT WHAT I WAS ASKING FOR!
PLEASE and THANKS!
DO NOT JUST COPY AND PASTE MY CODE WITHOUT DOING ANYTHING HOW IS THAT GOING TO HELP ME!!!!
Test and implement the function euler-circuit
#include <cstdlib>
#include <iostream>
#include <deque>
#include <string>
#include "digraph.h"
using namespace std;
typedef deque Stack; //Defines a stack as a deque of integers.
bool isEmpty(Stack s); //Checks whether s is empty.
int top(Stack s); //Returns the top element of s.
void pop(Stack s); //Pops s.
void push(Stack s, int x); //Pushes x onto s.
Stack euler_circuit(Digraph &g); //Returns, in a stack, an eulerian circuit of g.
//Note that g is passed by reference.
//If you decide to implement this function in a way
//that would modify g (such as deleting arcs), then
//you should pass g by value.
void output(const Digraph g); //Outputs the digraph g.
int main()
{
Stack result; //to hold the eulerian circuit
Digraph my_digraph;
int n; //order of my_digraph
int m; //size of my_digraph
int u,v; //nodes
char paren, comma;
string node_label[100]; //node labels for my_digraph
bool finished = false;
cout << "This program prompts the user to input a digraph." << endl;
cout << "It then checks whether id(x) = od(x) for every node x." << endl;
cout << "If this condition is not satisfied, the user is allowed" << endl;
cout << "to modify the digraph, so as to satisfy this condition." << endl;
cout << "Then, assuming the digraph is strongly connected, the" << endl;
cout << "program computes and outputs an eulerian circuit." << endl << endl;
while(! finished)
{
cout << "Input the order (number of nodes): ";
cin >> n;
my_digraph = Digraph(n);
cout << "Input the labels for the nodes, with one label per line." << endl;
for (int i = 1; i <= n; i++)
{
cout << "Node " << i << ": ";
cin >> node_label[i];
}
cout << "Input the size (number of arcs): ";
cin >> m;
cout << "Input the arcs, each in the form (u,v)," << endl;
cout << "with 0 < u,v <= " << n << ":"<< endl;
for (int i = 1; i <= m; i++)
{
cin >> paren;
cin >> u;
cin >> comma;
cin >> v;
cin >> paren;
my_digraph.add_arc(u,v);
}
cout << endl; //Output my_digraph. output(my_digraph);
//Check whether id(x) = od(x) for every node.
//If this condition is not satisfied, allow the user
//to modify my_digraph so that it is satisfied.
cout << "Attempting to find an eulerian circuit ..."<< endl;
result = euler_circuit(my_digraph);
}
cout << endl;
system("pause");
return 0;
}
bool isEmpty(Stack s)
{
return s.empty();
}
int top(Stack s)
{
return s.front();
}
void pop(Stack s)
{
s.pop_front();
}
void push(Stack s, int x)
{
s.push_front(x);
}
Stack euler_circuit(Digraph &g)
{
Stack result;
cout << "NEED THE CORRECT CODE PUT HERE!!!!! ." << endl;
return result;
}
Digraph Header:
class Digraph {
// A class for directed graphs having up to 99 nodes.
public:
Digraph(int n);
//Constructor. Creates a digraph with n nodes labelled 1, 2, ..., n
//and no arcs.
Digraph();
//Default constructor. Creates a digraph with 1 node and no arcs.
int order();
//g.order() returns the order - that is, the number of nodes -
//of the digraph g.
int size();
//g.size() returns the size - that is, the number of arcs -
//of the digraph g.
void add_node();
//g.add_node() adds a new node (labelled g.order() + 1) to the digraph g.
void delete_node();
//g.delete_node(v) deletes the node labelled g.order from the digraph g.
bool adjacent_to(int u, int v);
//g.adjacent_to(u,v) determines whether node u is adjacent to node v
//in the digraph g.
void add_arc(int u, int v);
//g.add_arc(u,v) adds the arc (u,v) to the digraph g.
//If the arc (u,v) already exists, then g.add_arc(u,v) does nothing.
void delete_arc(int u, int v);
//g.delete_arc(u,v) deletes the arc (u,v) from the digraph g.
//If the arc (u,v) doesn't exist, then g.delete_arc(u,v) does nothing.
int indegree(int v);
//g.indegree(v) returns the indegree of the node v in the digraph g.
int outdegree(int v);
//g.outdegree(v) returns the outdegree of the node v in the digraph g.
private:
const static int MAX_ORDER = 100;
//Actually, the maximum order is 99, since there is no node labelled 0.
int ord; //order of the digraph
int siz; //size of the digraph
int is_adjacent[MAX_ORDER][MAX_ORDER];
//For 0 < u,v <= order, is_adjacent[u,v] is true iff
//node u is adjacent to node v in the digraph.
//We'll use is_adjacent[0][v] for the indegree of v and
//is_adjacent[u][0] for the outdegree of u.
};
digraph-implementation:
#include "digraph.h"
Digraph::Digraph(int n)
{
ord = n;
siz = 0;
for (int i = 0; i <= n; i++)
for (int j = 0; j <= n; j++)
is_adjacent[i][j] = 0;
//Recall: false is represented by 0
}
Digraph::Digraph()
{
ord = 1;
siz = 0;
for (int i = 0; i <= 1; i++)
for (int j = 0; j <= 1; j++)
is_adjacent[i][j] = 0;
//Recall: false is represented by 0
}
int Digraph::order()
{
return ord;
}
int Digraph::size()
{
return siz;
}
void Digraph::add_node()
{
ord = ord++; //Increment the order.
//Make the new node have indegree 0, outdegree 0,
//and be not adjacent to or from any existing nodes.
for (int j = 0; j <= ord; j++)
is_adjacent[ord][j] = 0;
for (int i = 0; i <= ord; i++)
is_adjacent[i][ord] = 0;
}
void Digraph::delete_node()
{
//Decrement the outdegree of any node i adjacent to
//the node labelled ord.
for(int i = 1; i < ord; i++)
if(is_adjacent[i][ord] == 1)
is_adjacent[i][0]--;
//Decrement the indegree of any node j adjacent from
//the node labelled ord.
for(int j = 1; j < ord; j++)
if(is_adjacent[ord][j] == 1)
is_adjacent[0][j]--;
ord = ord--; //Decrement the order
}
bool Digraph::adjacent_to(int u, int v)
{
return static_cast<bool>(is_adjacent[u][v]);
}
void Digraph::add_arc(int u, int v)
{
if(is_adjacent[u][v] == 0)
{//If the arc is not already present ...
is_adjacent[u][v] = 1; //Add the arc.
is_adjacent[u][0]++; //Increment the outdegree of u.
is_adjacent[0][v]++; //Increment the indegree of v.
}
}
void Digraph::delete_arc(int u, int v)
{
if(is_adjacent[u][v] == 1)
{//If the arc is present ...
is_adjacent[u][v] = 0; //Delete the arc.
is_adjacent[u][0]--; //Decrement the outdegree of u.
is_adjacent[0][v]--; //Decrement the indegree of v.
}
}
int Digraph::indegree(int v)
{
return is_adjacent[0][v];
}
int Digraph::outdegree(int v)
{
return is_adjacent[v][0];
}
Explanation / Answer
Hi I have did this program few days back. It works fine in C++ compilter. But it was static. But it may help you.
/*
* C++ Program to Implement Euler Circuit Problem
*/
#include<iostream>
#include<conio.h>
#include<list>
using namespace std;
class Graph
{
int V;
list<int> *adj;
public:
Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
void addEdge(int v, int w);
int isEulerian();
bool isConnected();
void DFSUtil(int v, bool visited[]);
};
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w);
adj[w].push_back(v);
}
void Graph::DFSUtil(int v, bool visited[])
{
visited[v] = true;
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
{
if (!visited[*i])
{
DFSUtil(*i, visited);
}
}
}
bool Graph::isConnected()
{
bool visited[V];
int i;
for (i = 0; i < V; i++)
{
visited[i] = false;
}
for (i = 0; i < V; i++)
{
if (adj[i].size() != 0)
{
break;
}
}
if (i == V)
{
return true;
}
DFSUtil(i, visited);
for (i = 0; i < V; i++)
{
if (visited[i] == false && adj[i].size() > 0)
{
return false;
}
}
return true;
}
int Graph::isEulerian()
{
if (isConnected() == false)
{
return 0;
}
int odd = 0;
for (int i = 0; i < V; i++)
{
if (adj[i].size() & 1)
{
odd++;
}
}
if (odd > 2)
{
return 0;
}
return (odd)? 1 : 2;
}
void test(Graph &g)
{
int res = g.isEulerian();
if (res == 0)
{
cout << "Graph is not Eulerian ";
}
else if (res == 1)
{
cout << "Graph has a Euler path ";
}
else
{
cout << "Graph has a Euler cycle ";
}
}
int main()
{
Graph g1(5);
g1.addEdge(1, 0);
g1.addEdge(0, 2);
g1.addEdge(2, 1);
g1.addEdge(0, 3);
g1.addEdge(3, 4);
test(g1);
Graph g2(5);
g2.addEdge(1, 0);
g2.addEdge(0, 2);
g2.addEdge(2, 1);
g2.addEdge(0, 3);
g2.addEdge(3, 4);
g2.addEdge(4, 0);
test(g2);
Graph g3(5);
g3.addEdge(1, 0);
g3.addEdge(0, 2);
g3.addEdge(2, 1);
g3.addEdge(0, 3);
g3.addEdge(3, 4);
g3.addEdge(1, 3);
test(g3);
Graph g4(3);
g4.addEdge(0, 1);
g4.addEdge(1, 2);
g4.addEdge(2, 0);
test(g4);
Graph g5(3);
test(g5);
getch();
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.