THIS IS SUPPOSED TO BE A C++ PROGRAM! THIS SHOULD BE SELF EXPLANITORY. THE BOLDE
ID: 3822732 • Letter: T
Question
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<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];
}
"euler-circuit-test" code
#include <cstdlib>
#include <iostream>
#include <deque>
#include <string>
#include "digraph.h"
using namespace std;
typedef deque<int> 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;
}
Explanation / Answer
Answer:
#include <cstdio>
#include <vector>
#include <cstring>
#define SIZE 1000
using namespace std;
typedef vector <int> value;
value G[SIZE], read[SIZE];
bool input[SIZE];
int begin[SIZE], end[SIZE], request[SIZE], t = -1, high = 0, V, E;
void reverse_function(int i) {
input[i] = true;
for(value::iterator it = read[i].begin(); it != read[i].end(); it++)
if(!input[*it])
reverse_function(*it);
t++;
end[i] = t;
}
void dfs(int i) {
input[i] = true;
begin[i] = high;
for(value::iterator it = G[i].begin(); it != G[i].end(); it++)
if(!input[*it])
dfs(*it);
}
bool stronglyConnected(int u, int v) {
return begin[u] == begin[v];
}
int main() {
int i, u, v, inc, Q;
scanf("%d %d", &V, &E);
for(i=0; i<E; i++) {
scanf("%d %d", &u, &v);
G[u].push_back(v);
read[v].push_back(u);
}
printf("Original graph : ");
for(i=0; i<V; i++) {
if(!G[i].empty()) {
printf("%d : ", i);
for(value::iterator it = G[i].begin(); it != G[i].end(); it++)
printf("%d ", *it);
printf(" ");
}
}
printf("Reverse graph : ");
for(i=0; i<V; i++) {
if(!read[i].empty()) {
printf("%d : ", i);
for(value::iterator it = read[i].begin(); it != read[i].end(); it++)
printf("%d ", *it);
printf(" ");
}
}
memset(input, false, V*sizeof(bool));
for(i=0; i<V; i++) {
if(!input[i])
reverse_function(i);
request[end[i]] = i;
}
memset(input, false, V*sizeof(bool));
inc = 0;
for(i=V-1; i>=0; i--)
if(!input[request[i]]) {
high = request[i];
dfs(request[i]);
inc++;
}
printf("No. of strongly connected components : %d ", inc);
scanf("%d", &Q);
while(Q--) {
scanf("%d %d", &u, &v);
stronglyConnected(u, v) ? printf("YES ") : printf("NO ");
}
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.