THIS IS SUPPOSED TO BE A C++ PROGRAM! THIS SHOULD BE SELF EXPLANITORY. THE BOLDED CODE AT THE BOTTOM IS WHAT NEEDS TO BE FINISHED. TWO PIECES OF CODE NEED TO BE INSERTED. WHERE IT SAYS "//?" AND THE CODE THAT SAYS"UNDER CONSTRUCTION".I AM SUPPOSED TO FINISH THE CODE TO TEST THE FUNCTION "euler_circuit" I HAVE IT BOLDED SO IT WILL BE EASY TO KNOW WHICH CODE NEEDS TO BE WORKED ON. THANKS FOR ANY AND ALL HELP I APPRECIATE IT!!!

Implement and test the function euler_circuit, as described in class. You'll need the following files:

the header file for the Digraph class;

the implementation file for the Digraph class;

the template for euler-circuit-test;

"diagraph-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]; }

"euler-circuit-test" code

#include #include #include #include #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) { //? }

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 << "Under construction." << endl; return result; }