1. Engineering
  2. Computer Science
  3. how do you the complete the method for reachable containcycles...

Question: how do you the complete the method for reachable containcycles...

Question details

How do you the complete the method for reachable(), contain_cycles(), depth_first(), breadth_first(), out_tree(), pre-order, in-order, post-order traversal() and significance_sorting()? My code is primarily on adjacency matrix and i am aiming on creating a weighted directed graph. I need the method structure inside each method to be filled. Thank you! Here's my header file:

#ifndef DIRECTED_GRAPH_H

#define DIRECTED_GRAPH_H

#include<iostream>

#include<string>

#include<vector>

#include<unordered_map>

#include<set>

#include<queue>

#include<stack>

 

using namespace std;

 

template <typename T>

class vertex {

public:

int id;

T weight;

vertex(int v_id, T v_weight) : id(v_id), weight(v_weight) {}

};

 

 

template <typename T>

class directed_graph {

 

private:

unordered_map<int, T> all_vertices;

unordered_map<int, unordered_map<int, T>> adj_list;

 

public:

directed_graph();

~directed_graph();

bool contains(const int&);

bool adjacent(const int&, const int&);

void add_vertex(const vertex<T>&); 

void add_edge(const int&, const int&, const T&);

void remove_vertex(const int&);

void remove_edge(const int&, const int&);

size_t in_degree(const int&);

size_t out_degree(const int&);

size_t degree(const int&);

size_t num_vertices() const;

size_t num_edges();

vector<vertex<T>> get_vertices();

vector<vertex<T>> get_neighbours(const int&);

vector<vertex<T>> get_second_order_neighbours(const int&);

bool reachable(const int&, const int&) const;

bool contain_cycles() const;

vector<vertex<T>> depth_first(const int&);

vector<vertex<T>> breadth_first(const int&);

directed_graph<T> out_tree(const int&);

vector<vertex<T>> pre_order_traversal(const int&, directed_graph<T>&);

vector<vertex<T>> in_order_traversal(const int&, directed_graph<T>&); 

vector<vertex<T>> post_order_traversal(const int&, directed_graph<T>&);

vector<vertex<T>> significance_sorting();

};

 

template <typename T>

directed_graph<T>::directed_graph() {

}

 

template <typename T>

directed_graph<T>::~directed_graph() {

}

 

template <typename T>

bool directed_graph<T>::contains(const int& v_id) {

if(all_vertices.find(v_id)!=all_vertices.end()){

return true;

}

return false;

}

 

template <typename T>

bool directed_graph<T>::adjacent(const int& u_id, const int& v_id) {

if(contains(u_id) && contains(v_id)){

if(adj_list[u_id].find(v_id)!=adj_list[u_id].end()){

return true;

}

}

return false;

}

 

template <typename T>

void directed_graph<T>::add_vertex(const vertex<T>& v) {

if(!contains(v.id)){

all_vertices.insert({v.id, v.weight});

adj_list[v.id]=unordered_map<int, T>();

}

}

 

 

template <typename T>

void directed_graph<T>::add_edge(const int& u_id, const int& v_id, const T& uv_weight) {

if(contains(u_id) && contains(v_id)){

if(adj_list[u_id].find(v_id)==adj_list[u_id].end()){

adj_list[u_id].insert({v_id, uv_weight});

}

}

}

 

template <typename T>

void directed_graph<T>::remove_vertex(const int& u_id) {

all_vertices.erase(u_id);

adj_list.erase(u_id);

for (auto& x: adj_list){

x.second.erase(u_id);

}

}

 

template <typename T>

void directed_graph<T>::remove_edge(const int& u_id, const int& v_id) {

if(adj_list[u_id].find(v_id)!=adj_list[u_id].end()){

adj_list[u_id].erase(v_id);

}

}

 

template <typename T>

size_t directed_graph<T>::in_degree(const int& u_id) {

int amount = 0;

if(contains(u_id)) {

for (int i = 0; i < adj_list.size(); i++){

if(adj_list[i].find(u_id)!=adj_list[i].end()){

amount += 1;

}   

}

}

return amount;

}

 

template <typename T>

size_t directed_graph<T>::out_degree(const int& u_id) {

int amount = 0;

if(contains(u_id)) {

for (int i = 0; i < adj_list.size(); i++){

if(adj_list[u_id].find(i)!=adj_list[u_id].end()){

amount += 1;

}   

}

}

return amount;

}

 

template <typename T>

size_t directed_graph<T>::degree(const int& u_id) {

int amount = 0;

amount = in_degree(u_id) + out_degree(u_id);

return amount;

}

 

template <typename T>

size_t directed_graph<T>::num_vertices() const {

return all_vertices.size();

}

 

template <typename T>

size_t directed_graph<T>::num_edges() {

int amount = 0;

for (int i = 0; i < adj_list.size(); i++){

for (auto x:adj_list[i]){

amount += 1;

}

}

return amount;

}

 

template <typename T>

vector<vertex<T>> directed_graph<T>::get_vertices() {

vector<vertex<T>> v;

for(auto x: all_vertices){

v.push_back(vertex<T>(x.first, x.second));

}

return v;

}

 

template <typename T>

vector<vertex<T>> directed_graph<T>::get_neighbours(const int& u_id) {

vector<vertex<T>> v;

if(contains(u_id)){

for (auto x: adj_list[u_id]){

v.push_back(vertex<T>(x.first, all_vertices[x.first]));

}

}

return v;

}

 

template <typename T>

vector<vertex<T>> directed_graph<T>::get_second_order_neighbours(const int& u_id) {

return vector<vertex<T>>();

}

 

template <typename T>

bool directed_graph<T>::reachable(const int& u_id, const int& v_id) const {

return false;

}

 

template <typename T>

bool directed_graph<T>::contain_cycles() const {

return false;

}

 

template <typename T>

vector<vertex<T>> directed_graph<T>::depth_first(const int& u_id) {

return vector<vertex<T>>();

}

 

template <typename T>

vector<vertex<T>> directed_graph<T>::breadth_first(const int& u_id) {

return vector<vertex<T>>();

}

 

template <typename T>

directed_graph<T> directed_graph<T>::out_tree(const int& u_id) {

return directed_graph<vertex<T>>();

}

 

template <typename T>

vector<vertex<T>> directed_graph<T>::pre_order_traversal(const int& u_id, directed_graph<T>& mst) {

return vector<vertex<T>>();

}

 

template <typename T>

vector<vertex<T>> directed_graph<T>::in_order_traversal(const int& u_id, directed_graph<T>& mst) {

return vector<vertex<T>>(); 

}

 

template <typename T>

vector<vertex<T>> directed_graph<T>::post_order_traversal(const int& u_id, directed_graph<T>& mst) {

return vector<vertex<T>>();

}

 

template <typename T>

vector<vertex<T>> directed_graph<T>::significance_sorting() {

return vector<vertex<T>>();

}

 

#endif

Solution by an expert tutor
Blurred Solution
This question has been solved
Subscribe to see this solution