the incidence matrix to the adjacency matrix of an edge graph

Question

the incidence matrix to the adjacency matrix of an edge graph

It is necessary to transform the edge graph from the incidence matrix to the adjacency matrix. for those who do not understand graphs, the algorithm is generally as follows: you need to find all the elements with the value 1 in the first matrix in each row and put 1 in the second matrix at the intersection of these elements. I wrote a program, but why does it output something not quite right, please help me

{1 ,1, 0, 0},{1,0,1,0},{0,0,0,1},{0,1,1,0}}
переделать из этой матрицы инцидентности в матрицу смежности.


    
      for (int j = 1; j <= V; j++)
            {
                for (int i = 1; i <= V; i++)
                {
                    if (I[i][j] == 1) {
                        count += 1;
        
                    }
                }
            }
        
        
        
            int count2 = count / 2;
            cout << count2;
        
            cout << "\nMatritsa smejnosti\n";
            int SM[100][100];
            int p1, p2;
        
            for (int i = 1; i <= count2; i++) {
                for (int j = 1; j <= count2; j++) {
                    SM[i][j] = 0;
                }
            }
            cout << "\nCALC\n";
            for ( int i=1 ; i<= count2; i++) {
                for (int j=1; j <= count2; j++) {
        
                    if (I[i][j] == 1) {
        
                        for (int k = j + 1; k <= count2; k++) {
                            if (I[i][k] == 1) {
                                SM[k][j] = 1;
                        SM[j][k] = 1;
        
                            }
                        }
        
        
                    }
        
                }
            }
            //_________________________OUTPUT
            cout << "\nSM matrix:\n" << endl;
            for (int j = 1; j <= count2; j++)
            {
                for (int i = 1; i <= count2; i++)
                {
                    cout << "  " << SM[i][j];
                }
                cout << endl;
            }
            cout << endl;
        
        
            //end
            _getch();
        }

2

c++графы

Author: Igor, 2020-09-26

Source

2 answers

score 5 · Answer 1

By the size of the original matrix, we determine V and E - the number of vertices and edges (for some reason, the program implies their equality).

Next, we iterate through all the unit pairs along the lines (i.e., we find the pairs of edges that are incident to this vertex)

for (v = 1;v<=V;v++)
    for (e1 = 1; e1 <=E-1;e1++)
        if (I[v][e1])
             for (e2 = e1+1; e2 <=E; e2++)
                  if (I[v][e2]) {
                      AR[e1][e2] = 1;
                      AR[e2][e1] = 1;
                  }

score 3 · Answer 2

A little ahead of the MBo :) - while I was writing all the comments. Well, don't waste the same code ...

Since you have C++, it is better to use vectors.

#include <vector>
#include <iostream>

using namespace std;

vector<vector<int>> rebuild(const vector<vector<int>>& G)
{
    size_t vxs = G[0].size(); // Количество столбцов

    // Здесь по-хорошему нужно убедиться, что
    // в каждой строке одно и то же число столбцов

    vector<vector<int>> R(vxs, vector<int>(vxs,0)); // Результат

    // Проход по строкам
    for(const auto& s: G)
    {
        vector<size_t> ix; // Собираем ненулевые значения
        for(size_t i = 0; i < s.size(); ++i)
            if (s[i]) ix.push_back(i);
        // Если их хотя бы 2...
        if (ix.size() > 1)
        {
            // Каждый с каждым - расставляем единицы
            for(size_t i = 0; i < ix.size()-1; ++i)
                for(size_t j = i+1; j < ix.size(); ++j)
                    R[ix[i]][ix[j]] = R[ix[j]][ix[i]] = 1;
        }
    }
    return R;
}

int main([[maybe_unused]] int argc,
         [[maybe_unused]] const char * argv[])
{
    vector<vector<int>> G = {{1,1,0,0},{1,0,1,1},{0,0,0,1},{0,1,1,0}};

    vector<vector<int>> R = rebuild(G);

    for(size_t i = 0; i < R.size(); ++i)
    {
        for(size_t j = 0; j < R[i].size(); ++j)
            cout << R[i][j] << "  ";
        cout << endl;
    }
}