GraphForge/MatrixOperations.cpp at main · Mayukh-71/GraphForge · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include<bits/stdc++.h>
#include "ReadGraph.cpp"
using namespace std;
vector<vector<int>>MatrixMultiply(vector<vector<int>>A,vector<vector<int>>B)
{
    int a=A.size();
    vector<vector<int>>C(a,vector<int>(a,0));
    for(int i=0;i<a;i++)
    {
        for(int j=0;j<a;j++)
        {
            int s=0;
            for(int k=0;k<a;k++)
                s=s+A[i][k]*B[k][j];
            C[i][j]=s;
        }
    }
    return C;
}
vector<vector<int>>MatrixAdd(vector<vector<int>>A,vector<vector<int>>B)
{
    int a=A.size();
    vector<vector<int>>C(a,vector<int>(a,0));
    for(int i=0;i<a;i++)
        for(int j=0;j<a;j++)
            C[i][j]=A[i][j]+B[i][j];
    return C;
}
vector<vector<int>>MatrixMultiplyEle(vector<vector<int>>A,vector<vector<int>>B)
{
    int a=A.size();
    vector<vector<int>>C(a,vector<int>(a,0));
    for(int i=0;i<a;i++)
        for(int j=0;j<a;j++)
            C[i][j]=A[i][j]*B[i][j];
    return C;
}
int main()
{
    auto Graph=CreateGraph();
    vector<vector<int>>AO=Graph.matrix;
    vector<string>N=Graph.nodes;
    int c=Graph.C;
    int a=N.size();
    vector<vector<int>>A(a,vector<int>(a,0));
    for(int i=0;i<a;i++)
        for(int j=0;j<a;j++)
            if(AO[i][j]!=0)
                A[i][j]=1;
    vector<vector<int>>AT(a,vector<int>(a,0));
    for(int i=0;i<a;i++)
        for(int j=0;j<a;j++)
            AT[i][j]=A[j][i];
    if(A==AT)
        cout<<"Since it is an undirected graph, so A is equal to A transpose.\n";
    else
        cout<<"Since it is a directed graph, so A is not equal to A transpose.\n";
    if(c==0)
        cout<<"Since this is an undirected graph, so there is no degree of nodes..\n";
    else
    {
        vector<vector<int>>AAT=MatrixMultiply(A,AT);
        vector<vector<int>>ATA=MatrixMultiply(AT,A);
        cout<<"Calculating the out-degrees of each node of the graph from AAT:-\n";
        for(int i=0;i<a;i++)
            cout<<N[i]<<"->"<<AAT[i][i]<<"\n";
        cout<<"Calculating the in-degrees of each node of the graph from ATA:-\n";
        for(int i=0;i<a;i++)
            cout<<N[i]<<"->"<<ATA[i][i]<<"\n";
    }
    cout<<"Enter path length l:-";
    int l;
    cin>>l;
    cout<<"Calculating the no of paths of length l from each nodes to the other nodes:-\n";
    vector<vector<int>>S=A;
    for(int i=0;i<l-1;i++)
        S=MatrixMultiply(S,A);
    for(int i=0;i<a;i++)
    {
        for(int j=0;j<a;j++)
            cout<<S[i][j]<<" ";
        cout<<"\n";
    }
    cout<<"The Path Matrix P:-\n";
    vector<vector<int>>B=A;
    S=A;
    for(int i=0;i<a-1;i++)
    {
        S=MatrixMultiply(S,A);
        B=MatrixAdd(B,S);
    }
    vector<vector<int>>P(a,vector<int>(a,0));
    for(int i=0;i<a;i++)
    {
        for(int j=0;j<a;j++)
            if(B[i][j]!=0)
                P[i][j]=1;
    }
    for(int i=0;i<a;i++)
    {
        for(int j=0;j<a;j++)
            cout<<P[i][j]<<" ";
        cout<<"\n";
    }
    cout<<"The matrix P*PT(* is AND/element wise multiplication) is:-\n";
    vector<vector<int>>PT(a,vector<int>(a,0));
    for(int i=0;i<a;i++)
        for(int j=0;j<a;j++)
            PT[i][j]=P[j][i];
    vector<vector<int>>PPT=MatrixMultiplyEle(P,PT);
    for(int i=0;i<a;i++)
    {
        for(int j=0;j<a;j++)
            cout<<PPT[i][j]<<" ";
        cout<<"\n";
    }
    cout<<"Therefore the strongly connected components of the matrix are:-\n";
    for(int i=0;i<a;i++)
    {
        int r=0;
        for(int j=0;j<a;j++)
            if(PPT[i][j]==1)
                r=1;
        if(r==0)
            cout<<N[i]<<"\n";
    }
    for(int j=0;j<a;j++)
    {
        int r=0;
        for(int i=0;i<a;i++)
        {
            if(PPT[i][j]==1)
            {
                vector<int>U(a,0);
                cout<<N[i]<<" ";
                PPT[i]=U;
                r=1;
            }
        }
        if(r==1)
            cout<<"\n";
    }
    return 0;
}