Programmer's Wiki
Advertisement

C++ Mathematics Code Examples[]

Calculator - A division, multiplication, adding, subtracting program.[]

Calculator - A division, multiplication, adding, subtracting program.

#include<iostream>
#include<string>
using namespace std;
float mult(float num1,float num2);
float add(float num1,float num2);
float sub(float num1,float num2);
float divide(float num2,float num2);
int main()
{
    int choice;
    float num1,num2;


    cout<<" CALCULATOR "<<endl;


    cout<<"    Make a selction:"<<endl;
    cout<<"    1.Division"<<endl;
    cout<<"    2.Adding"<<endl;
    cout<<"    3.Subtraction"<<endl;
    cout<<"    4.multiplication"<<endl;
    cout<<"
YOUR CHIOCE IS: ";
    cin>>choice;
    switch(choice){
                   case 1:
                        cout<<"Please enter the two numbers you want to
divide, divisor first!: ";
                        cin>>num1>> num2;
                        cin.ignore();

cout<<"
"<<num1<<"/"<<num2<<"="<<divide(num1,num2)<<endl;
                        break;
                              case 2:
                                   cout<<"Please enter the two numbers 
you
want to add: ";
                                   cin>>num1>> num2;
                                   cin.ignore();

cout<<"
"<<num1<<"+"<<num2<<"="<<add(num1,num2)<<endl;
                                    break;
                                           case 3:
                                                 cout<<"Please enter 
the
two numbers you want to subtract, The number you want to subtract from
first!: ";
                                                 cin>>num1>> num2;
                                                 cin.ignore();

cout<<"
"<<num1<<"-"<<num2<<"="<<sub(num1,num2)<<endl;
                                                 break;
                                                       case 4:
                                                             
cout<<"Please
enter the two numbers you want to multiply: ";
                                                             
cin>>num1>>
num2;
                                                             
cin.ignore();

cout<<"
"<<num1<<"*"<<num2<<"="<<mult(num1,num2)<<endl;
                                                              break;

default:

cout<<"Invalid Entry!, BYE!!!"<<endl;

cin.ignore();

break;
                                                                          
        }
                                cin.ignore();
                                return 0;
}
float mult(float num1,float num2){
    return (num1*num2);
}
float add(float num1,float num2){
    return (num1+num2);
}
float sub(float num1,float num2){
    return (num1-num2);
}
float divide(float num1,float num2){
    return (num1/num2);
}

C++ Program to Calculate Power of a Number[]

C++ Program to Calculate Power of a Number

In this article, you will learn to compute power to a number manually, and by using pow() function.

This program takes two numbers from the user (a base number and an exponent) and calculates the power.

Power of a number = base^exponent

The above technique works only if the exponent is a positive integer.

If you need to find the power of a number with any real number as an exponent, you can use pow() function.

#include <iostream>
using namespace std;

int main() 
{
    int exponent;
    float base, result = 1;

    cout << "Enter base and exponent respectively:  ";
    cin >> base >> exponent;

    cout << base << "^" << exponent << " = ";

    while (exponent != 0) {
        result *= base;
        --exponent;
    }

    cout << result;
    
    return 0;
}

Program to Implement Miller Rabin Primality Test[]

Program to Implement Miller Rabin Primality Test

This C++ Program demonstrates the implementation of Miller Rabin Primality Test.

    #include <iostream>

    #include <cstring>

    #include <cstdlib>

    #define ll long long

    using namespace std;

    /* calculates (a * b) % c taking into account that a * b might overflow      */

    ll mulmod(ll a, ll b, ll mod)

    {

        ll x = 0,y = a % mod;

        while (b > 0)

        {

            if (b % 2 == 1)

            {    

                x = (x + y) % mod;

            }

            y = (y * 2) % mod;

            b /= 2;

        }

        return x % mod;

    }

    /* modular exponentiation     */

    ll modulo(ll base, ll exponent, ll mod)

    {

        ll x = 1;

        ll y = base;

        while (exponent > 0)

        {

            if (exponent % 2 == 1)

                x = (x * y) % mod;

            y = (y * y) % mod;

            exponent = exponent / 2;

        }

        return x % mod;

    }

    /* Miller-Rabin primality test, iteration signifies the accuracy     */

    bool Miller(ll p,int iteration)

    {

        if (p < 2)

        {

            return false;

        }

        if (p != 2 && p % 2==0)

        {

            return false;

        }

        ll s = p - 1;

        while (s % 2 == 0)

        {

            s /= 2;

        }

        for (int i = 0; i < iteration; i++)

        {

            ll a = rand() % (p - 1) + 1, temp = s;

            ll mod = modulo(a, temp, p);

            while (temp != p - 1 && mod != 1 && mod != p - 1)

            {

                mod = mulmod(mod, mod, p);

                temp *= 2;

            }

            if (mod != p - 1 && temp % 2 == 0)

            {

                return false;

            }

        }

        return true;

    }

    //Main

    int main()

    {

        int iteration = 5;

        ll num;

        cout<<"Enter integer to test primality: ";

        cin>>num;

        if (Miller(num, iteration))

            cout<<num<<" is prime"<<endl;

        else

            cout<<num<<" is not prime"<<endl;

        return 0;

    }

C++ Program to Multiply two Numbers[]

C++ Program to Multiply two Numbers

In this program, user is asked to enter two numbers (floating point numbers). Then, the product of those two numbers is stored in a variable and displayed on the screen.

In this program, user is asked to enter two numbers. These two numbers entered by the user is stored in variable firstNumber and secondNumber respectively.

Then, the product of firstNumber and secondNumber is evaluated and the result is stored in variable productOfTwoNumbers.

Finally, the productOfTwoNumbers is displayed on the screen.

#include <iostream>
using namespace std;

int main()
{
    double firstNumber, secondNumber, productOfTwoNumbers;
    cout << "Enter two numbers: ";

    // Stores two floating point numbers in variable firstNumber and secondNumber respectively
    cin >> firstNumber >> secondNumber;
 
    // Performs multiplication and stores the result in variable productOfTwoNumbers
    productOfTwoNumbers = firstNumber * secondNumber;  

    cout << "Product = " << productOfTwoNumbers;    
    
    return 0;
}

Fibonacci series Program[]

Fibonacci series Program

In mathematics, the Fibonacci numbers or Fibonacci series or Fibonacci sequence are the numbers in the following integer sequence:

1  1  2  3  5  8  13  21  34  55  89  144 ......

By definition, the first two numbers in the Fibonacci sequence are 0 and 1, and each subsequent number is the sum of the previous two.

#include<iostream>
#include<conio.h>

using namespace std;

int main() {

    // Variable Declaration
    int counter, n;
    long last = 1, next = 0, sum;
    // Get Input Value
    cout << "Enter the Number :";
    cin>>n;

    //Fibonacci Series Calculation
    while (next < n / 2) {
        cout << last << "  ";
        sum = next + last;
        next = last;
        last = sum;
    }

    // Wait For Output Screen
    getch();
    return 0;
}

next Prime number Print next Prime number[]

Print next Prime number

When we enter any number this code will print next Prime number.

Example: Suppose we enter 5 then next prime number is 7.

#include<iostream.h>
#include<conio.h>

void main()
{
  int i,j=2,num;
  clrscr();
  cout<<"Enter any num: ";
  cin>>num;
  cout<<"Next prime num: ";
  for(i=num+1;i<3000;i++)
   {
    for(j=2;j<i;j++)
      {
     if(i %j==0)
     {
     break;
      } // if
     } // for
     if(i==j || i==1)
       {
       cout<<"\t"<<i;
    break;
    } // if
    }  // outer for
getch();
}

Program to implement Polygon Filling Algorithm[]

Program to implement Polygon Filling Algorithm

#include<stdio.h>
#include<conio.h>
#include<iostream.h>
#include<graphics.h>
#include<dos.h>
#include<stdlib.h>

int gd=DETECT,gm;

class myStack
    {
        private:
    int arr[10000][2],top;
    public:
    myStack()
        {
        top=-1;
        }
    void push(int x,int y)
        {
        if(top>10000)
            {
            printf("
a    " Stack Full...:-("");
            exit(0);
            }
        top++;
        arr[top][0]=x;
        arr[top][1]=y;
        }

    void pop(int &x,int &y)
        {
        x=arr[top][0];
        y=arr[top][1];
        top--;
        }

    int empty(void)
        {
        if(top==-1)
        return(1);
        else return(0);
        }
    };

void show_quadrant()
    {
    cleardevice();
    rectangle(120,40,320,240);
    rectangle(320,40,520,240);
    rectangle(120,240,320,440);
    rectangle(320,240,520,440);
    for(int i=130;i<=510;i+=10)
        {
        if(i==320)
        continue;
        outtextxy(i,237,"+");
        }
    for(i=50;i<=430;i+=10)
        {
        if(i==240)
        continue;
        outtextxy(317,i,"-");
        }
    outtextxy(310,230,"O");
    outtextxy(530,240,"X");
    outtextxy(320,450,"-Y");
    outtextxy(100,240,"-X");
    outtextxy(320,30,"Y");
    }


int get_poly(int ed[20])
    {
    int edg,i,j;
    clearviewport();
        closegraph();
    cout<<"
    " Enter No. Of Edges ":=";
    cin>>edg;
    for(i=0,j=1;i<2*edg;i+=2,j++)
        {
        cout<<"
        " Enter Vertex No. "<<j<<" ":= ";
        flushall();
        cin>>ed[i]>>ed[i+1];
        ed[i]+=320;
        ed[i+1]=240-ed[i+1];
        }
    ed[i]=ed[0];
    ed[i+1]=ed[1];
    initgraph(&gd,&gm,"..\bgi");
    clearviewport();
    show_quadrant();
    drawpoly(edg+1,ed);
    return(edg);
    }

void get_y(int &min,int &max,int edge[20],int size)
    {
    int i;
    min=480;
    max=0;
    for(i=1;i<2*size;i+=2)
        {
        if(edge[i]>max)
        max=edge[i];
        if(edge[i]<min)
        min=edge[i];
        }
    }

void get_x(int &min,int &max,int edge[20],int size)
    {
    int i;
    min=480;
    max=0;
    for(i=0;i<2*size;i+=2)
        {
        if(edge[i]>max)
        max=edge[i];
        if(edge[i]<min)
        min=edge[i];
        }
    }

void fill_polygon(int x,int y,int fg,int bg)
    {
    myStack stack;
    int col;
    putpixel(x,y,fg);
    stack.push(x,y);
    while(!stack.empty())
        {
        stack.pop(x,y);
        col=getpixel(x,y);
        if(col!=bg&&col!=fg)
        putpixel(x,y,fg);
        col=getpixel(x,y+1);
        if(col!=bg&&col!=fg)
        stack.push(x,y+1);
        col=getpixel(x+1,y);
        if(col!=bg&&col!=fg)
        stack.push(x+1,y);
        col=getpixel(x-1,y);
        if(col!=bg&&col!=fg)
        stack.push(x-1,y);
        col=getpixel(x,y-1);
        if(col!=bg&&col!=fg)
        stack.push(x,y-1);
        }
    }


void flood_fill(int ed[20])
    {
    int i,j,x,y,num,bg,fg,col,k;
    clearviewport();
        closegraph();
    cout<<"
    " Enter No Of Edges ":= ";
    cin>>num;
    for(i=0,k=1;i<2*num;i+=2,k++)
        {
        cout<<"
    " Enter The Vertex No "<<k<<" ":=";
        flushall();
        cin>>ed[i]>>ed[i+1];
        ed[i]+=320;
        ed[i+1]=240-ed[i+1];
        }
    ed[i]=ed[0];
    ed[i+1]=ed[1];
    cout<<"
    " Enter The Seed Point (x,y) ":= ";
    cin>>x>>y;
    x+=320;
    y=240-y;
        initgraph(&gd,&gm,"..\bgi");
        cleardevice();
    show_quadrant();
    setcolor(1);
    drawpoly(num+1,ed);
    fill_polygon(x,y,15,1);
    }

int check_mid(int i,int ed[20],int k)
    {
    int max,min;
    if(ed[k+1]>ed[k+3])
        {
        max=ed[k+1];
        min=ed[k+3];
        }
    if(ed[k+1]<ed[k+3])
        {
        max=ed[k+3];
        min=ed[k+1];
        }
    if(i>min&&i<max)
    return(1);
    else
    return(0);
    }

void scan_poly(int ed[20],int num)
    {
    int i,j,k,xmax,xmin,ymax,ymin,p;
    void sort(float xi[10],int n);
    float xi[10];
    get_y(ymin,ymax,ed,num);
    get_x(xmin,xmax,ed,num);
    for(i=ymin;i<=ymax;i++)
        {
        p=0;
        for(k=0;k<2*num;k+=2)
            {
            if(ed[k+1]==ed[k+3])
            continue;
xi[p] = ed[k]+((double)((double)(i-ed[k+1])/(ed[k+1]-ed[k+3]))*(ed[k]-ed[k+2]));
            if(xi[p]>=xmin&&xi[p]<=xmax)
            p++;
            }
        sort(xi,p);
        for(j=0;j<p;j+=2)
        line(xi[j],i,xi[j+1],i);
        }
    }

void sort(float xi[10],int n)
    {
    int i,j;
    for(i=0;i<n-1;i++)
        {
        for(j=0;j<n-1;j++)
            {
            if(xi[j]>xi[j+1])
                {
                float temp;
                temp=xi[j];
                xi[j]=xi[j+1];
                xi[j+1]=temp;
                }
            }
           }
    }

void edge_fill(int ed[20],int num)
    {
    int i,j,k,xmax,xmin,ymax,ymin,col;
    double xint;
    get_y(ymin,ymax,ed,num);
    get_x(xmin,xmax,ed,num);
    for(k=0;k<2*num;k+=2)
        {
        for(i=ymin;i<=ymax;i++)
            {
            if(ed[k+1]==ed[k+3])
            continue;
            if(!check_mid(i,ed,k))
            continue;
xint = ed[k]+(((double)(i-ed[k+1])/(ed[k+1]-ed[k+3]))*(ed[k]-ed[k+2]));
            for(j=xmin;j<=xmax;j++)
                {
                if(j>xint)
                    {
                    col=getpixel(j,i);
                    if(col==15)
                    putpixel(j,i,0);
                    if(col==0)
                    putpixel(j,i,15);
                    }
                }
            }
        }
    }

void main()
    {
    clrscr();
    char *mess[]={"-","=","["," ","P","o","l","y","g","o","n"," ",
              "F","i","l","l","i","n","g"," ","]","=","-",};
    int xx=28,xxx=51,i,j;
    _setcursortype(_NOCURSOR);
    for(i=0,j=22;i<13,j>=11;i++,j--)
        {
        gotoxy(xx,1);
        cout<<mess[i];
        xx++;
        gotoxy(xxx,1);
        cout<<mess[j];
        xxx--;
        delay(50);
        }
    xx=30;xxx=49;
        int choice,ed[20],num;
    _setcursortype(_NORMALCURSOR);
    cout<<"


        1:==>" Flood Fill "";
    cout<<"

        2:==>" Ordered Edge List Fill "";
    cout<<"

        3:==>" Edge Fill "";
    cout<<"

        4:==>" Exit "";
    cout<<"

        " Enter Your Choice ":=";
    cin>>choice;
    initgraph(&gd,&gm,"..\bgi");
    clearviewport();
    switch(choice)
        {
        case 1:
            flood_fill(ed);
            getch();
            break;

        case 2:
            num=get_poly(ed);
            scan_poly(ed,num);
            getch();
            break;

        case 3:
            num=get_poly(ed);
            edge_fill(ed,num);
            getch();
            break;

        case 4:
            exit(0);

                default:
                    cout<<"
    a" Press A Valid Key...!!! "";
                        getch();
                        main();
                        break;
        }
    closegraph();
    }

Program to Check Whether a Directed Graph Contains a Eulerian Path[]

Program to Check Whether a Directed Graph Contains a Eulerian Path

This is a C++ Program to check whether graph contains Eulerian Path. The criteran Euler suggested,

1. If graph has no odd degree vertex, there is at least one Eulerian Circuit.

2. If graph as two vertices with odd degree, there is no Eulerian Circuit but at least one Eulerian Path.

3. If graph has more than two vertices with odd degree, there is no Eulerian Circuit or Eulerian Path.

    // A C++ program to check if a given graph is Eulerian or not

    #include<iostream>

    #include <list>

    using namespace std;

    // A class that represents an undirected graph

    class Graph

    {

            int V; // No. of vertices

            list<int> *adj; // A dynamic array of adjacency lists

        public:

            // Constructor and destructor

            Graph(int V)

            {

                this->V = V;

                adj = new list<int> [V];

            }

            ~Graph()

            {

                delete[] adj;

            } // To avoid memory leak

            // function to add an edge to graph

            void addEdge(int v, int w);

            // Method to check if this graph is Eulerian or not

            int isEulerian();

            // Method to check if all non-zero degree vertices are connected

            bool isConnected();

            // Function to do DFS starting from v. Used in isConnected();

            void DFSUtil(int v, bool visited[]);

    };

    void Graph::addEdge(int v, int w)

    {

        adj[v].push_back(w);

    }

    void Graph::DFSUtil(int v, bool visited[])

    {

        // Mark the current node as visited and print it

        visited[v] = true;

        // Recur for all the vertices adjacent to this vertex

        list<int>::iterator i;

        for (i = adj[v].begin(); i != adj[v].end(); ++i)

            if (!visited[*i])

                DFSUtil(*i, visited);

    }

    // Method to check if all non-zero degree vertices are connected.

    // It mainly does DFS traversal starting from

    bool Graph::isConnected()

    {

        // Mark all the vertices as not visited

        bool visited[V];

        int i;

        for (i = 0; i < V; i++)

            visited[i] = false;

        // Find a vertex with non-zero degree

        for (i = 0; i < V; i++)

            if (adj[i].size() != 0)

                break;

        // If there are no edges in the graph, return true

        if (i == V)

            return true;

        // Start DFS traversal from a vertex with non-zero degree

        DFSUtil(i, visited);

        // Check if all non-zero degree vertices are visited

        for (i = 0; i < V; i++)

            if (visited[i] == false && adj[i].size() > 0)

                return false;

        return true;

    }

    /* The function returns one of the following values

     0 --> If grpah is not Eulerian

     1 --> If graph has an Euler path (Semi-Eulerian)

     2 --> If graph has an Euler Circuit (Eulerian)  */

    int Graph::isEulerian()

    {

        // Check if all non-zero degree vertices are connected

        if (isConnected() == false)

            return 0;

        // Count vertices with odd degree

        int odd = 0;

        for (int i = 0; i < V; i++)

            if (adj[i].size() & 1)

                odd++;

        // If count is more than 2, then graph is not Eulerian

        if (odd > 2)

            return 0;

        // If odd count is 2, then semi-eulerian.

        // If odd count is 0, then eulerian

        // Note that odd count can never be 1 for undirected graph

        return (odd) ? 1 : 2;

    }

    // Function to run test cases

    void test(Graph &g)

    {

        int res = g.isEulerian();

        if (res == 0)

            cout << "Graph is not Eulerian\n";

        else if (res == 1)

            cout << "Graph has a Euler path\n";

        else

            cout << "Graph has a Euler cycle\n";

    }

    // Driver program to test above function

    int main()

    {

        // Let us create and test graphs shown in above figures

        Graph g1(5);

        g1.addEdge(1, 0);

        g1.addEdge(0, 2);

        g1.addEdge(2, 1);

        g1.addEdge(0, 3);

        g1.addEdge(3, 4);

        cout<<"Result for Graph 1: ";

        test(g1);

        Graph g2(5);

        g2.addEdge(1, 0);

        g2.addEdge(0, 2);

        g2.addEdge(2, 1);

        g2.addEdge(0, 3);

        g2.addEdge(3, 4);

        g2.addEdge(4, 0);

        cout<<"Result for Graph 2: ";

        test(g2);

        Graph g3(5);

        g3.addEdge(1, 0);

        g3.addEdge(0, 2);

        g3.addEdge(2, 1);

        g3.addEdge(0, 3);

        g3.addEdge(3, 4);

        g3.addEdge(1, 3);

        cout<<"Result for Graph 3: ";

        test(g3);

        // Let us create a graph with 3 vertices

        // connected in the form of cycle

        Graph g4(3);

        g4.addEdge(0, 1);

        g4.addEdge(1, 2);

        g4.addEdge(2, 0);

        cout<<"Result for Graph 4: ";

        test(g4);

        // Let us create a graph with all veritces

        // with zero degree

        Graph g5(3);

        cout<<"Result for Graph 5: ";

        test(g5);

        return 0;

    }

C++ Program to Check Whether Graph is DAG[]

C++ Program to Check Whether Graph is DAG

This is a C++ Program to check whether graph is DAG. In mathematics and computer science, a directed acyclic graph (DAG Listeni/'dæg/), is a directed graph with no directed cycles. That is, it is formed by a collection of vertices and directed edges, each edge connecting one vertex to another, such that there is no way to start at some vertex v and follow a sequence of edges that eventually loops back to v again.

    #include<stdio.h>

    #include<iostream>

    #include<conio.h>

    using namespace std;

    int c = 0;

    struct adj_list

    {

            int dest;

            adj_list *next;

    }*np = NULL, *np1 = NULL, *p = NULL, *q = NULL;

    struct Graph

    {

            int v;

            adj_list *ptr;

    } array[6];

    void addReverseEdge(int src, int dest)

    {

        np1 = new adj_list;

        np1->dest = src;

        np1->next = NULL;

        if (array[dest].ptr == NULL)

        {

            array[dest].ptr = np1;

            q = array[dest].ptr;

            q->next = NULL;

        }

        else

        {

            q = array[dest].ptr;

            while (q->next != NULL)

            {

                q = q->next;

            }

            q->next = np1;

        }

    }

    void addEdge(int src, int dest)

    {

        np = new adj_list;

        np->dest = dest;

        np->next = NULL;

        if (array[src].ptr == NULL)

        {

            array[src].ptr = np;

            p = array[src].ptr;

            p->next = NULL;

        }

        else

        {

            p = array[src].ptr;

            while (p->next != NULL)

            {

                p = p->next;

            }

            p->next = np;

        }

        //addReverseEdge(src, dest);

    }

    void print_graph(int n)

    {

        for (int i = 0; i < n; i++)

        {

            cout << "Adjacency List of " << array[i].v << ": ";

            while (array[i].ptr != NULL)

            {

                cout << (array[i].ptr)->dest << " ";

                array[i].ptr = (array[i].ptr)->next;

            }

            cout << endl;

        }

    }

    int checkDAG(int n)

    {

        int count = 0;

        int size = n - 1;

        for (int i = 0; i < n; i++)

        {

            //cout << "Adjacency List of " << array[i].v << ": ";

            if (count == size)

            {

                return 1;

            }

            if (array[i].ptr == NULL)

            {

                count++;

                for (int j = 0; j < n; j++)

                {

                    while (array[j].ptr != NULL)

                    {

                        if ((array[j].ptr)->dest == (array[i].ptr)->dest)

                        {

                            (array[j].ptr)->dest = -1;

                        }

                        array[i].ptr = (array[i].ptr)->next;

                    }

                }

            }

        }

        return 0;

    }

    int main()

    {

        int n = 6;

        cout << "Number of vertices: " << n << endl;

        for (int i = 0; i < n; i++)

        {

            array[i].v = i;

            array[i].ptr = NULL;

        }

        addEdge(0, 1);

        addEdge(1, 2);

        addEdge(1, 3);

        addEdge(3, 4);

        addEdge(4, 5);

        addEdge(5, 3);

        addEdge(5, 2);

        print_graph(n);

        cout << "The given graph is 'Directed Acyclic Graph' :";

        if (checkDAG(n) == 1)

            cout << " True";

        else

            cout << " False";

    }

Create a Balanced Binary Tree of the Incoming Data[]

Create a Balanced Binary Tree of the Incoming Data

This is a C++ Program to create a balanced binary tree. In computer science, a self-balancing (or height-balanced) binary search tree is any node-based binary search tree that automatically keeps its height (maximal number of levels below the root) small in the face of arbitrary item insertions and deletions.

    #include <iostream>

    using namespace std;

    typedef struct bin_tree_node

    {

            int v;

            struct bin_tree_node *left;

            struct bin_tree_node *right;

    } BTNode;

    BTNode *create_bin_tree_node(int v)

    {

        BTNode *p = new BTNode;

        if (p != NULL)

        {

            p->v = v;

            p->left = NULL;

            p->right = NULL;

        }

        return p;

    }

    void create_balanced_bin_tree(BTNode **root, int arr[], int start, int end)

    {

        if (start <= end)

        {

            int mid = (start + end + 1) / 2;

            *root = create_bin_tree_node(arr[mid]);

            create_balanced_bin_tree(&((*root)->left), arr, start, mid - 1);

            create_balanced_bin_tree(&((*root)->right), arr, mid + 1, end);

        }

    }

    void print_bin_tree(BTNode *root)

    {

        if (root != NULL)

        {

            cout << root->v << " ";

            print_bin_tree(root->left);

            print_bin_tree(root->right);

        }

    }

    void print_bin_tree1(BTNode *root)

    {

        if (root != NULL)

        {

            print_bin_tree1(root->left);

            cout << root->v << " ";

            print_bin_tree1(root->right);

        }

    }

    int main(int argc, char* argv[])

    {

        int arr[30];

        for (int i = 0; i < 30; i++)

        {

            arr[i] = i;

        }

        BTNode *root = NULL;

        create_balanced_bin_tree(&root, arr, 0, 29);

        cout << "Preorder of balanced tree is: ";

        print_bin_tree(root);

        cout << "\nInorder of balanced tree is: ";

        print_bin_tree1(root);

        return 0;

    }

C++ Program to Find the Maximum Size Clique in a Graph[]

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;

    }
Advertisement