C++ Programming Code Examples

C++ > Computer Graphics Code Examples

Program to Find Strongly Connected Components in Graphs



Program to Find Strongly Connected Components in Graphs

This C++ program displays the nodes which are strongly connected to each other. Strongly connected subgraphs are those in which a path is available from any node of the subgraph to any other node present in it.

    #include<iostream>

    #include<conio.h>

    using namespace std;

    struct node_info

    {

        int no;

        int lv_time, st_time;

    }*q = NULL;

    struct node

    {

        node_info *pt;

        node *next;

    }*top = NULL, *p = NULL, *np = NULL;

    struct node1

    {

        node1 *link;

        node_info *pt1;

    }*head = NULL, *m = NULL, *n = NULL, *np1 = NULL;

    int c = 0;

    void push(node_info *ptr)

    {

        np = new node;

        np->pt = ptr;

        np->next = NULL;

        if (top == NULL)

        {

            top = np;

        }

        else

        {

            np->next = top;

            top = np;

        }

    }

    node_info *pop()

    {

        if (top == NULL)

        {

            cout<<"underflow\n";

        }

        else

        {

            p = top;

            top = top->next;

            return(p->pt);

            delete(p);

        }

    }

    void store(node_info *ptr1)

    {

        np1 = new node1;

        np1->pt1 = ptr1;

        np1->link = NULL;

        if (c == 0)

        {

            head = np1;

            m = head;

            m->link = NULL;

            c++;

        }

        else

        {

            m = head;

            np1->link = m;

            head = np1;

        }

    }

    void remove(int x)

    {

        m = head;

        if ((m->pt1)->no == x)

        {

            head = head->link;

            delete(m);

        }

        else

        {

            while ((m->pt1)->no != x && m->link != NULL)

            {

                n = m;

                m = m->link;

            }

            if ((m->pt1)->no == x)

            {

                n->link = m->link;

                delete(m);

            }

            else if (m->link == NULL)

            {

                cout<<"error\n";

            }

        }

    }            

    void topo(int *v, int am[][8], int i)

    {

        q = new node_info;

        q->no = i;

        q->st_time = c;

         push(q);

        v[i] = 1;

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

        {

            if (am[i][j] == 0  || (am[i][j] == 1 && v[j] == 1))

                continue;

            else if (am[i][j] == 1 && v[j] == 0)

            {

                c++;

                topo(v,am,j);

            }

        }

        c++;

        q = pop();

        q->lv_time = c;

        store(q);

        return;

    }

    void topo1(int *v, int am[][8], int i)

    {

        v[i] = 1;

        remove(i);

        cout<<i<<endl;

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

        {

            if (am[i][j] == 0  || (am[i][j] == 1 && v[j] == 1))

            {

                continue;

            }

            else if (am[i][j] == 1 && v[j] == 0)

            {

                topo1(v,am,j);

            }

        }

        return;

    }

    int main()

    {

        int v[8], am[8][8], amt[8][8];

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

            v[i] = 0;

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

        {

            cout<<"enter the values for adjacency matrix row:"<<i + 1<<endl;

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

            {

                cin>>am[i][j];

            }

        }

        topo(v, am, 0);

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

        {

            v[i] = 0;

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

                amt[j][i] = am[i][j];

        }

        while (head != NULL)

        {

            cout<<"Strongly Connected Components:\n";                 

                topo1(v, amt, (head->pt1)->no);

        }

        getch();

    }