如何将邻接矩阵转换为发病率矩阵，反之亦然? [英] How do you transform Adjacency matrices to Incidence matrices and vice-versa?

问题描述

假设矩阵如下:(N = 4)

Let's say the matrices are the following: (N = 4)

邻接:

0110100110010110

0110 1001 1001 0110

发生率:

1100101001010011

1100 1010 0101 0011

仅具有邻接关系，如何才能获得关联矩阵?

How can you get the Incidence matrix from having just the Adjacency one, and vice-versa?

P.S:我从.txt文档中获得的邻接矩阵，我已将其读入数组并通过以下算法将其获取:

P.S: The Adjacency Matrix I'm getting from a .txt document, which I've read into an array and got it by the following algorithm:

int read(){

    ifstream graf("graf.txt");
    if(graf.is_open()){
        graf >> n;
        for (int i=0; i < n; i++) {
        for(int j = 0; j<2; j++)
                graf >> Graf[i][j];
        }
    }
    graf.close();
    return 0;
}

void adj() {
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++)
        sz[i][j] = 0;
    for (int i=0; i<n; i++)
        for (int j=0; j<2; j++)
        {sz[Graf[i][j]-1][Graf[i][j+1]-1] = 1;}
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++)
        sz[j][i] = sz[i][j];
}

推荐答案

通过查看顶点之间的每个可能的连接，可以将邻接矩阵转换为关联矩阵，并且只要确实存在连接，就可以在关联矩阵中添加一条边.不过，请注意仅一次查看每个顶点组合.

You can turn an adjacency matrix into an incidence matrix by looking at every possible connection between vertices and whenever there is indeed a connection, add an edge to your incidence matrix. Be careful to look at each combination of vertices only once, though.

相反，您可以简单地查看每个边缘.关联矩阵为每个边指定了它连接的两个顶点.

The other way around, you can simply look at each edge. The incidence matrix specifies for each edge, which two vertices it connects.

您无法重新创建的一种情况是，当多个边连接相同的两个顶点时.

The one situation you cannot recreate is when more than a single edge connects the same two vertices.

这里有一些源代码来说明上述说明(查看它的工作原理):

Here's some source code to illustrate the above explanations (See it work):

#include <vector>
#include <cassert>
#include <iostream>

typedef std::vector<bool> matrix_row;
typedef std::vector<matrix_row> matrix; // Saves some typing

// The initially given matrix. Uses C++11 initializer list.
matrix adj = 
{
    { 1, 1, 1, 0 },
    { 1, 0, 0, 1 },
    { 1, 0, 0, 1 },
    { 0, 1, 1, 0 }
};

matrix adjacency_to_incidence(const matrix &adj)
{
    int cols = adj.size();
    assert(cols > 0);

    int rows = adj[0].size();
    assert(rows > 0);

    assert(rows == cols);

    int edge = 0;
    matrix incidence;

    for (int col = 0; col < cols; ++col) {
        // We only look at half the adjacency matrix, so that we only add each
        // edge to the incidence matrix once.
        for (int row = 0; row <= col; ++row) {
            if (adj[col][row]) {
                incidence.push_back(matrix_row(cols, 0));
                incidence[edge][row] = incidence[edge][col] = 1;
                ++edge;
            }
        }
    }

    return incidence;
}

matrix incidence_to_adjacency(const matrix &inc)
{
    int edges = inc.size();
    assert(edges > 0);

    int vertices = inc[0].size();
    assert(vertices > 0);

    matrix adjacency(vertices, matrix_row(vertices, 0));

    for (int edge = 0; edge < edges; ++edge) {
        int a = -1, b = -1, vertex = 0;
        for (; vertex < vertices && a == -1; ++vertex) {
            if (inc[edge][vertex]) a = vertex;
        }
        for (; vertex < vertices && b == -1; ++vertex) {
            if (inc[edge][vertex]) b = vertex;
        }
        if (b == -1) b = a;
        adjacency[a][b] = adjacency[b][a] = 1;
    }

    return adjacency;
}

void print_matrix(const matrix &m)
{
    int cols = m.size();
    if (cols == 0) return;
    int rows = m[0].size();
    if (rows == 0) return;

    for (int c = 0; c < cols; ++c) {
        for (int r = 0; r < rows; ++r) {
            std::cout << m[c][r] << " ";
        }
        std::cout << std::endl;
    }
    std::cout << std::endl;
}

int main()
{
    matrix incidence = adjacency_to_incidence(adj);
    print_matrix(incidence);

    matrix adjacency = incidence_to_adjacency(incidence);
    print_matrix(adjacency);

    return 0;
}

当图形很大时，可能值得考虑在 adjacency_to_incidence 中运行两次循环.第一次计算边的数量，然后用足够的空间初始化矩阵，然后再次遍历邻接矩阵以填充入射矩阵.

When your graph is large, it might be worth considering running the loop in adjacency_to_incidence twice. The first time to count the amount of edges, then initialize the matrix with enough space and then loop over the adjacency matrix again to populate the incidence matrix.

这篇关于如何将邻接矩阵转换为发病率矩阵，反之亦然?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！