PLEASE SOMEONE HELP ME FINISH THIS CODE!!!! PLEASE and THANKS! Test and implemen
ID: 3832196 • Letter: P
Question
PLEASE SOMEONE HELP ME FINISH THIS CODE!!!! PLEASE and THANKS! 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(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
#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;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.