# Quiz 15: Graphs and Digraphs

Computing

Problem plan: • Include the required header files into the program. • Use "struct" for tree node • Allocate new tree to a node • Define a function "encoding ()" to encode the string. o check if the root node is null o check if the leaf node is found o call the function "encoding ()" to append 0 o call the function "encoding ()" to append 1 • Define a function "huff_tree ()" to generate huffman code o Use map tp count the frequency o store live nodes o create leaf node and push the elements o perform until more than 1 node in the tree o pointer is stored to the root of the Huffman o traverse and store the huffman codes o print the huffman codes • Define "main()" to demonstrate huffman technique o Declare variables o get input from user o call the function "huff_tree()" to generate huffman code Program: / ***********************************************************Run the code in c++ 11 compiler * *Program to construct Huffman code and the encode a * *message entered by the user * ********************************************************** / / / include header files #include #include #include #include using namespace std; / / struct for tree node struct Node { int f; char ch; Node *l, *r; }; / / allocation of new tree to a node Node* g_N(char ch, int f, Node* l, Node* r) { Node* node = new Node(); / / assign the node elements node- ch = ch; node- f = f; node- l = l; node- r = r; / / return after all the process has been done return node; } / / object for comparison struct comp { bool operator()(Node* l, Node* r) { / / the item with highest priority has lowest / / frequency return l- f r- f; } }; / / traverse and store in an huffman map void encoding(Node* root, string tx, map huffmanCode) { / / check if the root node is null if (root == NULL) return; / / if the leaf node is found if (!root- l !root- r) huffmanCode[root- ch] = tx; / / cal the function to append 0 encoding(root- l, tx + "0", huffmanCode); / / call the function to append 1 encoding(root- r, tx + "1", huffmanCode); } / / / build tree and decode void huff_tree(string inp) { / / to count the frequency map f; for (char ch : inp) f[ch]++; / / store live nodes priority_queue , comp pq; / / create leaf node and push the elements for (auto it : f) pq.push(g_N(it.first, it.second, NULL, NULL)); / / perform until more than 1 node in the tree while (pq.size() != 1) { / / remove nodes with highest priotity Node *l = pq.top(); pq.pop(); Node *r = pq.top(); pq.pop(); / / internal node is created and then a new node / / is added int sum = l- f + r- f; pq.push(g_N('\0', sum, l, r)); } / / pointer is stored to the root of the huffman tree Node* root = pq.top(); / / traverse and store the huffman codes map huffmanCode; encoding(root, "", huffmanCode); / / print the huffman codes cout "Huffman Code :\n" endl; for (auto it : huffmanCode) cout it.first " " it.second endl; / / actual string cout "\n actual string was :\n"; cout inp endl; / / print encoded string string tx = ""; for (char ch : inp) tx += huffmanCode[ch]; cout "\n encoded string is :\n" tx endl; } / / main function to perform huffman encoding int main() { / / variable declaration string inp; cout "enter the string you want to decode:"; / / get input from user cin inp; / / call the fuction to generate huffman code huff_tree(inp); return 0; } Sample Output: enter the string you want to decode:goodmorning Huffman Code : d 1100 g 00 i 1101 m 011 n 111 o 10 r 010 actual string was : goodmorning encoded string is : 001010110001110010111110111100

Problem plan: • Include the required header files into the program. • Declare the constant values • Declare "struct" for node • Define the class to compare the left and right side values o Use boolean function for operator o Return if left value is greater than right value • Type define for "priority queue" • Generate the "trie" code • Define a function "code()" to generate the code o Initialize the static string o Check if the right side of the node is not null o Fill the right substring with "1" o Again call the function o Fill until all the right sub tree values are full o Check if there is no string o Assign the values to the string • Define the function "cnt()" function to count values in the text file o Initilaise the required variables o Ifsteram to open the input file o Get the values from file one by one o Start counting the values o Use "while" loop to check if the input is text • If the count is greater or equal to "0" and less than size • Increment the count value o Close the input file • Define the function "bstrngstring()"to check the input file o Initialize the variable for input o Initialize a blank string o Get the input values for the file o Use while loop to check if the input is text. o Close the file • Define the "main()" function to demonstrate Huffman encoding o Initialize the required variables o Message for user to enter an option o Switch case to encode or decode o When user enters "a" • Request the user to enter the input file • Get the filename from the user • Print the input file name • Print the output filename • Open the output file and store the results • Print the results in the output file • Loop to print the left count value • Loop to push values using a temp variable o Call the function "code()"to go to the top of queue o Create a bit code string o Set the bit string value o Once the encoding is done find the compression ratio o Otherwise print stating that there is an error o When the user enters "b" • Request the user to enter the file name • Get input file from user • Open the input file • Obtain the input from the user one by one • Check for the magic number • Check for the match in the input file • For loop to read the letter count • Get the input from the user • Add the valid values to the priority queue o Create "trie" code o Create "bit" codes o Loop until input is not equal to "#" o Print to the output file the value of "j" o Assign the bit string value to be blank o Print when the input by user is not valid o Close the output file Program: / ***********************************************************Program to encode and decode a file using Huffman coding * ********************************************************** / / / include header files #include #include #include #include #include #include "bChar.h" / / declare the constant values const std::string m_num = "7771234777"; const int asze = 256; int l_Cnt[asze]; std::string st_cd[asze]; / / declare struct for node struct t_nd { char ch; int cnt; t_nd* l; t_nd* r; }; / / define the class to compare the left and right side / / values class cpre { public: / / boolean function for operator bool operator()(const t_nd* left_sde, const t_nd* right_sde) const { / / return if left value is greater than right / / value return left_sde- cnt right_sde- cnt; } }; / / make of the node t_nd* makeT_nd(char ch, int cnt) { / / temp value for node t_nd* tmp = new t_nd; / / assign the temp value to point to the character, / / count, left tmp- ch = ch; tmp- cnt = cnt; tmp- l = NULL; tmp- r = NULL; return tmp; }; / / typedef for priority queue typedef std::priority_queue , cpre p_q; / / to try fotr multiple values in the queue void tyr(p_q _h) { / / loop until the size is less than 1 while (_h.size() 1) { t_nd* holder = new t_nd; holder- l = _h.top(); _h.pop(); holder- r = _h.top(); _h.pop(); holder- cnt = holder- l- cnt + holder- r- cnt; holder- ch = -1; _h.push(holder); } } / / function to generate the code void code(t_nd* _h) { / / initialise the static swtring static std::string bstrng = ""; / / check if the right side of the node is not null if (_h- r != NULL) { / / fill the right substring with 1 bstrng += "1"; / / again call the function code(_h- r); / / fill until all the right sub stree values are / / filled with 1 bstrng = bstrng.substr(0, bstrng.size() - 1); } / / check if the left value is not null if (_h- l != NULL) { / / fill the right substring with 0 bstrng += "0"; / / again call the function for left node code(_h- l); / / fill until all the left sub stree values are / / filled with 0 bstrng = bstrng.substr(0, bstrng.size() - 1); } / / check if there is no string if (!_h- l !_h- r) { / / assign the values to the string st_cd[_h- ch] = bstrng; } } / / to count the values in the text file void cnt(std::string txt_fl, int _h) { / / initilaise the required variables char wrd; / / ifstram to open the input file std::ifstream inf(txt_fl.c_str()); / / get the values from file one by one inf std::noskipws; / / start counting the values for (int i = 0;i asze; ++i) l_Cnt[i] = 0; / / use while loop to check if the input is text while (inf wrd) { / / if the count is greater or equal to 0 and less / / than size if (wrd = 0 wrd asze) { / / increment the count value ++l_Cnt[wrd]; ++_h; } } / / close the file inf.close(); } / / function to check the input file std::string bstrngstring(std::string i_F) { / / initialise the variable for input char input; / / initialise a blank string std::string bstrng = ""; std::ifstream inf(i_F.c_str()); / / get the input values fro the file inf std::noskipws; / / use while loop to check if the input is text while (inf input) { bstrng += st_cd[input]; } / / close the file inf.close(); bstrng += st_cd; return bstrng; } / / Function main int main(int argc, char** argv) { / / initialize the required variables int r_c; char ch; unsigned char ch_in; std::string i_F = "", o_Txt_fl = "", bstrng = "", bstrngsub = "", mn = ""; std::ofstream o_F; std::ifstream inf; p_q pq; bChar bchar; int o_sze = 0; / / message for user to enter an option std::cout "select (a / b)\n" std::endl "a. to encode a file" std::endl "b. to decode a file" std::endl; std::cin ch; / / switch case to encode or decode switch (ch) { / / when user enters 'a' case 'a': / / request the user to enter the input file std::cout "please enter file to be encoded: " std::endl; / / get the filename from the user std::cin i_F; / / the output file o o_Txt_fl = i_F + ".txt"; / / print the input file name std::cout std::left std::setw(17); std::cout "Input file: " i_F std::endl; / / print the output filename std::cout std::left std::setw(17); std::cout "Output file:" o_Txt_fl std::endl; std::cout std::endl; / / open the output file and store the results o_F.open(o_Txt_fl.c_str()); cnt(i_F, o_sze); if (l_Cnt == 0) l_Cnt = 1; / / print the results in the output file o_F m_num std::endl; o_F i_F std::endl; / / loop to print the left count value for (int i = 0; i asze; ++i) { o_F l_Cnt[i] " "; } o_F std::endl; / / loop to push values using a temp variable for (int i = 0; i asze; ++i) { if (l_Cnt[i] 0) { / / call the function "makeT_nd" t_nd* tmp = makeT_nd(i, l_Cnt[i]); pq.push(tmp); } } / / call the functiiion to go to the top of queue tyr(pq); code(pq.top()); / / to create a bit code string bstrng = bstrngstring(i_F); o_F '#'; / / set the bit string value bchar.setbstrng(bstrng); o_F std::noskipws; r_c = bchar.i_R(o_F); / / once the encoding is done if (r_c == bstrng.length()) { std::cout "Encoding is done successfully! :)" std::endl; / / find the compression ratio std::cout "The ration of compression: " (float)r_c / ((float)o_sze * 8.0) * 100.0 "%" std::endl; } else { / / otherwise print stating that there is an / / error std::cout "there is an error :(" std::endl; std::cout "Expected: " bstrng.length() * 8 " but got: " r_c std::endl; } break; / / when the user enters b case 'b': / / request the user to enter the file name std::cout "Please enter the file to be decoded: " std::endl; / / get input file from user std::cin i_F; / / open the input file inf.open(i_F.c_str()); / / obtain the input form the user one by one inf mn; / / check for the magic number if (mn != m_num) { std::cout "the numbers does not match" std::endl; return 1; } inf o_Txt_fl; / / check for the match in the input file if (o_Txt_fl != i_F.substr(0, i_F.length() - 4)) { std::cout o_Txt_fl " " std::cout "no match found but the decoding can be performed" std::endl; } o_F.open(o_Txt_fl.c_str()); / / for loop to read the letter count for (int i = 0; i asze; ++i) { / / get the input from the user inf l_Cnt[i]; if (l_Cnt[i] 0) { / / add the valid values to the the / / priority queue t_nd* tmp = makeT_nd(i, l_Cnt[i]); pq.push(tmp); } } / / to create trie code tyr(pq); / / to create bit codes code(pq.top()); / / loop until input is not equal to "#" while (ch_in != '#') { inf ch_in; } inf std::noskipws; while (inf ch_in) { bstrng += bchar.g_B(ch_in); } / / close the input dile inf.close(); for (int i = 0; i bstrng.length(); ++i) { / / increment the value of bit string variable bstrngsub += bstrng[i]; for (int j = 0; j asze; ++j) { / / check if the bit string is equal to / / string code if (bstrngsub == st_cd[j]) { / / if it is an end of file if (j == 3) { / / go to the newline o_F "\n"; i = bstrng.length(); / / then exit break; } / / print to the output file the / / value of j o_F (char)j; / / assign the bit string value to / / be blank bstrngsub = ""; break; } } } break; default: / / print when the input by user is not valid std::cout "your choice is invalid" std::endl; break; } / / close the output file o_F.close(); return 0; } bChar.h: / / include header files #include #include #include #include / / class definition for bChar class bChar { public: / / declare the variables in public unsigned char* c; int shift_cnt; std::string bstrng; / / function call for bchar() bChar(); void setbstrng(std::string _h); int i_R(std::ofstream outf); std::string g_B(unsigned char _h); void w_R(std::ofstream outf); ~bChar(); }; / / include the required files #include "bChar.h" / / include the ffunction from the header "bChar.h" bChar::bChar() { shift_cnt = 0; c = (unsigned char*)calloc(1, sizeof(char)); } / / this function will return how many bits are been inserted void bChar::setbstrng(std::string _h) { bstrng = _h; } int bChar::i_R(std::ofstream outf) { int tot = 0; / / check the length of the bit string while (bstrng.length()) { if (bstrng == '1') *c |= 1; *c = 1; ++shift_cnt; ++tot; bstrng.erase(0, 1); / / check if the shift count is 7 if (shift_cnt == 7) { / / write the results to the output file w_R(outf); shift_cnt = 0; free(c); c = (unsigned char*)calloc(1, sizeof(char)); } } / / check for trailing bits if (shift_cnt 0) { / / if there is a trailing bit then push it *c = (8 - shift_cnt); w_R(outf); free(c); c = (unsigned char*)calloc(1, sizeof(char)); } return tot; } / / the output is given in binary format std::string bChar::g_B(unsigned char _h) { std::stringstream _itoa; int _size = sizeof(unsigned char) * 8; for (unsigned _s = 0; _s _size - 1; ++_s) { _itoa ((_h (_size - 1 - _s)) 1); } return _itoa.str(); } / / function to write the bits void bChar::w_R(std::ofstream outf) { outf *c; } / / destructor for the method "bChar()" bChar::~bChar() { if (c) free(c); } Sample Input file: Maria is studying to become an immigration lawyer. At her university alone there are more than a thousand undocumented students; so many, they have established a support centre. Cities like Los Angeles have vowed to fight to defend immigrant communities from Mr Trump's policies Sample Output: select (a / b) a. to encode a file b. to decode a file a please enter file to be encoded: f1.txt Input file: f1.txt Output file: f1.txt.txt Encoding is done successfully! :) The ration of compression: 55.3191% f1.txt.mpc : 7771234777 f1.txt 0 0 0 1 0 0 0 0 0 0 3 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 41 0 0 0 0 0 0 1 0 0 0 0 1 0 2 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 2 0 1 0 0 0 0 0 0 0 0 1 2 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 16 2 5 9 29 3 5 9 19 0 1 6 12 16 16 4 0 14 16 21 9 4 2 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Problem plan: • Include the required header files into the program. • Declare the AVL node class template • Now define the template class for AVL node o Initialize the required variables o Assign values to all the node variables o Delete the nodes • Define the class template for AVL tree node. o Declare the required functions o Initialize the root node o Declare the function to rotate right o Declare the function to rotate left o Declare the function to rotate left then right o Declare the function to rotate right then left o Declare the other functions to re-balance a tree, find height, set balance, print balance and clear nodes • Define the functions • Define the "main()" function to demonstrate the AVL tree class template o Create an object for AVL tree class o Start inserting the values into the tree o Call the function "prnt_bal()" to print the results Program: / ***********************************************************Program to test AVL Tree class template * ********************************************************** / / / include the required header files #include #include using namespace std; / / AVL node class template template / / class definition class AVL_node { public: / / initialise the required variables T key; int balance; AVL_node *l, *r, *parent; / / assign values to all the node variables AVL_node(T k, AVL_node *p) : key(k), balance(0), parent(p), l(NULL), r(NULL) {} / / delete the nodes ~AVL_node() { delete l; delete r; } }; / / template for AVLTree class template / / class definition class AVLtree { public: / / declare the required functions AVLtree(void); ~AVLtree(void); / / to insert the values into the tree bool insert(T key); / / to delete the constant value k void del_K(const T key); / / to print the balance void prnt_bal(); private: / / initialize the root node AVL_node *root; / / initilaise to rotate left AVL_node * LL(AVL_node *a); / / initilaise to rotate right AVL_node * RR(AVL_node *a); / / initilaise to rotate left then right AVL_node * LR(AVL_node *n); / / initialize to rotate right then left AVL_node * RL(AVL_node *n); / / to re_bal the tree void re_bal(AVL_node *n); / / to find the ht of the tree int ht(AVL_node *n); / / to set the balance of the tree void st_bal(AVL_node *n); / / to print the balance of the tree void prnt_bal(AVL_node *n); / / to clear the nodes void clr_n(AVL_node *n); }; / / AVL tree class definition template / / function definition for rebalancing the nodes void AVLtree ::re_bal(AVL_node *n) { st_bal(n); / / if the balance is -2 if (n- balance == -2) { / / if the height of left is greater than height of / / right if (ht(n- l- l) = ht(n- l- r)) / / then perform RR rotation n = RR(n); else / / otherwise perform LR rotation n = LR(n); } / / if the balance is 2 else if (n- balance == 2) { / / if the height of the right tree is greater than / / height of left right if (ht(n- r- r) = ht(n- r- l)) / / perform LL rotation n = LL(n); else / / perform RL rotation n = RL(n); } / / if the parent node is null if (n- parent != NULL) { / / perform rebalancing the tree re_bal(n- parent); } else { / / assign the root to n root = n; } } / / template function for LL rotation template / / perform LL rotation AVL_node * AVLtree ::LL(AVL_node *a) { / / assign right of a to b AVL_node *b = a- r; / / a is assigned to parent of b b- parent = a- parent; / / left of b is assigned to right of b a- r = b- l; / / check if the right of a is not equal to null if (a- r != NULL) a- r- parent = a; / / a is assigned to left of b b- l = a; / / b is assigned to parent of b a- parent = b; / / if the parent of b is not NULL if (b- parent != NULL) { if (b- parent- r == a) { b- parent- r = b; } else { b- parent- l = b; } } / / set balance of a st_bal(a); / / set balance of b st_bal(b); return b; } template / / template function for RR rotation AVL_node * AVLtree ::RR(AVL_node *a) { AVL_node *b = a- l; / / parent of a is assigned to parent of b b- parent = a- parent; / / right of b is assigned to left of a a- l = b- r; / / check if left of a is NULL if (a- l != NULL) a- l- parent = a; / / a is assigned to right of b b- r = a; / / b is assigned to parent of a a- parent = b; / / check if parent of b is NULL if (b- parent != NULL) { if (b- parent- r == a) { b- parent- r = b; } else { b- parent- l = b; } } / / set balance of a st_bal(a); / / set balance of b st_bal(b); return b; } / / template LR rotation template / / perform LR rotation AVL_node * AVLtree ::LR(AVL_node *n) { n- l = LL(n- l); return RR(n); } / / template function for RL rotation template AVL_node * AVLtree ::RL(AVL_node *n) { n- r = RR(n- r); return LL(n); } template / / find the height of the tree int AVLtree ::ht(AVL_node *n) { if (n == NULL) return -1; return 1 + max(ht(n- l), ht(n- r)); } / / set the balance of the tree template void AVLtree ::st_bal(AVL_node *n) { n- balance = ht(n- r) - ht(n- l); } / / print the balance node template / / define the function to print the tree void AVLtree ::prnt_bal(AVL_node *n) { / / check if n is not NULL if (n != NULL) { / / cal the function to print the left tree prnt_bal(n- l); cout n- balance "\n"; / / call the function to print the right tree prnt_bal(n- r); } } template / / check if the AVL tree is NULL AVLtree ::AVLtree(void) : root(NULL) {} / / check if the AVL tree is void then delete the root node template AVLtree ::~AVLtree(void) { / / delete the root value delete root; } / / template class to insert element into the tree template / / define the function insert the node bool AVLtree ::insert(T key) { / / check if the root value is NULL if (root == NULL) { root = new AVL_node (key, NULL); } else { AVL_node *n = root, *parent; / / use while loop to insert the element into the / / tree while (true) { / / check if the n of key equals to key if (n- key == key) return false; / / n is assigned to the parrent parent = n; bool g_L = n- key key; / / if the control goes to left then n is / / right otherwise left n = g_L ? n- l : n- r; / / check if the n value is null if (n == NULL) { if (g_L) { / / left of the parent is set to new / / AVL node parent- l = new AVL_node (key, parent); } else { / / right of the parent node is set / / to new AVL node parent- r = new AVL_node (key, parent); } / / rebalance the parent node re_bal(parent); break; } } } return true; } / / template class for deletion template / / function to delete the values void AVLtree ::del_K(const T d_k) { if (root == NULL) return; / / assign nodes with the respective values AVL_node *n = root, *parent = root, *d_N = NULL, *child = root; / / use while loop to check the nodes one by one whether / / it is balanced and then delete the nodes while (child != NULL) { / / if the value is not null the assign n to parent / / node parent = n; / / assign child to n n = child; child = d_k = n- key ? n- r : n- l; / / check if the key to be deleted is equal the / / node if (d_k == n- key) d_N = n; } / / if the delete key value is not null if (d_N != NULL) { / / then the key is assigned to delete node d_N- key = n- key; / / now the left node is assigned to the child child = n- l != NULL ? n- l : n- r; / / if the root is assigned to the delete key node if (root- key == d_k) { / / childe is assigned to the root node root = child; } else { / / if the left of parent is n if (parent- l == n) { / / then assign the child to left parent- l = child; } else { / / otherwise assign right to the child parent- r = child; } / / call the function to rebalance the nodes / / again re_bal(parent); } } } / / template class to print the balance template void AVLtree ::prnt_bal() { prnt_bal(root); cout endl; } / / main function to demonstarte AVLTree class int main(void) { / / create an object for AVL tree class AVLtree t; / / start inserting the values into the tree cout "Inserting values into the tree one by one....." endl; / / insert values into the tree t.insert(11); t.insert(33); t.insert(22); t.insert(55); t.insert(44); t.insert(99); t.insert(77); t.insert(88); t.insert(66); / / print the values cout "Print the balance factor: "; / / call the function to print the results t.prnt_bal(); } Sample Output: Inserting values into the tree one by one..... Print the balance factor: 0 0 0 1 1 0 0 0 -1