C++ Programming Code Examples

/* C++ Program to Find the Maximum Size Clique in a Graph This is a C++ Program to find the cliques of size k in a a graph. An undirected graph is formed by a finite set of vertices and a set of unordered pairs of vertices, which are called edges. By convention, in algorithm analysis, the number of vertices in the graph is denoted by n and the number of edges is denoted by m. A clique in a graph G is a complete subgraph of G; that is, it is a subset S of the vertices such that every two vertices in S are connected by an edge in G. A maximal clique is a clique to which no more vertices can be added; a maximum clique is a clique that includes the largest possible number of vertices, and the clique number ?(G) is the number of vertices in a maximum clique of G. */ #include <iostream> #include <fstream> #include <string> #include <vector> using namespace std; bool removable(vector<int> neighbor, vector<int> cover); int max_removable(vector<vector<int> > neighbors, vector<int> cover); vector<int> procedure_1(vector<vector<int> > neighbors, vector<int> cover); vector<int> procedure_2(vector<vector<int> > neighbors, vector<int> cover, int k); int cover_size(vector<int> cover); ifstream infile("graph.txt"); ofstream outfile("cliques.txt"); int main() { //Read Graph (note we work with the complement of the input graph) cout << "Clique Algorithm." << endl; int n, i, j, k, K, p, q, r, s, min, edge, counter = 0; infile >> n; vector<vector<int> > graph; for (i = 0; i < n; i++) { vector<int> row; for (j = 0; j < n; j++) { infile >> edge; if (edge == 0) row.push_back(1); else row.push_back(0); } graph.push_back(row); } //Find Neighbors vector<vector<int> > neighbors; for (i = 0; i < graph.size(); i++) { vector<int> neighbor; for (j = 0; j < graph[i].size(); j++) if (graph[i][j] == 1) neighbor.push_back(j); neighbors.push_back(neighbor); } cout << "Graph has n = " << n << " vertices." << endl; //Read maximum size of Clique wanted cout << "Find a Clique of size at least k = "; cin >> K; k = n - K; //Find Cliques bool found = false; cout << "Finding Cliques..." << endl; min = n + 1; vector<vector<int> > covers; vector<int> allcover; for (i = 0; i < graph.size(); i++) allcover.push_back(1); for (i = 0; i < allcover.size(); i++) { if (found) break; counter++; cout << counter << ". "; outfile << counter << ". "; vector<int> cover = allcover; cover[i] = 0; cover = procedure_1(neighbors, cover); s = cover_size(cover); if (s < min) min = s; if (s <= k) { outfile << "Clique (" << n - s << "): "; for (j = 0; j < cover.size(); j++) if (cover[j] == 0) outfile << j + 1 << " "; outfile << endl; cout << "Clique Size: " << n - s << endl; covers.push_back(cover); found = true; break; } for (j = 0; j < n - k; j++) cover = procedure_2(neighbors, cover, j); s = cover_size(cover); if (s < min) min = s; outfile << "Clique (" << n - s << "): "; for (j = 0; j < cover.size(); j++) if (cover[j] == 0) outfile << j + 1 << " "; outfile << endl; cout << "Clique Size: " << n - s << endl; covers.push_back(cover); if (s <= k) { found = true; break; } } //Pairwise Intersections for (p = 0; p < covers.size(); p++) { if (found) break; for (q = p + 1; q < covers.size(); q++) { if (found) break; counter++; cout << counter << ". "; outfile << counter << ". "; vector<int> cover = allcover; for (r = 0; r < cover.size(); r++) if (covers[p][r] == 0 && covers[q][r] == 0) cover[r] = 0; cover = procedure_1(neighbors, cover); s = cover_size(cover); if (s < min) min = s; if (s <= k) { outfile << "Clique (" << n - s << "): "; for (j = 0; j < cover.size(); j++) if (cover[j] == 0) outfile << j + 1 << " "; outfile << endl; cout << "Clique Size: " << n - s << endl; found = true; break; } for (j = 0; j < k; j++) cover = procedure_2(neighbors, cover, j); s = cover_size(cover); if (s < min) min = s; outfile << "Clique (" << n - s << "): "; for (j = 0; j < cover.size(); j++) if (cover[j] == 0) outfile << j + 1 << " "; outfile << endl; cout << "Clique Size: " << n - s << endl; if (s <= k) { found = true; break; } } } if (found) cout << "Found Clique of size at least " << K << "." << endl; else cout << "Could not find Clique of size at least " << K << "." << endl << "Maximum Clique size found is " << n - min << "." << endl; cout << "See cliques.txt for results." << endl; return 0; } bool removable(vector<int> neighbor, vector<int> cover) { bool check = true; for (int i = 0; i < neighbor.size(); i++) if (cover[neighbor[i]] == 0) { check = false; break; } return check; } int max_removable(vector<vector<int> > neighbors, vector<int> cover) { int r = -1, max = -1; for (int i = 0; i < cover.size(); i++) { if (cover[i] == 1 && removable(neighbors[i], cover) == true) { vector<int> temp_cover = cover; temp_cover[i] = 0; int sum = 0; for (int j = 0; j < temp_cover.size(); j++) if (temp_cover[j] == 1 && removable(neighbors[j], temp_cover) == true) sum++; if (sum > max) { max = sum; r = i; } } } return r; } vector<int> procedure_1(vector<vector<int> > neighbors, vector<int> cover) { vector<int> temp_cover = cover; int r = 0; while (r != -1) { r = max_removable(neighbors, temp_cover); if (r != -1) temp_cover[r] = 0; } return temp_cover; } vector<int> procedure_2(vector<vector<int> > neighbors, vector<int> cover, int k) { int count = 0; vector<int> temp_cover = cover; int i = 0; for (int i = 0; i < temp_cover.size(); i++) { if (temp_cover[i] == 1) { int sum = 0, index; for (int j = 0; j < neighbors[i].size(); j++) if (temp_cover[neighbors[i][j]] == 0) { index = j; sum++; } if (sum == 1 && cover[neighbors[i][index]] == 0) { temp_cover[neighbors[i][index]] = 1; temp_cover[i] = 0; temp_cover = procedure_1(neighbors, temp_cover); count++; } if (count > k) break; } } return temp_cover; } int cover_size(vector<int> cover) { int count = 0; for (int i = 0; i < cover.size(); i++) if (cover[i] == 1) count++; return count; }

/* If Else Statement in C++ Language */ #include <iostream> using namespace std; int main () { // local variable declaration: int a = 100; // check the boolean condition if( a < 20 ) { // if condition is true then print the following cout << "a is less than 20;" << endl; } else { // if condition is false then print the following cout << "a is not less than 20;" << endl; } cout << "value of a is : " << a << endl; return 0; }

/* using #include directive in C language */ #include <stdio.h> int main() { /* * C standard library printf function * defined in the stdio.h header file */ printf("I love you Clementine"); printf("I love you so much"); printf("HappyCodings"); return 0; }

/* Vectors in C++ language */ // C++ program to illustrate the capacity function in vector #include <iostream> #include <vector> using namespace std; int main() { vector<int> myvector; for (int i = 1; i <= 5; i++) myvector.push_back(i); cout << "Size : " << myvector.size(); cout << "\nCapacity : " << myvector.capacity(); cout << "\nMax_Size : " << myvector.max_size(); // resizes the vector size to 4 myvector.resize(4); // prints the vector size after resize() cout << "\nSize : " << myvector.size(); // checks if the vector is empty or not if (myvector.empty() == false) cout << "\nVector is not empty"; else cout << "\nVector is empty"; // Shrinks the vector myvector.shrink_to_fit(); cout << "\nVector elements are: "; for (auto it = myvector.begin(); it != myvector.end(); it++) cout << *it << " "; return 0; }

/* For Loop Statement in C++ Language */ // C++ program to find the sum of first n natural numbers // positive integers such as 1,2,3,...n are known as natural numbers #include <iostream> using namespace std; int main() { int num, sum; sum = 0; cout << "Enter a positive integer: "; cin >> num; for (int i = 1; i <= num; ++i) { sum += i; } cout << "Sum = " << sum << endl; return 0; }

/* C++ files and streams */ /* writing to a file and reading from a file in C++ language */ #include <fstream> #include <iostream> using namespace std; int main () { char data[100]; // open a file in write mode. ofstream outfile; outfile.open("afile.dat"); cout << "Writing to the file" << endl; cout << "Enter your name: "; cin.getline(data, 100); // write inputted data into the file. outfile << data << endl; cout << "Enter your age: "; cin >> data; cin.ignore(); // again write inputted data into the file. outfile << data << endl; // close the opened file. outfile.close(); // open a file in read mode. ifstream infile; infile.open("afile.dat"); cout << "Reading from the file" << endl; infile >> data; // write the data at the screen. cout << data << endl; // again read the data from the file and display it. infile >> data; cout << data << endl; // close the opened file. infile.close(); return 0; }

/* While Loop Statement in C++ language */ // program to find the sum of positive numbers // if the user enters a negative number, the loop ends // the negative number entered is not added to the sum #include <iostream> using namespace std; int main() { int number; int sum = 0; // take input from the user cout << "Enter a number: "; cin >> number; while (number >= 0) { // add all positive numbers sum += number; // take input again if the number is positive cout << "Enter a number: "; cin >> number; } // display the sum cout << "\nThe sum is " << sum << endl; return 0; }

/* get the size of a vector, it returns the total number of elements in the vector by vector::size() library function. */ #include <bits/stdc++.h> using namespace std; int main() { // Initializing a vector of string type vector<string> vec = { "Happy", "8)", "Codings" }; // Clearing the vector // Now size is equal to 0 vec.clear(); // Typecasting vec.size() to int for (int i = 0; i < (int)vec.size() - 1; i++) cout << vec[i] << ' '; cout << "Happy8)Codings"; return 0; }

/* Standard Input Stream (cin) in C++ language */ // cin with Member Functions #include <iostream> using namespace std; int main() { char name[20], address[20]; cout << "Name: "; // use cin with getline() cin.getline(name, 20); cout << "Address: "; cin.getline(address, 20); cout << endl << "You entered " << endl; cout << "Name = " << name << endl; cout << "Address = " << address; return 0; }

/* vector::push_back() is a library function of "vector" header, it is used to insert/add an element at the end of the vector, it accepts an element of the same type and adds the given element at the end of the vector and increases the size of the vector. */ //C++ STL program code example to demonstrate example of vector::push_back() function #include <iostream> #include <vector> using namespace std; int main() { //vector declaration vector<int> v1; //inserting elements and printing size cout << "size of v1: " << v1.size() << endl; v1.push_back(10); cout << "size of v1: " << v1.size() << endl; v1.push_back(20); v1.push_back(30); v1.push_back(40); v1.push_back(50); cout << "size of v1: " << v1.size() << endl; //printing all elements cout << "elements of vector v1..." << endl; for (int x : v1) cout << x << " "; cout << endl; return 0; }

/* namespaces in C++ language */ // A C++ code to demonstrate that we can define // methods outside namespace. #include <iostream> using namespace std; // Creating a namespace namespace ns { void display(); class happy { public: void display(); }; } // Defining methods of namespace void ns::happy::display() { cout << "ns::happy::display()\n"; } void ns::display() { cout << "ns::display()\n"; } // Driver code int main() { ns::happy obj; ns::display(); obj.display(); return 0; }

/* Relational and equality operators (<, <=, >, >=, ==, !=) are defined to operate on scalars and produce scalar Boolean results. For vector results, use the following built-in functions. In all cases, the sizes of all the input and return vectors for any particular call must match. */ /* vector comparisons by vector relational operators code example */ #include <iostream> #include <vector> int main () { std::vector<int> foo (3,100); // three ints with a value of 100 std::vector<int> bar (2,200); // two ints with a value of 200 if (foo==bar) std::cout << "foo and bar are equal\n"; if (foo!=bar) std::cout << "foo and bar are not equal\n"; if (foo< bar) std::cout << "foo is less than bar\n"; if (foo> bar) std::cout << "foo is greater than bar\n"; if (foo<=bar) std::cout << "foo is less than or equal to bar\n"; if (foo>=bar) std::cout << "foo is greater than or equal to bar\n"; return 0; }

/* simple code example by main() function in C++ */ #include <iostream> using namespace std; int main() { int day = 4; switch (day) { case 1: cout << "Monday"; break; case 2: cout << "Tuesday"; break; case 3: cout << "Wednesday"; break; case 4: cout << "Thursday"; break; case 5: cout << "Friday"; break; case 6: cout << "Saturday"; break; case 7: cout << "Sunday"; break; } return 0; }

/* break statement with while loop code example */ // program to find the sum of positive numbers // if the user enters a negative numbers, break ends the loop // the negative number entered is not added to sum #include <iostream> using namespace std; int main() { int number; int sum = 0; while (true) { // take input from the user cout << "Enter a number: "; cin >> number; // break condition if (number < 0) { break; } // add all positive numbers sum += number; } // display the sum cout << "The sum is " << sum << endl; return 0; }

/* The operator ! is the C++ operator for the Boolean operation NOT. It has only one operand, to its right, and inverts it, producing false if its operand is true, and true if its operand is false. Basically, it returns the opposite Boolean value of evaluating its operand. The logical operators && and || are used when evaluating two expressions to obtain a single relational result. The operator && corresponds to the Boolean logical operation AND, which yields true if both its operands are true, and false otherwise. */ #include <iostream> using namespace std; main() { int a = 5; int b = 20; int c ; if(a && b) { cout << "Line 1 - Condition is true"<< endl ; } if(a || b) { cout << "Line 2 - Condition is true"<< endl ; } /* Let's change the values of a and b */ a = 0; b = 10; if(a && b) { cout << "Line 3 - Condition is true"<< endl ; } else { cout << "Line 4 - Condition is not true"<< endl ; } if(!(a && b)) { cout << "Line 5 - Condition is true"<< endl ; } return 0; }

/* write a C program which demonstrate use of if-else-if ladder statement */ /* Program to Print Day Names using Else If Ladder in C++*/ #include <iostream> using namespace std; int main() { int day; cout << "Enter Day Number: "; cin >> day; cout << "Day is "; if (day == 1) cout << "Sunday" << endl; else if (day == 2) cout << "Monday" << endl; else if (day == 3) cout << "Tuesday" << endl; else if (day == 4) cout << "Wednesday" << endl; else if (day == 5) cout << "Thursday" << endl; else if (day == 6) cout << "Friday" << endl; else cout << "Saturday" << endl; return 0; }

/* Returns a reference to the element at specified location pos. No bounds checking is performed. Unlike std::map::operator[], this operator never inserts a new element into the container. Accessing a nonexistent element through this operator is undefined behavior. */ /* Access element from a vector by vector::operator[] code example */ #include <iostream> #include <vector> int main () { std::vector<int> myvector (10); // 10 zero-initialized elements std::vector<int>::size_type sz = myvector.size(); // assign some values: for (unsigned i=0; i<sz; i++) myvector[i]=i; // reverse vector using operator[]: for (unsigned i=0; i<sz/2; i++) { int temp; temp = myvector[sz-1-i]; myvector[sz-1-i]=myvector[i]; myvector[i]=temp; } std::cout << "myvector contains:"; for (unsigned i=0; i<sz; i++) std::cout << ' ' << myvector[i]; std::cout << '\n'; return 0; }

/* nested loop statement in C++ language */ // C++ program that uses nested for loop to print a 2D matrix #include <bits/stdc++.h> using namespace std; #define ROW 3 #define COL 3 // Driver program int main() { int i, j; // Declare the matrix int matrix[ROW][COL] = { { 4, 8, 12 }, { 16, 20, 24 }, { 28, 32, 36 } }; cout << "Given matrix is \n"; // Print the matrix using nested loops for (i = 0; i < ROW; i++) { for (j = 0; j < COL; j++) cout << matrix[i][j]; cout << "\n"; } return 0; }